SaaSHub helps you find the best software and product alternatives Learn more →
Top 23 C++ Data structure Projects
-
C-Plus-Plus
Collection of various algorithms in mathematics, machine learning, computer science and physics implemented in C++ for educational purposes.
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
cp-algorithms
Algorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)
-
immer
Postmodern immutable and persistent data structures for C++ — value semantics at scale (by arximboldi)
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
DataStructures-Algorithms
This repo contains links of resources, theory subjects content and DSA questions & their solution for interview preparation from different websites like geeksforgeeks, leetcode, etc.
-
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
-
ewig
The eternal text editor — Didactic Ersatz Emacs to show immutable data-structures and the single-atom architecture
-
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
-
Daily-Coding-DS-ALGO-Practice
A open source project🚀 for bringing all interview💥💥 and competative📘 programming💥💥 question under one repo📐📐
-
ExcaliburHash
Excalibur Hash is a high-speed hash map and hash set, ideal for performance-critical uses like video games
-
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.
-
SaaSHub
SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives
Project mention: Reverse Engineering Protobuf Definitions from Compiled Binaries | news.ycombinator.com | 2024-03-09For at least 4 years protobuf has had decent support for self-describing messages (very similar to avro) as well as reflection
https://github.com/protocolbuffers/protobuf/blob/main/src/go...
Xgooglers trying to make do on the cheap will just create a Union of all their messages and include the message def in a self-describing message pattern. Super-sensitive network I/O can elide the message def (empty buffer) and any for RecordIO clone well file compression takes care of the definition.
Definitely useful to be able to dig out old defs but protobuf maintainers have surprisingly added useful features so you don’t have to.
Bonus points tho for extracting the protobuf defs that e.g. Apple bakes into their binaries.
Project mention: Do you know of any helpful sources like this for leetcode? | /r/csMajors | 2023-10-02I've been learning alot from this git repository: https://cp-algorithms.com/ . Do you know of any of any sources or repositories like this that help with Leetcode or problem solving?
Project mention: Popcount walks: next, previous, toward and nearest | news.ycombinator.com | 2023-11-14As a competitive programmer, I’ve seen similar ‘magic’ tricks here: https://github.com/kth-competitive-programming/kactl/blob/ma... (page 23)
I've been working on an editor (not text) in C++ and pretty early got into undo/redo. I went down the route of doIt/undoIt for commands but that quickly got old. There was both the extra work needed to implement undo separately for every operation, but also the nagging feeling that the undo operation for some operation wasn't implemented correctly.
In the end, I switched to representing the entire document state using persistent data structures (using the immer library). This vastly simplified things and implementing undo/redo becomes absolutely trivial when using persistent data structures. It's probably not something that is suitable for all domains, but worth checking out.
https://github.com/arximboldi/immer
Project mention: Just started reading this book "Groking the coding interview" found this paragraph worth sharing | /r/developersIndia | 2023-05-18
If you can't use the STL because of exceptions: https://www.etlcpp.com/
In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible)
Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem.
“With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate.”
I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (Although boost and Absl forcibly grow/rehash at 0.85-0.9):
https://strong-starlight-4ea0ed.netlify.app/
Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC, respectively). Absl and Boost are the well-known SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (it caches a 4-bit fragment of the hash code to avoid most key comparisons).
As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the better performer) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion.
I’ve only read briefly about bi-directional linear probing – never experimented with it.
PGM Index
You might be interested in ewig and immer by Juan Pedro Bolivar Puente:
https://github.com/arximboldi/ewig
https://github.com/arximboldi/immer
See the author instantly opening a ~1GB text file with async loading, paging through, copying/pasting, and undoing/redoing in their prototype “ewig” text editor about 27 minutes into their talk here:
https://m.youtube.com/watch?v=sPhpelUfu8Q
It’s backed by a “vector of vectors” data structure called a relaxed radix balanced tree:
https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
That original paper has seen lots of attention and attempts at performance improvements, such as:
https://hypirion.com/musings/thesis
https://github.com/hyPiRion/c-rrb
Project mention: Atree: A simple and efficient pointer-free tree implementation | news.ycombinator.com | 2023-12-16
Project mention: Excalibur Hash is a high-speed hash map and hash set | news.ycombinator.com | 2024-01-10
C++ Data structures related posts
- Reverse Engineering Protobuf Definitions from Compiled Binaries
- Modern C++ Programming Course
- Popcount walks: next, previous, toward and nearest
- Do you know of any helpful sources like this for leetcode?
- How to learn to use protoc in 21 easily infuriating steps
- What's involved in protobuf encoding?
- Trying To Solve The Confusion of Choice Between gRPC vs REST🕵
-
A note from our sponsor - SaaSHub
www.saashub.com | 24 Apr 2024
Index
What are some of the best open-source Data structure projects in C++? This list will help you:
Project | Stars | |
---|---|---|
1 | Protobuf | 63,586 |
2 | C-Plus-Plus | 29,048 |
3 | cp-algorithms | 6,464 |
4 | algorithms_and_data_structures | 5,767 |
5 | NumCpp | 3,377 |
6 | kactl | 2,496 |
7 | immer | 2,420 |
8 | Coding | 2,290 |
9 | etl | 1,942 |
10 | DataStructures-Algorithms | 1,599 |
11 | robin-map | 1,165 |
12 | stdgpu | 1,077 |
13 | PGM-index | 751 |
14 | Hopscotch map | 698 |
15 | megahit | 555 |
16 | ewig | 517 |
17 | ordered-map | 500 |
18 | Leetcode | 471 |
19 | Data-Structures-and-Algorithms-in-cpp | 361 |
20 | atree | 358 |
21 | Daily-Coding-DS-ALGO-Practice | 313 |
22 | ExcaliburHash | 306 |
23 | Data-Structures-and-Algorithms | 269 |
Sponsored