When does C++23 std::flat_map beat std::map for an order book's price levels, and what do you give up by switching?
answer
- an adaptor over two sequences
- binary search over contiguous keys
- linear single-element insert
- no reference stability, no nodes
- proxy reference type
basics
~20 sstd::flat_map keeps sorted keys and values in two contiguous containers, so lookup and iteration are cache-friendly and per-element overhead is small. Single-element insert and erase are linear, insertions can invalidate iterators and references, and there are no node handles.
solid answer
~40 sC++23's `std::flat_map<Key, T, Compare, KeyContainer, MappedContainer>` is a container adaptor: by default two `std::vector`s, keys sorted by `Compare` and values at matching offsets. Lookup is still a logarithmic binary search, but over contiguous memory, and iteration walks two arrays, so a read-heavy book of a few hundred price levels typically traverses faster than `std::map`'s per-node allocations would allow. The cost is in writes: the standard makes single-element insert and erase **linear**, as later elements shift; it exempts `flat_map` from the associative containers' iterator-invalidation rules, so pointers and references may dangle after any insert; it has no node handles; and `reference` is the proxy `pair<const Key&, T&>`. Bulk building is cheap with `sorted_unique` or range insert. Order the levels so that churn happens near the end.
code
cpp · 19 lines#include <flat_map>
#include <iostream>
#include <vector>
int main() {
// price levels for one side of a small book, kept in two contiguous vectors
std::vector<int> prices{10098, 10099, 10100};
std::vector<int> qty{4, 7, 1};
std::flat_map<int, int> bids(std::sorted_unique, std::move(prices), std::move(qty));
bids[10097] = 2; // new lowest key: every element shifts right
auto it = bids.lower_bound(10099); // binary search over contiguous keys
std::cout << it->first << " -> " << it->second << '\n';
const auto& keys = bids.keys(); // the sorted key vector itself
std::cout << "keys:";
for (int k : keys) std::cout << ' ' << k;
std::cout << "\nsize " << bids.size() << '\n';
}go deeper
Know that std::flat_map, new in C++23, keeps sorted keys in contiguous storage instead of tree nodes.
Explain the two-container layout, the binary-search lookup, linear single-element insert and the proxy reference type.
Choose between std::map and std::flat_map from the read-write profile, place churn at the end of the array, and avoid holding references across updates.
Weigh adopting C++23 flat containers across a codebase against toolchain support and the review burden of their weaker invalidation guarantees.
## What std::flat_map is C++23 added **`std::flat_map`**, `std::flat_multimap`, `std::flat_set` and `std::flat_multiset` (headers `<flat_map>` and `<flat_set>`, feature-test macro `__cpp_lib_flat_map`). The standard calls `flat_map` a **container adaptor** that provides an associative-container interface with unique keys: ```cpp template<class Key, class T, class Compare = less<Key>, class KeyContainer = vector<Key>, class MappedContainer = vector<T>> class flat_map; ``` It maintains three invariants: the two containers hold the same number of elements, the keys are sorted by the comparator, and the value at offset `off` belongs to the key at offset `off`. `value_type` is `pair<Key, T>` (no `const` on the key), while `reference` is the **proxy** `pair<const key_type&, mapped_type&>`, built on the fly from the two arrays. Iterators are random-access. Any sequence container with random-access iterators (whose `size` and `max_size` do not throw) can be used underneath; the standard names `vector` and `deque`. ## Where it wins - **Lookup**: `find`, `lower_bound` and friends are still O(log n) binary searches, but they touch a compact array of keys instead of chasing pointers between separately allocated tree nodes. - **Iteration**: walking all levels is a linear scan of two arrays, which is what depth snapshots and book publishing do constantly. - **Memory**: there is no per-element node with parent, child and color fields, and no allocation per insert. - **Bulk construction**: constructors taking `sorted_unique` adopt already-sorted containers as they are; range `insert` appends, sorts the new elements and merges them, which the standard specifies as N + M log M rather than M separate linear insertions. ## What it costs | Property | `std::map` | `std::flat_map` (C++23) | |---|---|---| | Lookup | O(log n), node hops | O(log n), contiguous | | Single insert or erase | O(log n) | **linear** (elements shift) | | Iterator, pointer and reference stability | only erased elements invalidated | **not guaranteed** after modification | | Node handles (`extract`, `merge`) | yes | **no** | | Allocator-aware container | yes | no (the underlying containers carry allocators) | | `reference` type | `pair<const Key, T>&` | proxy `pair<const Key&, T&>` | Other rules worth knowing: 1. Passing `sorted_unique` with data that is not sorted, or has duplicates, is **undefined behaviour**; it is a promise, not a request. 2. If a member function exits with an exception, the invariants are restored, which, as the standard notes, can mean the `flat_map` ends up **empty**. 3. `keys()` and `values()` return const references to the underlying containers; `std::move(fm).extract()` hands both containers back and `replace` installs new ones. ## The proxy reference trap Because dereferencing yields a temporary `pair<const Key&, T&>`, `for (auto& [price, qty] : fm)` does not compile: a non-const lvalue reference cannot bind to that temporary, and Apple clang 21 reports `non-const lvalue reference to type '_If<...>' cannot bind to a temporary of type '_If<...>'`. Use `auto&&` or plain `auto`; with plain `auto` the pair is copied, but its `second` member is still a `T&` into the map, so assignments through it **do** modify the stored value, unlike plain `auto` over a `std::map`. ## Judging the order book A price ladder for one instrument typically holds a few dozen to a few hundred live levels. Reads dominate (best price, depth, snapshots), and updates mostly hit existing levels, changing quantity without inserting. That profile favours `std::flat_map`. Two design choices keep its weakness, shifting on insert, small: - **Put churn at the end.** New levels appear mostly around the best price. For bids stored ascending, the best bid is the last element, so inserts there shift only a few elements; storing bids with `std::greater<>` would put every new best level at the front and shift the whole array. - **Do not hold pointers** to quantities across updates; hold prices and look them up again. - **Reserve the underlying vectors** when building from a snapshot: extract the containers with `std::move(fm).extract()`, call `reserve` on each, and `replace` them, or build the vectors first and adopt them with `sorted_unique`. `std::map` remains the better choice when the set of keys churns heavily across the whole range, when code depends on stable references or node handles, or when elements are expensive to move. Measure with the book's real update stream before switching; the asymptotics alone do not decide it.
- Why does for (auto& [k, v] : fm) fail to compile for a std::flat_map, and what should you write?Dereferencing a `flat_map` iterator yields a prvalue proxy `pair<const Key&, T&>`, and a non-const lvalue reference cannot bind to a temporary. Write `for (auto&& [k, v] : fm)` or `for (const auto& [k, v] : fm)`. Even plain `auto` lets you modify values, because the copied proxy still holds a `T&` into the map.
- How do you build a large std::flat_map efficiently from unsorted input?Avoid inserting one element at a time, which shifts elements on every call. Collect keys and values, then use range `insert`, which appends, sorts the new elements and merges them in N + M log M. If you sort and deduplicate the vectors yourself, construct with `std::sorted_unique` to adopt them without any reordering.
- std::flat_map lookups are O(1) because the storage is contiguous
- Inserting into std::flat_map is logarithmic, just like std::map
- Pointers into a std::flat_map stay valid across insertions
- std::flat_map stores one vector of std::pair<const Key, T>
- std::sorted_unique sorts the input for you
Assumes C++23, which added std::flat_map, flat_multimap, flat_set and flat_multiset; earlier standards need a third-party flat container.