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

Overview

std::flat_set and std::flat_map are container adapters — they wrap an underlying sequence container and impose sorted-associative semantics on top of it. The default backing container is std::vector, giving true contiguous memory layout and the cache-friendliness that comes with it.

Unlike std::set (a red-black tree), every element in a flat_set is adjacent in memory. A binary search over 1 000 contiguous integers touches perhaps five or six cache lines; the equivalent tree walk chases eight to ten pointer hops, each a potential cache miss. At typical L1 miss penalties this difference is not theoretical — benchmarks routinely show flat_set lookup at 2–5× faster than std::set for integer keys under a few thousand elements.

The tradeoff is mutability. Insertion and erasure are O(n) because elements must shift to maintain order. flat_set is the right choice when the set is built once (or infrequently) and read often; it is the wrong choice when elements arrive in high-frequency interleaved insert/erase bursts.

flat_map extends the model to key-value pairs with an important structural distinction: keys and values are stored in two separate parallel arrays, not as contiguous std::pair objects. A flat_map<string, int> keeps all strings contiguous and all ints contiguous — better for workloads that scan only keys, and occasionally useful for SIMD over the value array.

C++23 also provides std::flat_multiset and std::flat_multimap for non-unique keys.

Syntax

// C++23 — header: <flat_set>
template<
    class Key,
    class Compare      = std::less<Key>,
    class KeyContainer = std::vector<Key>
>
class flat_set;

// C++23 — header: <flat_map>
template<
    class Key,
    class T,
    class Compare         = std::less<Key>,
    class KeyContainer    = std::vector<Key>,
    class MappedContainer = std::vector<T>
>
class flat_map;

Both provide the full sorted-associative lookup interface: find, contains, lower_bound, upper_bound, equal_range, count, operator[] (flat_map only), and at. All lookups are O(log n) via binary search on the contiguous key array.

Examples

Basic flat_set usage

#include <flat_set>
#include <print>          // C++23

std::flat_set<int> s = {5, 3, 1, 4, 2};
// Internal layout: contiguous sorted array [1, 2, 3, 4, 5]

s.insert(6);   // O(n) — may shift elements
s.erase(3);    // O(n) — shifts tail

std::println("{}", s.contains(4));  // true  // C++23

// Direct read-only access to the backing vector
const auto& raw = s.keys();  // const std::vector<int>&
std::println("size={} front={}", raw.size(), raw.front());

flat_map with parallel arrays

#include <flat_map>
#include <algorithm>

std::flat_map<std::string, int> scores = {
    {"alice", 95}, {"bob", 87}, {"carol", 92}
};

scores["dave"] = 78;
std::println("{}", scores.at("alice"));  // 95

// Keys and values live in separate contiguous arrays
const auto& keys   = scores.keys();    // const std::vector<std::string>&
const auto& values = scores.values();  // const std::vector<int>&

// Binary-search keys directly — useful when you only need to probe existence
auto it = std::lower_bound(keys.begin(), keys.end(), std::string{"carol"});
if (it != keys.end() && *it == "carol") {
    auto idx = std::distance(keys.begin(), it);
    std::println("carol: {}", values[idx]);
}

Bulk construction and sorted_unique

#include <flat_set>

// from_range (C++23): accepts any range, sorts and deduplicates internally
std::vector<int> raw = {8, 1, 5, 3, 7, 2, 4, 6, 1, 5};
std::flat_set<int> fs(std::from_range, raw);   // C++23 — result: {1,2,3,4,5,6,7,8}

// If input is already sorted and unique, skip the sort+unique pass:
std::vector<int> pre = {1, 2, 3, 4, 5};
std::flat_set<int> fs2(std::sorted_unique, pre.begin(), pre.end());  // C++23
// Passing unsorted or duplicate data with sorted_unique_t is undefined behaviour.

extract and replace for zero-copy rebuilds

std::flat_set<int> fs = {1, 2, 3, 4, 5};

// extract() moves out the backing container; fs is left empty — O(1)
std::vector<int> vec = std::move(fs).extract();

// Mutate the raw vector externally (batch append, filter, etc.)
vec.push_back(6);
std::sort(vec.begin(), vec.end());
// No duplicates required here; dedup if needed before replace()

// replace() injects pre-sorted, deduplicated data back — O(1), no allocation
// Violating the sorted+unique precondition is undefined behaviour.
fs.replace(std::move(vec));

Custom backing container

#include <flat_set>
#include <memory_resource>    // C++17

std::pmr::monotonic_buffer_resource pool;
std::flat_set<int, std::less<int>, std::pmr::vector<int>> pmr_set{&pool};
// All key storage comes from the pool; reset the pool to free everything at once.
pmr_set.insert({3, 1, 4, 1, 5, 9});

Best Practices

Prefer bulk construction over repeated insertion. Building a flat_set by inserting N elements one at a time is O(n²) in total shifts. Construct from a range or use extract/replace to mutate the underlying vector in bulk and reinject it.

Call reserve before incremental insertion. flat_set delegates reserve() to its backing vector. Pre-reserving eliminates reallocation copies even when inserts are unavoidable.

Use sorted_unique for pre-sorted input. When rehydrating from a sorted store (a database result set, a sorted file), sorted_unique_t constructors skip the internal sort pass entirely — O(n) construction instead of O(n log n).

Size threshold: flat_set wins below ~10 000 elements with low mutation rate. Above that point the O(n) insert cost tends to dominate unless the container is genuinely immutable after construction. Profile your specific key type; string keys with long common prefixes shift the crossover lower than integers.

flatmap's parallel-array layout enables key-only scans. When checking membership without caring about values, operating directly on keys() avoids touching the value array entirely — meaningful for wide mapped types.

Common Pitfalls

Every mutation invalidates all iterators. Unlike std::set, where only the erased iterator is invalidated, any insert or erase in flat_set/flat_map may reallocate the underlying vector or shift elements, invalidating all iterators, pointers, and references. This is the single largest source of correctness bugs when migrating from std::set.

std::flat_set<int> s = {1, 2, 3};
auto it = s.find(2);
s.insert(4);          // it is now invalid — dereferencing it is undefined behaviour

flat_map dereference yields a proxy, not a real pair. The value_type is std::pair<const Key, T>, but the reference type (what *it yields) is std::pair<const Key&, T&> — a proxy object. Taking the address of *it and treating it as std::pair<const Key, T>* is undefined behaviour.

std::flat_map<int, int> m = {{1, 10}};
auto it = m.begin();
auto& [k, v] = *it;                       // OK — structured binding works
// std::pair<const int, int>* p = &*it;   // UB: address of a proxy temporary

sorted_unique and replace() are trust-me APIs. No validation is performed. Passing unsorted or duplicate data leaves the container in a broken state where binary search produces silently wrong results. Assert invariants in debug builds before calling these APIs on externally-sourced data.

operator[] on flat_map inserts on miss — and that insert is O(n). Probing with [] on a map that may not contain the key is therefore a potential O(n) operation. Use find for read-only probing, or try_emplace with a position hint when you know where the key should land.

// Avoid if the key may be absent and performance matters:
scores["unknown_player"];       // inserts default-constructed value, O(n) shift

// Prefer:
if (auto it = scores.find("unknown_player"); it != scores.end()) { ... }

See Also

• std::set — node-based sorted set; O(log n) insert/erase without iterator invalidation
• std::unordered_set — O(1) average lookup; unsorted, no range queries
• std::vector — default backing container; determines allocation and iterator behaviour
• std::flat_multiset / std::flat_multimap — C++23 variants permitting duplicate keys