std::flat_map and std::flat_set (C++23)
C++23 sorted contiguous-memory container adapters with O(log n) binary search and cache-friendly layout — no pointer chasing through tree nodes.
std::flat_map / std::flat_setsince C++23Sorted associative container adapters backed by contiguous-memory sequences (defaulting to std::vector) that replace tree-based nodes with sorted arrays, trading O(n) insert/erase for dramatically better cache locality on lookup and iteration.
Overview
std::flat_map and std::flat_set are container adapters introduced in C++23. They wrap one or more sequence containers and expose a sorted-associative interface identical to std::map and std::set. The core distinction is memory layout: tree-based containers allocate each node on the heap and link them via pointers; flat containers store all data contiguously.
A binary search over 10,000 contiguous integers touches roughly 14 cache lines in sequence. A red-black tree traversal of the same depth touches 14 different cache lines from 14 independent heap allocations scattered across memory. For read-heavy workloads this difference is significant — typically 3–10× faster lookup on modern hardware.
flat_map stores keys and mapped values in two separate vectors, not as vector<pair<Key, T>>. This split layout means a key-only binary search never loads mapped values into cache, and enables efficient operations over keys in isolation.
flat_set stores elements in a single sorted vector.
Duplicate-key variants flat_multimap and flat_multiset are also provided.
#include <flat_map> // flat_map, flat_multimap (C++23)
#include <flat_set> // flat_set, flat_multiset (C++23)Syntax
// flat_map — five template parameters
template<
class Key,
class T,
class Compare = std::less<Key>,
class KeyContainer = std::vector<Key>,
class MappedContainer = std::vector<T>
>
class flat_map; // C++23
// flat_set — three template parameters
template<
class Key,
class Compare = std::less<Key>,
class KeyContainer = std::vector<Key>
>
class flat_set; // C++23Any random-access sequence container satisfying begin, end, size, empty, push_back, and emplace_back is a valid underlying container. std::deque works; std::list does not.
Examples
Basic usage
#include <flat_map>
#include <flat_set>
#include <print> // C++23
std::flat_map<std::string, int> scores;
scores["Alice"] = 95; // operator[] inserts default value on miss, then assigns
scores.emplace("Bob", 87); // O(n) — maintains sorted order
if (auto it = scores.find("Alice"); it != scores.end()) // C++17 init-if
std::println("{} scored {}", it->first, it->second); // C++23
scores.erase("Bob");
bool present = scores.contains("Alice"); // C++20 member
for (const auto& [name, score] : scores) // C++17 structured bindings
std::println("{}: {}", name, score); // guaranteed sorted output
// flat_set usage mirrors std::set
std::flat_set<int> primes{2, 3, 5, 7, 11, 13};
primes.insert(17);
primes.erase(2);
auto [lo, hi] = primes.equal_range(5); // iterator pair bracketing 5Bulk construction — avoid O(n²)
Inserting into a flat_map one element at a time requires shifting up to n elements per insertion to maintain sorted order. For n insertions this is O(n²). The correct pattern for large datasets is to collect unsorted and construct once:
#include <flat_map>
#include <vector>
#include <algorithm>
std::vector<std::pair<int, double>> raw;
raw.reserve(50'000);
for (const auto& rec : data_source)
raw.emplace_back(rec.id, rec.value);
// Range constructor: sorts internally — O(n log n) total
std::flat_map<int, double> lookup(raw.begin(), raw.end());
// If data is already sorted and contains no duplicate keys,
// use sorted_unique to skip the sort pass — O(n) construction.
// Precondition violation (unsorted or duplicate data) is undefined behavior.
std::sort(raw.begin(), raw.end());
raw.erase(std::unique(raw.begin(), raw.end(),
[](const auto& a, const auto& b){ return a.first == b.first; }),
raw.end());
std::flat_map<int, double> fast(std::sorted_unique,
raw.begin(), raw.end());Accessing underlying containers
flat_map exposes its internal vectors, which is not possible with std::map:
std::flat_map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};
const auto& ks = m.keys(); // const vector<int>& — sorted keys
const auto& vs = m.values(); // const vector<string>& — mapped values
// Invariant: ks[i] corresponds to vs[i]
// Binary search only over keys — values stay cold in cache
auto pos = std::ranges::lower_bound(ks, 2); // C++20
if (pos != ks.end() && *pos == 2)
std::println("{}", vs[std::distance(ks.begin(), pos)]);extract and replace for bulk modification
When you must perform multiple mutations, avoid repeated O(n) shifts by extracting the containers, modifying them freely, and replacing:
std::flat_map<int, int> m{{1, 10}, {2, 20}, {3, 30}};
// extract() returns a struct { KeyContainer keys; MappedContainer values; }
// The map is left empty after extraction.
auto c = m.extract();
// Modify raw vectors however you like — O(1) amortized appends
c.keys.push_back(4);
c.values.push_back(40);
c.keys.push_back(5);
c.values.push_back(50);
// replace() requires the containers to already satisfy the sorted-unique invariant.
// They do here since we only appended larger keys.
m.replace(std::move(c.keys), std::move(c.values));
// m now contains {1,10}, {2,20}, {3,30}, {4,40}, {5,50}Custom containers and PMR allocation
#include <flat_map>
#include <memory_resource> // C++17
using PmrFlatMap = std::flat_map<
int, std::string,
std::less<int>,
std::pmr::vector<int>, // C++17 PMR
std::pmr::vector<std::string>
>;
alignas(std::max_align_t) std::byte buf[8192];
std::pmr::monotonic_buffer_resource arena{buf, sizeof(buf)};
PmrFlatMap m{std::pmr::polymorphic_allocator<>(&arena)};
m.emplace(1, "one");
m.emplace(2, "two");
// All allocations served from the stack buffer — zero heap activityflat_multimap — duplicate keys
#include <flat_map>
std::flat_multimap<int, std::string> mm{
{1, "alpha"}, {1, "beta"}, {2, "gamma"}
};
// For pre-sorted data with duplicates, use sorted_equivalent (not sorted_unique)
std::flat_multimap<int, std::string> mm2(std::sorted_equivalent,
mm.begin(), mm.end());
auto [lo, hi] = mm.equal_range(1);
for (auto it = lo; it != hi; ++it)
std::println("{}", it->second); // "alpha", "beta"Best Practices
Build then freeze. flat_map is purpose-built for containers that are populated upfront and queried repeatedly — config tables, reverse-lookup indexes, precomputed caches. If your access pattern is predominantly read after an initial bulk load, the lookup speedup over std::map is consistent and significant.
Use sorted_unique when data is already sorted. Queries against sorted data sources (databases, flat files, pre-sorted ranges) can skip the internal sort pass entirely. Always validate the precondition in debug builds with std::is_sorted and std::adjacent_find — violations are undefined behavior.
Use extract/replace for batch mutations. When you need to add or remove multiple elements, extract the containers, modify them however you like, sort them, and replace. This avoids n×O(n) shifts and is O(n log n) total regardless of how many elements you modify.
Prefer find or contains over operator[] for read-only access. operator[] inserts a default-constructed value for missing keys, which is O(n) due to the insertion shift. For lookups where you do not want insertion, use find() or contains() (C++20).
Common Pitfalls
Incremental insertion is O(n²). Each single-element insert shifts all elements with larger keys. A tight loop inserting n items runs in O(n²) time. Collect into a vector and construct from range instead.
All iterators are invalidated on any mutation. Unlike std::map, which provides stable iterators across insertions and erasures elsewhere in the container, any insert or erase into a flat_map or flat_set invalidates all existing iterators, pointers, and references — including pointers into the underlying key and value vectors obtained via keys() / values().
sorted_unique with unsorted or duplicate data is undefined behavior. The standard does not require a diagnostic. The behavior is silent data corruption, not an exception.
sorted_equivalent for multi-variants, not sorted_unique. flat_multimap and flat_multiset accept the std::sorted_equivalent tag. Passing std::sorted_unique to a multi-container when duplicates are present is undefined behavior.
Reallocation silently invalidates raw pointers. Pointers obtained by keys().data() or values().data() are invalidated whenever an insertion triggers reallocation. Store indices, not pointers, if you need stable references across mutations.
flat_map vs std::map
| Property | std::map | std::flat_map (C++23) |
|---|---|---|
| Memory layout | Heap nodes, pointer-linked | Two contiguous vectors |
| Lookup | O(log n), ~10–20 cache misses | O(log n), ~1–3 cache misses |
| Insert (single element) | O(log n), no shift | O(n) — shifts tail |
| Erase (single element) | O(log n), no shift | O(n) — shifts tail |
| Bulk construction | O(n log n) | O(n log n); O(n) with sorted_unique |
| Iteration | Tree traversal (poor locality) | Sequential scan (excellent) |
| Iterator stability | Stable on insert/erase | Invalidated on any mutation |
| Memory per element | ~48 bytes (key + val + 3 ptrs) | Size of key + size of val |
| Best use case | Frequent interleaved insert+lookup | Build once, query many |
std::flat_set and std::flat_multimap
std::flat_set is the unordered sibling of std::flat_map — it stores a single sorted sequence of unique keys with no associated mapped values. std::flat_multimap extends flat_map to allow multiple values per key, maintaining the contiguous-memory layout while permitting duplicate keys.
#include <flat_set> // C++23
#include <flat_map> // C++23
// flat_set: sorted unique keys, single contiguous vector
std::flat_set<int> primes{11, 7, 2, 13, 3, 5}; // C++23
// Stored as: [2, 3, 5, 7, 11, 13] — sorted on construction
// flat_multimap: multiple values per key, still contiguous
std::flat_multimap<std::string, int> scores; // C++23
scores.emplace("Alice", 95);
scores.emplace("Alice", 88); // second entry for same key is allowed
scores.emplace("Bob", 77);
// If data is already sorted (with possible duplicates),
// use std::sorted_equivalent to skip the sort pass — O(n)
std::vector<std::pair<std::string, int>> sorted_data{
{"Alice", 88}, {"Alice", 95}, {"Bob", 77}
};
std::flat_multimap<std::string, int> fast(
std::sorted_equivalent, // C++23 hint tag
sorted_data.begin(), sorted_data.end()
);
// flat_set with sorted_unique hint for already-sorted unique data
std::vector<int> sorted_primes{2, 3, 5, 7, 11, 13};
std::flat_set<int> fs(std::sorted_unique, // C++23 hint tag
sorted_primes.begin(), sorted_primes.end());std::sorted_unique tells the constructor the input is already sorted and free of duplicate keys, skipping the O(n log n) sort pass entirely. Passing it with unsorted or duplicate data is undefined behavior; validate with std::is_sorted in debug builds.
Custom Underlying Container
The KeyContainer and MappedContainer template parameters accept any random-access sequence container — swapping in std::deque or std::pmr::vector changes allocation behavior without altering the associative interface. std::deque provides O(1) push_front and avoids large contiguous reallocations, but its segmented layout yields worse cache locality than a plain std::vector.
#include <flat_map>
#include <deque>
#include <memory_resource> // C++17
// deque-backed flat_map: O(1) push_front, but segmented memory
std::flat_map<int, std::string,
std::less<int>,
std::deque<int>, // C++23
std::deque<std::string> // C++23
> deque_map;
deque_map.emplace(3, "three");
deque_map.emplace(1, "one"); // O(n) shift applies regardless of backing store
deque_map.emplace(2, "two");PMR (polymorphic memory resource) vectors enable arena allocation so every key and value is served from a single pre-allocated buffer with zero heap fragmentation.
// PMR flat_map: all allocations come from a single arena buffer
using PmrFlatMap = std::flat_map<
int, std::string,
std::less<int>,
std::pmr::vector<int>, // C++23 + C++17 PMR
std::pmr::vector<std::string> // C++23 + C++17 PMR
>;
alignas(std::max_align_t) std::byte buf[4096];
std::pmr::monotonic_buffer_resource arena{buf, sizeof(buf)};
PmrFlatMap m{std::pmr::polymorphic_allocator<>(&arena)}; // C++23
m.emplace(1, "alpha");
m.emplace(2, "beta");
// Zero heap allocation — both key and value vectors grow inside buf[]Batch Insertion and sorted_unique Hint
Inserting elements one by one into a flat_map is O(n) per insertion because each insertion shifts all subsequent elements to maintain sorted order — giving O(n²) total for n insertions. The efficient pattern is to accumulate unsorted data externally, then construct the flat_map once, paying O(n log n) for the internal sort instead.
#include <flat_map>
#include <vector>
#include <algorithm>
#include <ranges> // C++20
// Path 1: unsorted construction — sorts internally, O(n log n)
std::vector<std::pair<int, double>> raw{
{5, 5.0}, {1, 1.0}, {3, 3.0}, {2, 2.0}, {4, 4.0}
};
std::flat_map<int, double> m1(raw.begin(), raw.end()); // C++23
// Path 2: sorted_unique — skips sort, O(n) construction
std::sort(raw.begin(), raw.end());
raw.erase(std::unique(raw.begin(), raw.end(),
[](const auto& a, const auto& b){ return a.first == b.first; }),
raw.end());
std::flat_map<int, double> m2(std::sorted_unique, // C++23
raw.begin(), raw.end());insert_range appends an entire sorted range in one call, which is still O(n + m) for n existing elements and m new ones but avoids n individual O(n) shifts.
// insert_range: append a pre-sorted range — C++23
std::flat_map<int, double> m3;
m3.reserve(100);
std::vector<std::pair<int, double>> extra{{10, 10.0}, {20, 20.0}};
m3.insert_range(extra); // C++23 — merges and re-sorts oncePrefer constructing from a full dataset over calling insert in a loop whenever possible; the savings grow quadratically with the number of inserted elements.
Transparent Comparators with flat_map
std::less<> — the void specialization — enables heterogeneous lookup, allowing find, contains, lower_bound, and other key-based operations to accept any comparable type without constructing the stored key type. This is identical in interface to the same feature on std::map, but matters more for flat_map because unnecessary std::string construction would heap-allocate even for a purely read-only lookup.
#include <flat_map>
#include <string>
#include <string_view>
struct Value { int score; std::string label; };
// std::less<> (void) enables heterogeneous lookup — C++23
std::flat_map<std::string, Value, std::less<>> m; // C++23
m.emplace("Alice", Value{95, "excellent"});
m.emplace("Bob", Value{77, "good"});
// find() with string_view — no std::string allocation
std::string_view key = "Alice";
auto it = m.find(key); // compiles only with std::less<>
if (it != m.end())
std::println("{}", it->second.score);
// Without std::less<>, this would fail to compile:
// std::flat_map<std::string, Value> m2; // uses std::less<std::string>
// m2.find(key); // error: no match for find(string_view)The same technique applies to std::map<std::string, V, std::less<>> — both tree-based and flat containers benefit equally from transparent comparators when keys are string-like types.
flat_map vs map vs unordered_map: When to Use Each
std::flat_map wins for read-heavy, build-once maps under roughly 1 000–10 000 elements where cache locality dominates; std::unordered_map wins for large maps with many interleaved inserts; std::map wins when you need ordered iteration alongside frequent single-element mutations with stable iterators.
| Property | std::map | std::unordered_map | std::flat_map (C++23) |
|---|---|---|---|
find complexity | O(log n) | O(1) average | O(log n) |
insert complexity | O(log n) | O(1) amortized | O(n) — shifts tail |
| Iteration order | Sorted | Unspecified | Sorted |
| Cache-friendly lookup | No — pointer chasing | No — bucket indirection | Yes — contiguous scan |
| Cache-friendly iteration | No | No | Yes |
| Per-element allocations | Yes (one node each) | Yes (bucket array + nodes) | No (two vectors) |
| Iterator stability | Stable on insert/erase | Rehash invalidates all | Any mutation invalidates all |
| Best for | Ordered data + frequent inserts | Large maps, many inserts | Build-once, query-many; small maps |
For request-scoped lookup tables built from config files or query results (typically under a few thousand entries), flat_map consistently outperforms both alternatives on lookup benchmarks because binary search over contiguous memory fits in L1/L2 cache.
Using flat_map with PMR Allocators
std::pmr::flat_map<K, V> is an alias for flat_map backed by std::pmr::vector, allowing every key and value allocation to be served from a std::pmr::polymorphic_allocator — making it ideal for request-scoped or parse-time data structures that must not touch the global heap. A stack-allocated std::pmr::monotonic_buffer_resource provides O(1) bump-pointer allocation with no deallocation overhead.
#include <flat_map>
#include <memory_resource> // C++17
// Stack-allocated arena: 8 KiB on the stack, zero heap activity
alignas(std::max_align_t) std::byte stack_buf[8192];
std::pmr::monotonic_buffer_resource arena{
stack_buf, sizeof(stack_buf),
std::pmr::null_memory_resource() // throw on overflow instead of falling back
};
// pmr::flat_map: std::flat_map with pmr::vector backing — C++23
std::pmr::flat_map<int, std::string> request_map{
std::pmr::polymorphic_allocator<>(&arena) // C++23
};
// Build the map during request parsing
request_map.emplace(1, "token_one");
request_map.emplace(2, "token_two");
request_map.emplace(3, "token_three");
// All key vector and value vector storage came from stack_buf —
// the global allocator was never called.
auto it = request_map.find(2);
if (it != request_map.end())
std::println("Found: {}", it->second);
// arena destroyed at end of scope — all memory reclaimed in O(1)When the stack buffer is exhausted, null_memory_resource throws std::bad_alloc rather than silently falling back to the heap, keeping allocation behavior explicit and auditable. For production use, size the buffer conservatively and validate in integration tests.
See Also
std::map— tree-based, stable iterators, O(log n) insert/erasestd::unordered_map— O(1) average lookup, hash-based, unsorted (C++11)std::vector+std::lower_bound— manual sorted-vector lookup without adapter overheadstd::ranges::lower_bound— binary search over any sorted range (C++20)std::pmr::vector— polymorphic memory resource sequence container (C++17)