Hopscotch map
C++ implementation of a fast hash map and hash set using hopscotch hashing (by Tessil)
C++ Btree
Git mirror of the official (mercurial) repository of cppbtree (by algorithmninja)
Hopscotch map  C++ Btree  

3    
718  71  
    
3.0  0.0  
5 days ago  almost 10 years ago  
C++  C  
MIT License  Apache License 2.0 
The number of mentions indicates the total number of mentions that we've tracked plus the number of user suggested alternatives.
Stars  the number of stars that a project has on GitHub. Growth  month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Stars  the number of stars that a project has on GitHub. Growth  month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Hopscotch map
Posts with mentions or reviews of Hopscotch map.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 20220630.

boost::unordered map is a new king of data structures
Unordered hash map shootout CMAP = https://github.com/tylov/STC KMAP = https://github.com/attractivechaos/klib PMAP = https://github.com/greg7mdp/parallelhashmap FMAP = https://github.com/skarupke/flat_hash_map RMAP = https://github.com/martinus/robinhoodhashing HMAP = https://github.com/Tessil/hopscotchmap TMAP = https://github.com/Tessil/robinmap UMAP = std::unordered_map Usage: shootout [nmillion=40 keybits=25] Random keys are in range [0, 2^25). Seed = 1656617916: T1: Insert/update random keys: KMAP: time: 1.949, size: 15064129, buckets: 33554432, sum: 165525449561381 CMAP: time: 1.649, size: 15064129, buckets: 22145833, sum: 165525449561381 PMAP: time: 2.434, size: 15064129, buckets: 33554431, sum: 165525449561381 FMAP: time: 2.112, size: 15064129, buckets: 33554432, sum: 165525449561381 RMAP: time: 1.708, size: 15064129, buckets: 33554431, sum: 165525449561381 HMAP: time: 2.054, size: 15064129, buckets: 33554432, sum: 165525449561381 TMAP: time: 1.645, size: 15064129, buckets: 33554432, sum: 165525449561381 UMAP: time: 6.313, size: 15064129, buckets: 31160981, sum: 165525449561381 T2: Insert sequential keys, then remove them in same order: KMAP: time: 1.173, size: 0, buckets: 33554432, erased 20000000 CMAP: time: 1.651, size: 0, buckets: 33218751, erased 20000000 PMAP: time: 3.840, size: 0, buckets: 33554431, erased 20000000 FMAP: time: 1.722, size: 0, buckets: 33554432, erased 20000000 RMAP: time: 2.359, size: 0, buckets: 33554431, erased 20000000 HMAP: time: 0.849, size: 0, buckets: 33554432, erased 20000000 TMAP: time: 0.660, size: 0, buckets: 33554432, erased 20000000 UMAP: time: 2.138, size: 0, buckets: 31160981, erased 20000000 T3: Remove random keys: KMAP: time: 1.973, size: 0, buckets: 33554432, erased 23367671 CMAP: time: 2.020, size: 0, buckets: 33218751, erased 23367671 PMAP: time: 2.940, size: 0, buckets: 33554431, erased 23367671 FMAP: time: 1.147, size: 0, buckets: 33554432, erased 23367671 RMAP: time: 1.941, size: 0, buckets: 33554431, erased 23367671 HMAP: time: 1.135, size: 0, buckets: 33554432, erased 23367671 TMAP: time: 1.064, size: 0, buckets: 33554432, erased 23367671 UMAP: time: 5.632, size: 0, buckets: 31160981, erased 23367671 T4: Iterate random keys: KMAP: time: 0.748, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 CMAP: time: 0.627, size: 23367671, buckets: 33218751, repeats: 8, sum: 4465059465719680 PMAP: time: 0.680, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 FMAP: time: 0.735, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 RMAP: time: 0.464, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 HMAP: time: 0.719, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 TMAP: time: 0.662, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 UMAP: time: 6.168, size: 23367671, buckets: 31160981, repeats: 8, sum: 4465059465719680 T5: Lookup random keys: KMAP: time: 0.943, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 CMAP: time: 0.863, size: 23367671, buckets: 33218751, lookups: 34235332, found: 29040438 PMAP: time: 1.635, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 FMAP: time: 0.969, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 RMAP: time: 1.705, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 HMAP: time: 0.712, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 TMAP: time: 0.584, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 UMAP: time: 1.974, size: 23367671, buckets: 31160981, lookups: 34235332, found: 29040438

Yes, this is embarrassingly slow .so I solved your problem
the map member used for the lookups is a tsl::hopscotch_map (https://github.com/Tessil/hopscotchmap), which is a proper hash map. so it seems to be the latter, that the API is wrong, but from what I can tell it is only a wrongly named class. i don't see where the API makes guarantees about iteration order, which is where the implementation difference would be noticeable (beyond performance for lookup).

Any suggestions for resources to optimize for memory allocation/reallocation?
using an openaddressing hash table, such as abseil flat_hash_map or tessil/hopscotchmap
C++ Btree
Posts with mentions or reviews of C++ Btree.
We have used some of these posts to build our list of alternatives
and similar projects.
We haven't tracked posts mentioning C++ Btree yet.
Tracking mentions began in Dec 2020.
What are some alternatives?
When comparing Hopscotch map and C++ Btree you can also consider the following projects:
PEGTL  Parsing Expression Grammar Template Library
stxbtree  OBSOLETE, contained in https://github.com/tlx/tlx  STX B+ Tree C++ Template Classes 
sparsehashc11  Experimental C++11 version of sparsehash
FunctionalPlus  Functional Programming Library for C++. Write concise and readable C++ code.
sparsehash  C++ associative containers
Optional Argument in C++  Named Optional Arguments in C++17
Hashmaps  Various open addressing hashmap algorithms in C++
robinmap  C++ implementation of a fast hash map and hash set using robin hood hashing
flat_map  Header only associative linear container.
Hopscotch map vs PEGTL
C++ Btree vs stxbtree
Hopscotch map vs sparsehashc11
C++ Btree vs FunctionalPlus
Hopscotch map vs sparsehash
C++ Btree vs PEGTL
Hopscotch map vs Optional Argument in C++
C++ Btree vs Hashmaps
Hopscotch map vs Hashmaps
C++ Btree vs sparsehashc11
Hopscotch map vs robinmap
C++ Btree vs flat_map