ankerl::unordered_dense for C++17 HashMaps and HashSets

Why dense hash containers fit data-heavy C++ code

ankerl::unordered_dense targets a specific weakness in the conventional unordered container design: hash table storage can make iteration follow bucket and node structures rather than one contiguous sequence. The library places the map and set data in a std::vector, so iteration walks contiguous elements and the README documents this as insertion order. That design is aimed at applications that build collections, scan them repeatedly, or keep large sets of keys and values in memory. It is not a general-purpose replacement for every unordered container, because the README explicitly says the classes are almost drop-in replacements rather than exact substitutes.

The project provides four main container types. ankerl::unordered_dense::map and ankerl::unordered_dense::set target speed and dense storage. ankerl::unordered_dense::segmented_map and ankerl::unordered_dense::segmented_set trade some of that density for lower peak memory usage and stable references on insertion, although their iterators are not stable. The available ankerl::unordered_dense::pmr typedefs support polymorphic allocators, and a template parameter can replace std::vector with another compatible random-access container. These choices matter for codebases that care about allocator ownership, memory placement, or container layout rather than only API syntax.

Inside the vector and hash-index architecture

The README states that map iteration walks a std::vector in insertion order. The associated design documentation describes an index made from one 88-byte block per group of sixteen slots, with overflow counters that remove the need for tombstones. Based on that documented structure, lookup uses the hash index to locate a candidate while the actual key-value pair remains in contiguous vector storage. Insertion appends data to the vector and updates the index. Erasure leaves a gap and moves another element into that gap, which explains why deletion requires two lookups.

The result is a separation between dense element storage and a smaller indexing layer. It can improve iteration and memory locality, but it does not make the container a simple open-addressed table. The library also supports customizable storage, including boost::interprocess::vector or another compatible random-access container. That makes the implementation relevant to applications using interprocess memory. The documented trade-off is structural: data movement during erasure and vector growth can invalidate references and iterators. The README states that iterators and references are not stable on insert or erase, so callers must follow std::vector-like lifetime rules even when the map API otherwise resembles std::unordered_map.

Installing the header-only library with CMake

The simplest installation path is header-only. Copy include/ankerl/unordered_dense.h and include/ankerl/stl.h into the project while keeping them in the same directory, then include unordered_dense.h. The README says stl.h contains standard includes and is separated so a build using import std can skip it. Two other headers, include/ankerl/huge_page_allocator.h and include/ankerl/mapped_view.h, are optional and are needed only for huge pages or mapping a map read in place from a file.

For a system or project-local installation, clone the repository and create a build directory. These commands are taken from the README:

mkdir build && cd build
cmake ..
cmake --build . --target install

The README states that the default installation location is /usr/local. To avoid installing it system wide, use the documented prefix form:

mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH=${HOME}/unordered_dense_install ..
cmake --build . --target install

After installation, configure the consuming project with CMake. The package name and imported target are specified in the README:

find_package(unordered_dense CONFIG REQUIRED)
target_link_libraries(your_project_name unordered_dense::unordered_dense)

The README documents a header-only project rather than a mandatory compiled runtime dependency. The repository also contains meson.build, meson_options.txt, xmake.lua, tests, examples, and a requirements.txt listing meson and ninja, but those entries do not make the header-only installation path mandatory.

A first map use and what output to expect

The README example creates a map, inserts repeated words with operator[], and iterates over the result. The following is the documented first-use shape, without adding flags or configuration:

#include <ankerl/unordered_dense.h>

#include <iostream>
#include <string>

auto main() -> int {
    auto counts = ankerl::unordered_dense::map<std::string, int>();
    for (auto const* word : {"the", "quick", "brown", "fox", "the"}) {
        ++counts[word];
    }

    for (auto const& [word, count] : counts) {
        std::cout << count << ' ' << word << '\n';
    }
}

The first loop initializes missing entries through operator[] and increments the value for the repeated word "the". The second loop uses structured bindings. According to the README, iteration walks a std::vector in insertion order, so a reader should expect the entries to be visited in the order they were first inserted, with the final value for "the" equal to 2. The example does not print hashes, bucket counts, allocator behavior, or timing information, so it should not be treated as a performance test.

A caller should also treat references obtained from the map as temporary across operations. The README specifically warns that references are not stable on insert or erase. Code that stores a reference to a mapped value and then performs another insertion or deletion must account for that invalidation rule.

Performance claims and the cost of dense layout

The README reports that the dense layout makes iteration fast because the data is contiguous. Its benchmark section states 0.20 ns per element for iteration in the documented setup, with flat maps shown at 5.4x to 13x the cost and std::unordered_map at 112x in the cited comparison. It also states that builds and destruction with std::string keys were 2.1x to 2.6x faster than any flat map in that benchmark. These are repository-reported figures, not a claim about every machine or workload. The README identifies Ryzen 9 7950X, clang 22.1.8, one binary per map, and one million to two million entries as the stated benchmark environment.

The same section gives a counterweight. When results are sorted by find rather than iteration, unordered_dense is seventh of fourteen, and the README says integer find and churn cost 0.73 and 0.59 against boost::unordered_flat_map. The project documentation also explicitly calls out relatively slow deletion. Consequently, the design is most compelling when iteration and dense traversal are frequent. A workload dominated by deletion, pointer stability, or operations that repeatedly mutate existing references may get a better fit from a different container.

The benchmark files and design notes are useful when deciding whether to investigate further. The README points to doc/bench_readme.csv, doc/benchmarks.md, and scripts/ab/README.md, including the measurement harnesses and notes about cases that did not produce positive results. Those files can help distinguish a container that suits a measured workload from one that merely looks attractive in a microbenchmark.

Upgrade, maintenance, and reference-stability constraints

The repository is not archived, and the last push was on 2026-10-09. Recent releases include v5.3.2 on 2026-10-09, v5.3.1 on 2026-10-04, and v5.3.0 on 2026-10-03. This supports considering the current release line, but it does not by itself establish compatibility with a particular compiler, standard library, or application. The repository includes a CII Best Practices badge and workflow files, although the available documentation does not define their full contents or test coverage.

The README links to an upgrading guide for users moving from 4.x to 5.x. That guide reportedly covers renames and breaks in 5.0, including changes that are not compile errors. This matters because an upgrade should be reviewed as a source-compatibility and behavioral-compatibility task, not just as copying a newer header. The documentation also lists optional huge-page and mapped-view files, so enabling those features increases the files and configuration involved in an integration.

The MIT license permits use, modification, and redistribution under its terms, but license obligations still need to be checked against the project's LICENSE and the consumer's distribution process. This is an engineering note rather than legal advice. The main technical upgrade cost is validating reference invalidation, allocator configuration, included headers, and any build-system changes introduced between releases.

Choosing between map, set, and segmented containers

Use ankerl::unordered_dense::map when keys map to values and iteration over the full collection is important. Use ankerl::unordered_dense::set when membership and dense storage are the goals. The API is described as almost drop-in compatible with std::unordered_map and std::unordered_set, but the difference in const Key pairing and iterator stability means that code relying on exact standard-library reference semantics should be reviewed.

The segmented variants are the documented alternative within the same library. They provide lower peak memory usage and stable references on insertion, while explicitly not promising stable iterators. That distinction is important. An application that keeps a reference to an element can consider the segmented form when insertion is frequent, but it still cannot promise iterator survival. The plain dense containers are the more direct choice when the priority is contiguous iteration and lower memory usage for the normal representation.

Compared with std::unordered_map, unordered_dense keeps elements in a vector and uses a separate index. Compared with flat hash maps, the README reports similar speed territory for insertion and lookup, while emphasizing iteration and construction benefits. The library does not claim that it wins every operation. Benchmark the actual key type, mutation pattern, allocator, and iteration profile before selecting it.

Editorial conclusion

Adopt ankerl::unordered_dense when the workload iterates stored elements frequently and can accept invalidation of iterators and references during insertion or erasure. Do not choose it when stable element references are mandatory or deletion performance is the primary concern. Verify compatibility with your C++ standard library, allocator requirements, reference lifetime assumptions, and the exact release you pin before integrating the headers.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. martinus/unordered_dense on GitHub
4. README
5. Releases