unordered_dense
A fast, densely stored C++17+ hashmap and hashset using robin-hood backward shift deletion, offering near-drop-in replacements for std::unordered_map/set.
What is unordered_dense?
ankerl::unordered_dense is a C++17+ library providing fast, densely stored hashmap and hashset containers. It serves as a high-performance alternative to `std::unordered_map` and `std::unordered_set` by storing elements contiguously in a vector, significantly speeding up iterations and lookups while trading off some iterator stability guarantees.
C++ developers working on performance-sensitive applications, such as game engines, scientific computing, or high-frequency trading systems, who need faster associative containers than the STL provides.
Developers choose ankerl::unordered_dense for its exceptional speed—often matching or exceeding libraries like Abseil's flat_hash_map—and its low memory footprint, all while maintaining a familiar API and supporting modern C++ features like custom allocators and heterogeneous lookups.
Overview
A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
Use Cases
Best For
- Replacing std::unordered_map/set in performance-critical codebases
- Applications requiring fast iteration over hash table elements
- Scenarios where cache locality and data contiguity are important
- Projects needing lower memory usage than standard hash containers
- Implementing custom allocators or using polymorphic allocators (PMR)
- Situations where iterator stability is less critical than raw speed
Not Ideal For
- Codebases requiring stable iterators or references across insertions and erasures
- Applications where deletion operations are frequent and performance-critical
- Projects tightly coupled to the exact API guarantees of std::unordered_map (e.g., const Key in std::pair)
- Embedded systems with severe memory fragmentation concerns, as segmented variants trade contiguity for lower peaks
Pros & Cons
Pros
Benchmarks show it consistently outperforms std::unordered_map, with iteration speeds matching a std::vector due to contiguous storage, making it ideal for data-intensive applications.
Elements are stored in a std::vector, drastically reducing cache misses during lookups and iterations, which is highlighted as a key design advantage over standard hash tables.
Supports high-quality avalanching hashes via wyhash, heterogeneous lookups with is_transparent, and customizable container types for integration with systems like boost::interprocess.
Fully compatible with C++17+, includes polymorphic allocator (PMR) typedefs, and offers C++20 module support for cleaner compilation in modern codebases.
Cons
The README admits deletions are relatively slow due to requiring two lookups—one to find the element and another to update the moved element—which can bottleneck certain workloads.
Iterators and references are invalidated on insert or erase, breaking code that relies on stable pointers, a trade-off explicitly noted in the design philosophy.
Does not provide const Key in std::pair<Key, Value>, which can cause issues in template-heavy code expecting standard-compliant types, as mentioned in the overview.
Features like custom bucket types or segmented variants require deeper understanding of internal mechanics, adding setup overhead compared to simpler drop-in libraries.
Frequently Asked Questions
Related Projects
Parallel HashmapA family of header-only, very fast and memory-friendly hashmap and btree containers.
CRoaringRoaring bitmaps in C (and C++), with SIMD (AVX2, AVX-512 and NEON) optimizations: used by Apache Doris, ClickHouse, Alibaba Tair, Redpanda, YDB and StarRocks
robin-hood-hashingFast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
robin-mapC++ implementation of a fast hash map and hash set using robin hood hashing
Found a gem we're missing?
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.