C++ Data structures

Open-source C++ projects categorized as Data structures | Edit details
Related topics: #CPP #Algorithms #C++ #header-only #C

Top 23 C++ Data structure Projects

  • GitHub repo Protobuf

    Protocol Buffers - Google's data interchange format

    Project mention: protobuf-related: intro + write a proto | dev.to | 2022-01-07

    I will be quite short in this section: just follow the guidelines provided by Google.

  • GitHub repo Apache Thrift

    Apache Thrift

    Project mention: Ask HN: Who Wants to Collaborate? | news.ycombinator.com | 2022-01-01
  • SonarQube

    Static code analysis for 29 languages.. Your projects are multi-language. So is SonarQube analysis. Find Bugs, Vulnerabilities, Security Hotspots, and Code Smells so you can release quality code every time. Get started analyzing your projects today for free.

  • GitHub repo NumCpp

    C++ implementation of the Python Numpy library

    Project mention: Machine Learning using C++ vs Python | reddit.com/r/cpp_questions | 2021-12-27

    Yeah, as someone who writes C++ daily for their ML related job, I concur that the cost of executing a convolutions dwarves the overhead of calling from Python. So as much as I like C++ over Python (because static compilation to find little typos or type mismatches ahead of time is much nicer than exploding 5 minutes later into my batched vision recognition problem 😠), generally for small problems, Python is a nice quick and dirty approach. I do have my eye though on this little C++ numpy clone.

  • GitHub repo immer

    Postmodern immutable and persistent data structures for C++ — value semantics at scale (by arximboldi)

    Project mention: I started developing a level editor | reddit.com/r/gameenginedevs | 2022-01-14

    I haven't tried it, but https://github.com/arximboldi/immer might help.

  • GitHub repo kactl

    KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)

    Project mention: Competitive Programming Is Useless | news.ycombinator.com | 2021-08-23

    There's not _that_ many algorithms or data structures you see in competitive programming, and the vast majority of them aren't advanced. You do need to memorize a good portion of them, but doing so is the easy part towards becoming good at it.

    You can read one moderate length book and know all of the DSes and algorithms you'll need for 99.9% of the time. cses.fi/book is a good one with a free version if you're curious.

    https://github.com/kth-competitive-programming/kactl may also be of interest, it contains a good amount of the algorithms/DSes you'd ever need on a few printable pages (20ish).

  • GitHub repo etl

    Embedded Template Library

    Project mention: Which C++ concepts you use in embedded world? | reddit.com/r/cpp | 2022-01-16
  • GitHub repo robin-map

    C++ implementation of a fast hash map and hash set using robin hood hashing

    Project mention: A brief and incomplete guide for selecting the appropriate container from inside/outside the C++ standard library, based on performance characteristics, functionality and benchmark results | reddit.com/r/cpp | 2021-12-11

    a = yes, b = no 0. Is all you're doing just inserting to the back of the container and iterating? 0a. Do you know the largest possible maximum capacity you will ever have for this container, and is the lowest possible maximum capacity not too far away from that? 0aa. Use an array. 0ab. Use a vector. 0b. Can you change your data layout or your processing strategy so that back insertion and iterating would be all you're doing? 0ba. Goto 0a. 0bb. Goto 1. 1. Is the use of the container stack-like, queue-like or ring-like? 1a. If stack-like, use plf::stack, if queue-like, use plf::queue (both are faster than the std:: equivalent adaptors, have stable pointers to elements and are configurable in terms of memory block sizes). If ring-like, use "ring_span lite". 1b. If not, goto 2. 2. Does each element need to be accessible via an identifier ie. key? ie. is the data associative. 2a. If so, is the number of elements small and the type sizeof not large? 2aa. If so, is the value of an element also the key? 2aaa. If so, just make an array or vector of elements, and sequentially-scan to lookup elements. Benchmark vs absl:: sets below. 2aab. If not, make a vector of key/element structs, and do sequential scans of the vector to find the element based on the key. Benchmark vs absl:: maps below. 2ab. If not, do the elements need to have an order? 2aba. If so, is the value of the element also the key? 2abaa. If so, can multiple keys have the same value? 2abaaa. If so, use absl::btree_multiset. 2abaab. If not, use absl::btree_set. 2abab. If not, can multiple keys have the same value? 2ababa. If so, use absl::btree_multimap. 2ababb. If not, use absl::btree_map. 2abb. If no order needed, is the value of the element also the key? 2abba. If so, can multiple keys have the same value? 2abbaa. If so, use std::unordered_multiset or absl::btree_multiset. 2abbab. If not, is pointer stability to elements necessary? 2abbaba. If so, use absl::node_hash_set. 2abbabb. If not, use absl::flat_hash_set. 2abbb. If not, can multiple keys have the same value? 2abbba. If so, use std::unordered_multimap or absl::btree_multimap. 2abbbb. If not, is on-the-fly insertion and erasure common in your use case, as opposed to mostly lookups? 2abbbba. If so, use robin-map. 2abbbbb. If not, is pointer stability to elements necessary? 2abbbbba. If so, use absl::flat_hash_map > . Use absl::node_hash_map if pointer stability to keys is also necessary. 2abbbbbb. If not, use absl::flat_hash_map. 2b. If not, goto 3. Note: if iteration over the associative container is frequent rather than rare, try the std:: equivalents to the absl:: containers or tsl::sparse_map. Also take a look at this page of benchmark conclusions for more definitive comparisons across more use-cases and C++ hash map implementations. 3. Are stable pointers/iterators/references to elements which remain valid after non-back insertion/erasure required, and/or is there a need to sort non-movable/copyable elements? 3a. If so, is the order of elements important and/or is there a need to sort non-movable/copyable elements? 3aa. If so, will this container often be accessed and modified by multiple threads simultaneously? 3aaa. If so, use forward_list (for its lowered side-effects when erasing and inserting). 3aab. If not, do you require range-based splicing between two or more containers (as opposed to splicing of entire containers)? 3aaba. If so, use std::list. 3aabb. If not, use plf::list. 3ab. If not, use hive. 3b. If not, goto 4. 4. Is the order of elements important? 4a. If so, are you almost entirely inserting/erasing to/from the back of the container? 4aa. If so, use vector, with reserve() if the maximum capacity is known in advance (or array). 4ab. If not, are you mostly inserting/erasing to/from the front of the container? 4aba. If so, use deque. 4abb. If not, is insertion/erasure to/from the middle of the container frequent when compared to iteration or back erasure/insertion? 4abba. If so, is it mostly erasures rather than insertions, and can the processing of multiple erasures be delayed until a later point in processing, eg. the end of a frame in a video game? 4abbaa. If so, try the vector erase_if pairing approach listed at the bottom of this guide, and benchmark against plf::list to see which one performs best. Use deque with the erase_if pairing if the number of elements is very large. 4abbab. If not, goto 3aa. 4abbb. If not, are elements large or is there a very large number of elements? 4abbba. If so, benchmark vector against plf::list, or if there is a very large number of elements benchmark deque against plf::list. 4abbbb. If not, do you often need to insert/erase to/from the front of the container? 4abbbba. If so, use deque. 4abbbbb. If not, use vector, or array if number of elements is known in advance. 4b. If not, goto 5. 5. Is non-back erasure frequent compared to iteration? 5a. If so, is the non-back erasure always at the front of the container? 5aa. If always at the front, use deque. 5ab. If not, is the type large, non-trivially copyable/movable or non-copyable/movable? 5aba. If so, use hive. 5abb. If not, is the number of elements very large? 5abba. If so, use a deque with a swap-and-pop approach (to save memory vs vector - assumes standard deque implementation of fixed block sizes) - swap the element you wish to erase with the back element, and then pop_back() to erase. Benchmark vs hive. 5abbb. If not, use a vector with a swap-and-pop approach and benchmark vs hive. 5b. If not, goto 6. 6. Can non-back erasures be delayed until a later point in processing eg. the end of a video game frame? 6a. If so, is the type large or is the number of elements large? 6aa. If so, use hive. 6ab. If not, is consistent latency more important than lower average latency? 6aba. If so, use hive. 6abb. If not, try the erase_if pairing approach listed below with vector, or with deque if the number of elements is large. Benchmark this approach against hive to see which performs best. 6b. If not, use hive. Vector erase_if pairing approach: Try pairing the type with a boolean, in a vector, then marking this boolean for erasure during processing, and then use erase_if with the boolean to remove multiple elements at once at the designated later point in processing. Alternatively if there is a condition in the element itself which identifies it as needing to be erased, try using this directly with erase_if and skip the boolean pairing. If you know the total number of elements in advance, use array instead of vector, or reserve() with vector.

  • Scout APM

    Less time debugging, more time building. Scout APM allows you to find and fix performance issues with no hassle. Now with error monitoring and external services monitoring, Scout is a developer's best friend when it comes to application development.

  • GitHub repo stdgpu

    stdgpu: Efficient STL-like Data Structures on the GPU

  • GitHub repo PGM-index

    🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

    Project mention: PGM Indexes: Learned indexes that match B-tree performance with 83x less space | news.ycombinator.com | 2021-01-25

    Yep, I'm working on a multidimensional version that I hope to upload to the main repo (https://github.com/gvinciguerra/PGM-index) in a few weeks.

  • GitHub repo Hopscotch map

    C++ implementation of a fast hash map and hash set using hopscotch hashing

    Project mention: Any suggestions for resources to optimize for memory allocation/reallocation? | reddit.com/r/cpp | 2021-01-24

    using an open-addressing hash table, such as abseil flat_hash_map or tessil/hopscotch-map

  • GitHub repo ewig

    The eternal text editor — Didactic Ersatz Emacs to show immutable data-structures and the single-atom architecture

    Project mention: Ask HN: How to learn about text editor architectures and implementations? | news.ycombinator.com | 2022-01-10

    Ewig is an interesting implementation using immutable data structures. https://github.com/arximboldi/ewig Very proof of concept, tries to be a little vi like. Might be worth checking out.

  • GitHub repo ordered-map

    C++ hash map and hash set which preserve the order of insertion

    Project mention: What’s the fastest doubly linked list out there? | reddit.com/r/cpp_questions | 2021-07-27

    Doing some searching, looks like here's an example of someone building one, https://github.com/Tessil/ordered-map

  • GitHub repo Data-Structures-and-Algorithms-in-cpp

    This repository is in development phase and will soon provide you with c++ code of various data structures and algorithms

  • GitHub repo Daily-Coding-DS-ALGO-Practice

    A open source project🚀 for bringing all interview💥💥 and competative📘 programming💥💥 question under one repo📐📐

    Project mention: My First Opensource Program Experience [LGMSOC] | dev.to | 2021-08-16

    At the time when I Joined the Programme I didn't know a lot about Opensource. I just know that what is commit, pull request, issue, how to create repository but not have implemented as I should. While the program runs I contribute to Daily-Algo-Pratice, Hacking-Script and makesmatheasy and I found my many mistake which are pointed by my mentor. As well as due to the Programme I became more active on GitHub and solved many problem and create many projects which helps me a lot to learn about many expects of programming that how a great project is arranged and etc. Before the programme I have listen about Summer of code(SOC) but never Participated. It was a great experienced through out the programme

  • GitHub repo Data-Structures-and-Algorithms

    Data Structures and Algorithms implemented In Python, C, C++, Java or any other languages. Aimed to help strengthen the concepts of DSA. Give a Star 🌟 if it helps you.

  • GitHub repo Ygg

    An intrusive C++17 implementation of a Red-Black-Tree, a Weight Balanced Tree, a Dynamic Segment Tree and much more!

  • GitHub repo sdsl-lite

    Succinct Data Structure Library 3.0 (by xxsds)

    Project mention: SDSL-RS: A Rust interface for the C++ Succinct Data Structure Library. | reddit.com/r/rust | 2021-05-26

    This is awesome. As somebody who was actively involved in the development of SDSL I want to point out that https://github.com/xxsds/sdsl-lite is a more actively developed fork of SDSL with a more permissible license.

  • GitHub repo DSAQuestions

    Collection of data-structures and algorithms along with resources and guidelines for mastering coding

    Project mention: Data structures and algorithms | dev.to | 2021-03-10

    Data structures and algorithms are a must for any coding interview. There is no well set road map for learning data structures and algorithms other than hard work, consistency and practice. Since this is a very vast field, therefore, only regular practice can help you become a good programmer. While learning data structures and algorithms, I have solved various questions and decided to compile all the codes I come across into a git repository. Everyone and anyone enthusiastic in data structures and algorithms can contribute to the repository. All you have to do is: fork, clone, create a branch , write your code and send a pull request describing the code you have written. Here is the link of the git repository: DATA STRUCTURES AND ALGORITHMS Hope this will help learners who want to learn DSA! Follow me on Github Happy coding!

  • GitHub repo nelson

    Nelson numerical interpreter

  • GitHub repo cpp

    algorithms in c++ (by vsmolyakov)

    Project mention: Algorithms C++ | dev.to | 2021-05-07

    } For C(n=5, k=2), the code above produces the following output: Top-down DP: -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 3 3 -1 -1 -1 -1 -1 -1 4 6 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n=5, k=2): 10 Bottom-up DP: 1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 2 1 -1 -1 -1 -1 -1 1 3 3 -1 -1 -1 -1 -1 1 4 6 -1 -1 -1 -1 -1 1 5 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 C(n=5, k=2): 10 The time complexity is O(n * k) and the space complexity is O(n * k). In the case of top-down DP, solutions to sub-problems are stored (memoized) as needed, whereas in the bottom-up DP, the entire table is computed starting from the base case. Note: a small DP table size (V=8) was chosen for printing purposes, a much larger table size is recommended. Code All code is available at: https://github.com/vsmolyakov/cpp To compile C++ code you can run the following command:

  • GitHub repo tfds

    A collection of fast data structures in C++

    Project mention: tfds - a small collection of fast data structures in C++ | reddit.com/r/cpp | 2021-04-28
  • GitHub repo parallel-kd-tree

    Parallel implementation of k-d tree with C++17, MPI and OpenMP

    Project mention: My first non-trivial project in C++ and MPI/OpenMP | reddit.com/r/cpp | 2022-01-06

    Source code: https://github.com/fAndreuzzi/parallel-kd-tree

  • GitHub repo BitsPlease-solutions

    Solutions For Problems uploaded in

NOTE: The open source projects on this list are ordered by number of github stars. The number of mentions indicates repo mentiontions in the last 12 Months or since we started tracking (Dec 2020). The latest post mention was on 2022-01-16.

C++ Data structures related posts

Index

What are some of the best open-source Data structure projects in C++? This list will help you:

Project Stars
1 Protobuf 52,735
2 Apache Thrift 8,865
3 NumCpp 2,092
4 immer 1,953
5 kactl 1,514
6 etl 1,060
7 robin-map 659
8 stdgpu 639
9 PGM-index 573
10 Hopscotch map 516
11 ewig 445
12 ordered-map 324
13 Data-Structures-and-Algorithms-in-cpp 264
14 Daily-Coding-DS-ALGO-Practice 241
15 Data-Structures-and-Algorithms 195
16 Ygg 90
17 sdsl-lite 50
18 DSAQuestions 39
19 nelson 38
20 cpp 38
21 tfds 17
22 parallel-kd-tree 6
23 BitsPlease-solutions 3
Find remote jobs at our new job board 99remotejobs.com. There are 29 new remote jobs listed recently.
Are you hiring? Post a new remote job listing for free.
OPS - Build and Run Open Source Unikernels
Quickly and easily build and deploy open source unikernels in tens of seconds. Deploy in any language to any cloud.
github.com/nanovms