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()) { ... }

std::flat_multiset (C++23)

std::flat_multiset is the duplicate-keys sibling of std::flat_set. It shares the same template signature and the same contiguous-storage adapter pattern, but allows multiple elements with equivalent keys. Its count() can return values greater than one and equal_range() is the idiomatic way to iterate over all copies of a key.

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

The key behavioural differences from flat_set:

• No uniqueness enforcement on insert. Inserting a key that already exists does not silently discard it.
• sorted_equivalent_t instead of sorted_unique_t. When pre-sorted data may contain duplicates, use the std::sorted_equivalent tag (not std::sorted_unique) to bypass the sort pass.
• count() and equal_range() return meaningful ranges. On flat_set, count() always returns 0 or 1.

#include <flat_set>
#include <print>

std::flat_multiset<int> ms = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
// Stored sorted: [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]

std::println("count(3) = {}", ms.count(3));   // 2
std::println("count(7) = {}", ms.count(7));   // 0

// Iterate over all copies of 5
auto [lo, hi] = ms.equal_range(5);
for (auto it = lo; it != hi; ++it) {
    std::println("{}", *it);  // prints 5 twice
}

// Pre-sorted input with duplicates: use sorted_equivalent, not sorted_unique
std::vector<int> pre = {1, 1, 2, 3, 3};
std::flat_multiset<int> ms2(std::sorted_equivalent, pre.begin(), pre.end());

std::flat_multimap (header <flat_map>) extends the same pattern to key-value pairs with duplicate keys permitted. Both share the same __cpp_lib_flat_set feature-test macro (202207L).

Custom Comparators and Heterogeneous Lookup

flat_set accepts any comparator satisfying strict weak ordering as its second template argument. The most impactful use is enabling heterogeneous lookup via a comparator that declares is_transparent.

Without a transparent comparator, find("hello") on a flat_set<std::string> must construct a temporary std::string from the string literal before the binary search can begin — a heap allocation for each probe. A transparent comparator eliminates that temporary.

#include <flat_set>
#include <string>
#include <string_view>

// Transparent comparator: declares is_transparent so that find/contains/
// lower_bound/upper_bound/equal_range accept heterogeneous arguments.
struct StringCmp {
    using is_transparent = void;   // the magic opt-in marker

    bool operator()(std::string_view a, std::string_view b) const {
        return a < b;
    }
};

// Key type is std::string; comparator is StringCmp (transparent).
std::flat_set<std::string, StringCmp> names = {
    "alice", "bob", "carol", "dave"
};

// These calls do NOT construct a temporary std::string:
bool found = names.contains("alice");           // string_view overload
auto it    = names.find(std::string_view{"bob"}); // zero allocation
auto lo    = names.lower_bound("c");             // string_view overload

// Without StringCmp (using default std::less<std::string>),
// all three lines above would allocate a temporary std::string.

std::less<> (the void specialisation, C++14) is the easiest way to get a transparent less-than comparator when your key type already defines operator< that accepts the lookup types:

// std::less<> is transparent out of the box — works for string vs string_view
// because std::string has operator< overloads accepting string_view.
std::flat_set<std::string, std::less<>> words = {"alpha", "beta", "gamma"};
bool ok = words.contains("alpha");   // string_view lookup, no allocation

Custom ordering example — reverse sort:

std::flat_set<int, std::greater<int>> desc = {1, 2, 3, 4, 5};
// Stored: [5, 4, 3, 2, 1]
// Iteration and all range queries honour the descending order.
std::println("max = {}", *desc.begin());  // 5

Case-insensitive lookup:

struct ILess {
    using is_transparent = void;
    bool operator()(std::string_view a, std::string_view b) const {
        return std::ranges::lexicographical_compare(
            a, b, [](unsigned char x, unsigned char y) {
                return std::tolower(x) < std::tolower(y);
            });
    }
};

std::flat_set<std::string, ILess> tags = {"Alpha", "Beta", "Gamma"};
// Heterogeneous lookup with a string literal — no temporary std::string:
std::println("{}", tags.contains("alpha"));  // true (case-insensitive match)
std::println("{}", tags.contains("BETA"));   // true

Performance Comparison

The table below summarises empirical characteristics across three sorted/unsorted containers. Figures assume integer keys, a modern x86-64 processor, and cold L1/L2 caches; actual crossover points depend heavily on key size, value size, comparator cost, and mutation rate.

Key takeaways sourced from benchmarks (Björn Fahller, CppCon / Playful Programming; Tyler Young 2019):

• For iteration-heavy workloads, flat_set can be 5–10× faster than std::set and std::unordered_set due to sequential memory access and hardware prefetch.
• For lookup at small n (under ~256 elements for integers), flat_set and even std::set beat std::unordered_set, which spends more time on hashing and bucket overhead than it saves.
• For pure lookup at large n with rare mutation, std::unordered_set reclaims the lead over both ordered containers.
• flat_set's memory footprint is lowest: no per-node allocations, no hash-table load-factor headroom, and shrink_to_fit() is available.

When NOT to Use flat_set

flat_set has a hard structural weakness: every insert or erase is O(n) in the worst case due to element shifting. In the right workloads this cost is negligible; in the wrong ones it dominates everything else.

Avoid flat_set when:

High insertion or erasure rate at arbitrary positions. If your code does interleaved insert/erase throughout the element lifetime (a dynamic membership set, an event queue, a live blacklist), the O(n) shift cost accumulates to O(n²) total work across N mutations. std::set (O(log n) per mutation) or std::unordered_set (O(1) amortised) are the right tools.

// Anti-pattern: repeated individual inserts into a large flat_set
std::flat_set<int> live_ids;
for (int id : stream_of_10k_ids) {
    live_ids.insert(id);   // O(n) per call — O(n²) total
}
// Prefer: accumulate into a vector, sort once, construct flat_set from range

Non-movable or expensive-to-move key types. Every shift during insert/erase invokes the move constructor (or copy constructor for non-movable types). If your key type wraps a large buffer or has a throwing move, the shift cost multiplies and exception safety degrades.

Large n with random-access lookup patterns dominating. Once the key array no longer fits in L2/L3 cache, the binary search's non-sequential access pattern starts generating cache misses. Above roughly 50 000–100 000 elements, std::unordered_set typically pulls ahead on pure lookup throughput. Profile with your actual key type and access pattern before committing.

When iterator or pointer stability is required. Code that caches iterators or pointers into the set across mutations is fundamentally incompatible with flat_set. If stability is a correctness requirement, std::set is the only standard option.

// Broken: iterator cached across an insert
std::flat_set<int> s = {1, 2, 3};
auto it = s.find(2);    // iterator into the backing vector
s.insert(4);            // vector may reallocate or shift — it is now dangling
*it;                    // undefined behaviour

Rule of thumb: reach for flat_set when you build once and query often, or when iteration performance is critical. Reach for std::set when mutation is frequent and interleaved. Reach for std::unordered_set when n is large and you need pure lookup speed without order.

flat_set Backed by std::deque

std::vector is the default backing store, but it is not mandatory. Any sequence container that models the SequenceContainer requirements can be substituted as the third template argument, and std::deque is the most practically useful alternative because it offers O(1) amortised push-front and push-back without invalidating existing data once capacity is established.

// C++23 — deque-backed flat_set for workloads with frequent front insertions
#include <flat_set>
#include <deque>
#include <print>

std::flat_set<int, std::less<int>, std::deque<int>> ds;

// push_front on std::deque is O(1) amortised; a vector would shift all elements.
// flat_set still goes through insert(), which maintains sorted order —
// but the underlying deque avoids the full-vector-shift when inserting near front.
ds.insert(5);
ds.insert(1);  // lands near front — deque handles this cheaply
ds.insert(3);
ds.insert(2);
ds.insert(4);

for (int v : ds) std::print("{} ", v);  // 1 2 3 4 5
std::println();

The practical trade-off is that std::deque stores data in fixed-size chunks rather than a single contiguous block. Binary search still works correctly — flat_set only requires random-access iterators — but it now traverses chunk boundaries, losing the pure cache-line linearity of a vector. Use a deque backend when insertions at or near the front are common and the set is large enough that vector-shift costs dominate; for purely read-heavy or back-appending usage, stick with the default std::vector.

// C++23 — extract the backing deque for external manipulation
std::flat_set<int, std::less<int>, std::deque<int>> ds2 = {10, 20, 30};
std::deque<int> raw = std::move(ds2).extract();
raw.push_front(5);   // O(1) — deque's native cheap front-insert
std::sort(raw.begin(), raw.end());
ds2.replace(std::move(raw));  // reinject sorted data — O(1) move, no copy
std::println("front: {}", *ds2.begin());  // 5

A pmr::deque variant is also possible, combining per-block pool allocation with the front-insert benefit — worth profiling on embedded or arena-allocator workloads where heap fragmentation matters.

flat_multiset vs flat_set: Choosing Between Them

Choose flat_multiset whenever the domain permits logically equal elements that must each survive insertion. The common mistake is reaching for flat_set and relying on insert silently discarding duplicates to normalise data — this works, but it hides intent and loses the original multiplicity information.

// C++23 — flat_multiset retains all duplicate insertions
#include <flat_set>
#include <print>

// Use case: frequency counting via a multiset range + equal_range scan
std::flat_multiset<std::string> log_levels = {
    "warn", "info", "error", "warn", "warn", "info"
};
// Stored sorted: [error, info, info, warn, warn, warn]

auto [lo, hi] = log_levels.equal_range("warn");
std::println("warn count: {}", std::distance(lo, hi));  // 3

When uniqueness is an invariant, flat_set enforces it automatically and communicates it in the type. When multiplicity carries meaning (event logs, weight vectors, multisets of tokens), flat_multiset is the correct model. Both types share the same O(log n) lookup and O(n) insertion cost for the contiguous layout.

// C++23 — sorted_equivalent_t bypasses the sort pass for pre-sorted duplicate data
std::vector<int> pre_sorted = {1, 1, 2, 3, 3, 3, 5};
std::flat_multiset<int> fms(std::sorted_equivalent, pre_sorted.begin(), pre_sorted.end());
// O(n) construction: no sort performed, data injected directly into backing vector.

// flat_set equivalent would silently drop duplicate 1s and 3s:
std::flat_set<int> fs(std::sorted_unique, pre_sorted.begin(), pre_sorted.end());
// UB if pre_sorted actually contains duplicates — sorted_unique trusts the caller.

One nuance: flat_multiset::insert_range (C++23) appends all incoming elements and re-sorts the combined backing store, making bulk insertion from a second sorted range efficient. Prefer this over a loop of individual insert calls when merging two sorted sequences.

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