C++23 introduced std::flat_map, a container that replaces the red-black tree backing std::map with two sorted vectors. The result is simpler, uses less memory, and outperforms std::map in most read-heavy workloads. The tradeoff is that mutations become expensive. Daniel Lemire benchmarked the new container and found that for many practical use cases, the flat map is the better choice.
Two Arrays and a Binary Search
A flat map stores keys in one sorted vector and values in a parallel vector. A lookup performs a binary search over the keys array. This is the same algorithmic complexity as std::map, but the memory layout is fundamentally different. A red-black tree scatters nodes across the heap, each node carrying pointer overhead and breaking cache locality. A flat map keeps everything contiguous. A keys array of 64-bit integers uses exactly 8 bytes per entry with no additional overhead.
Continuity matters for modern hardware. A binary search over a contiguous array benefits from prefetching and cache lines that load multiple comparisons at once. A tree traversal following pointers from node to node does not. The difference shows up clearly in benchmarks, especially as the map grows large enough that the tree's pointer-chasing pattern starts missing L1 and L2 caches.
The container requires a recent standard library. GCC 15's libstdc++ includes std::flat_map, as does LLVM's libc++ starting with LLVM 20. Apple's clang 17 also provides it. The standard includes std::flat_set and other variants, but the map is the most practically significant addition.
Serialization Comes for Free
Because the data lives in two contiguous arrays, serializing a flat map to disk or transmitting it over a network requires two memcpy or write calls. The keys vector and the values vector each map directly to a byte range. Deserialization works the same way: read the two arrays, then construct the flat map with the std::sorted_unique tag, which tells the container that the incoming keys are already sorted and distinct.
This property matters for applications that load large lookup tables at startup. A database index, a configuration cache, or a compiled symbol table can be serialized as two flat arrays and loaded without parsing or rebuilding a tree structure. The construction is effectively instantaneous because it skips the sorting step entirely.
Lemire's example demonstrates this with uint64_t keys and a simple struct value. The keys vector is 8 bytes per entry. The values vector is 16 bytes per entry for a struct containing two doubles. The total memory footprint is exactly what you would calculate from the types, with zero overhead for tree nodes, pointers, or color bits.
Where the Flat Map Wins and Where It Loses
Random insertions into an initially empty flat map follow a quadratic growth curve. Each insertion shifts elements in the sorted keys vector to make room. For small maps, up to around a thousand elements, the flat map is competitive with or faster than std::map because the contiguous memory access pattern outweighs the shifting cost. Beyond that size, the quadratic behavior dominates and performance degrades badly.
Sequential insertions, where keys arrive in increasing order, tell a different story. The flat map appends each new key at the end of the vector with no shifting. Performance is dramatically better than std::map in this case, because the flat map avoids both the tree's pointer-chasing and the cost of rebalancing.
Bulk insertion resolves the random-insertion problem. The insert_range method takes a batch of new pairs, sorts the batch, and merges it with the existing arrays in a single pass. This is far more efficient than inserting elements one at a time. Construction from a range of random key-value pairs works the same way. Building a flat map from unsorted data in bulk is significantly faster than building a std::map from the same data.
Lookups are where the flat map consistently wins for large containers. The binary search over contiguous memory is faster than the tree traversal, and the difference grows with map size. Lemire's benchmarks on an Intel Xeon Gold 6548N with GCC 16.1 at -O3 show that random lookups in a large flat map are substantially faster than in a std::map, and the advantage comes largely from reduced memory usage and better cache behavior.
The Practical Calculus
The decision between std::flat_map and std::map comes down to workload. If you build a map once and read from it heavily, the flat map is the clear choice. If you need frequent random insertions and deletions on a large map, std::map remains better. The flat map also works well when keys arrive in sorted order or when you can batch your writes.
Serialization is an underappreciated advantage. Applications that persist lookup tables or share them between processes benefit from the trivial serialization format. A std::map requires walking the tree and reconstructing node relationships. A flat map requires writing two arrays.
The irony Lemire notes is worth repeating. std::flat_map replaces a textbook data structure, the red-black tree, with what amounts to two sorted vectors and a binary search. The simpler structure wins on performance in most practical scenarios. Cache locality, memory overhead, and prefetch-friendly access patterns matter more than the theoretical elegance of balanced trees.
For developers working with C++23, std::flat_map is worth evaluating as the default choice for read-heavy lookup tables. The cases where std::map is clearly better are narrow enough that the flat map should be the starting point rather than the alternative.