std::flat_map and std::flat_set (C++23)

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++23

Any 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 5

Bulk 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 activity

flat_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

See Also

• std::map — tree-based, stable iterators, O(log n) insert/erase
• std::unordered_map — O(1) average lookup, hash-based, unsorted (C++11)
• std::vector + std::lower_bound — manual sorted-vector lookup without adapter overhead
• std::ranges::lower_bound — binary search over any sorted range (C++20)
• std::pmr::vector — polymorphic memory resource sequence container (C++17)