Our great sponsors
-
unordered_dense
A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
-
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.
-
robin-hood-hashing
Discontinued Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
-
If you don't need all the guarantees provided by std::unordered_map (pointer stability is usually the big one), you can go a /lot/ faster with a map that uses open addressing.
Some of my favorite alternative hash map implementations are ska::flat_hash_map and ska::bytell_hash_map from https://github.com/skarupke/flat_hash_map. They're fast, and the single header implementation makes them easy to add to a project. For my use cases they generally offer similar performance to abseil and folly F14.
Don't be fooled by the fact that they haven't been updated in ~5 years. I've been using them for nearly that long and have yet to find any bugs.
https://github.com/martinus/unordered_dense
Check this one out, it's a successor to this idea. Boost also introduced a very performant flat_hash_map in 1.81
For anyone in a situation where a set/map (or unordered versions) is in a hot part of the code, I'd also highly recommend Robin Hood: https://github.com/martinus/robin-hood-hashing
It made a huge difference in one of the programs I was running.
XOR is a bad way to do it, but there are ones that work much better that are described in answers to that post, and it's what other languages use in similar situations (e.g. tuples in Python and C#):
https://github.com/python/cpython/blob/71db5dbcd714b2e1297c4...