std::flat_map is just two vectors

C++23 added std::flat_map (P0429, together with flat_set, flat_multimap, and flat_multiset). It is a container adaptor over two sequences: a sorted vector of keys and a parallel vector of values, kept in lockstep. Lookup is a binary search over contiguous keys. There is no tree and no per-node allocation, and the API is open about it: keys() and values() hand you the underlying containers, and construction can adopt pre-sorted data without doing any work.

That design is the thing to understand before you reach for the container. “A faster std::map” is true enough, but it hides where the speed comes from and what you pay for it.

The demo shows the whole mental model in three prints. The keys() observer returns ["dns", "http", "https", "ssh"], sorted and contiguous, exactly what binary search wants. values() is the parallel array. The last construction is the zero-work path: std::sorted_unique plus two moved-in vectors builds the map by taking ownership of your containers as they are. If your data arrives sorted (from a file, a database, or a build step) you pay nothing at all. The example also runs on clang with libc++; both mainstream standard libraries ship it.

What the two vectors buy you

• Cache-friendly lookups. A std::map lookup chases pointers through nodes scattered across the heap; a flat_map lookup walks a contiguous array the prefetcher understands. For lookup-heavy workloads this is routinely a large win.
• Memory. No per-node allocation. A flat_map stores two vectors’ worth of data and nothing else, where a red-black tree carries three pointers and a colour bit on every element.
• Free bulk construction via sorted_unique, and symmetric extract() to take the vectors back out.

What they cost you

Each of these is a real change in contract from std::map:

• Insertion into a populated map is O(n). Everything after the insertion point shifts, in both vectors. Build once and look up often, or batch your mutations.
• Iterators and references are invalidated by insert and erase. A std::map keeps them valid across mutation; flat_map does not, so code that holds references into the map does not port.
• Exception behavior is unusual. If a mutating operation throws, the standard guarantees the invariants (sorted keys, equal lengths) are restored, in some cases by clearing the container. A throwing mutation can leave you with an empty map.

One comparison worth getting right: flat_map competes with std::map, not std::unordered_map. A good hash table still wins pure point lookups on large data. What flat_map adds over a tree is ordered iteration and a much smaller memory footprint at similar lookup cost.

If your data is mostly static and read often (configuration, symbol tables, routing tables), the two-vector layout is the one you would have hand-rolled anyway. C++23 puts it in the standard library.

Sources: P0429R9 “A Standard flat_map” · cppreference: std::flat_map.