std::flat_map

Overview

std::flat_map, introduced in C++23 via <flat_map>, is a container adaptor, not a standalone container. It wraps two separate sequence containers — one for keys, one for mapped values — and keeps them sorted in lockstep. By default both containers are std::vector, so iteration walks a tight contiguous block of keys and a separate contiguous block of values rather than chasing tree node pointers scattered across the heap.

The performance trade-off relative to std::map:

flat_map wins when the map is built once and read many times, the map is small enough that O(n) shifts are cheap relative to allocation overhead, or cache pressure from tree-node indirection is measurable on the critical path.

Syntax

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

The KeyContainer and MappedContainer types must satisfy the SequenceContainer requirements and support random-access iterators. std::deque is the most common alternative to std::vector when you need stable pointers to elements (flat_map itself does not guarantee pointer stability, but an underlying deque provides it).

Examples

Construction and basic access

#include <flat_map>
#include <string>
#include <print>  // C++23

int main() {
    // Default construction + insertion — C++23
    std::flat_map<std::string, int> scores;
    scores["alice"] = 95;
    scores["bob"]   = 87;
    scores.emplace("carol", 92);

    // Initializer-list construction: elements are sorted on construction
    std::flat_map<std::string, int> config{
        {"timeout", 30},
        {"retries", 3},
        {"workers", 8},
    };

    // If you already have sorted, unique data, skip the sort pass
    std::flat_map<int, std::string> lookup{
        std::sorted_unique,         // std::sorted_unique_t tag — C++23
        {1, 2, 3, 4, 5},
        {"one", "two", "three", "four", "five"}
    };

    std::println("{}", scores.at("alice")); // 95
}

Accessing the underlying sequences

flat_map exposes the raw key and mapped containers directly, which is impossible with std::map:

std::flat_map<int, double> prices{
    {10, 1.25}, {20, 3.50}, {30, 0.99}
};

// Read-only views of the underlying vectors — C++23
const auto& ks = prices.keys();    // std::vector<int> const&
const auto& vs = prices.values();  // std::vector<double> const&

// SIMD-friendly: both are contiguous, separately accessible
for (std::size_t i = 0; i < ks.size(); ++i) {
    std::println("id={} price={:.2f}", ks[i], vs[i]);
}

Bulk construction via extract/replace

When you need to build a large map from unsorted data without per-element overhead:

#include <flat_map>
#include <algorithm>
#include <vector>

std::flat_map<int, std::string> build_from_log(
    std::vector<std::pair<int, std::string>> records)
{
    // Sort outside the map, then inject the sorted sequences
    std::ranges::sort(records, {}, &std::pair<int,std::string>::first);

    std::vector<int> keys;
    std::vector<std::string> vals;
    keys.reserve(records.size());
    vals.reserve(records.size());

    for (auto& [k, v] : records) {
        keys.push_back(k);
        vals.push_back(std::move(v));
    }

    // Construct directly from sorted containers, bypassing re-sort
    return std::flat_map<int, std::string>{
        std::sorted_unique, std::move(keys), std::move(vals)
    };
}

extract_sequence and replace_sequence

For in-place bulk mutation (rare, but useful for batch updates):

std::flat_map<int, int> fm{{1,10},{2,20},{3,30}};

// Extract ownership of both containers
auto [ks, vs] = std::move(fm).extract_sequence();  // C++23

// Mutate freely — invariant is suspended
ks.push_back(4);
vs.push_back(40);

// Restore: you must re-sort and enforce uniqueness yourself
auto cs = typename decltype(fm)::containers{std::move(ks), std::move(vs)};
fm.replace_sequence(std::sorted_unique, std::move(cs));

Custom underlying container

#include <deque>

// Deque-backed: no iterator invalidation on push_back at either end
// (flat_map still doesn't guarantee stable references, but deque itself does)
std::flat_map<int, std::string,
              std::less<int>,
              std::deque<int>,
              std::deque<std::string>> dm;

dm[1] = "one";
dm[2] = "two";

Best Practices

Prefer flat_map for read-heavy maps built during startup. Load configuration, parse a lookup table, sort once, then query millions of times — this is where the binary-search-over-vector pattern dominates tree lookup.

Reserve capacity before bulk insertion. If you're calling insert or emplace in a loop on a vector-backed flat_map, every insertion above capacity triggers an O(n) reallocation on top of the O(n) shift. Pre-reserve the underlying vectors by constructing from a range or using extract_sequence / replace_sequence.

Use the std::sorted_unique constructor when data is already ordered. It skips the internal sort entirely and avoids the O(n log n) construction cost.

Avoid as a write-heavy shared data structure. If inserts and erases happen concurrently with reads and writes throughout the object's lifetime, std::map or std::unordered_map will outperform flat_map because they avoid the O(n) shift.

Common Pitfalls

Violating the sorted-unique invariant via std::sorted_unique. Passing std::sorted_unique with data that is not actually sorted or contains duplicate keys is undefined behaviour. The tag is a contract, not a hint.

Mixing operator[] with performance assumptions. operator[] inserts a default-constructed value if the key is absent, which is O(n) on a flat container. In a tight lookup loop, prefer find() or contains().

std::flat_map<int, int> fm{{1,1},{2,2},{3,3}};

// Avoid: inserts zero for key 99 — O(n) shift
int& v = fm[99];

// Prefer for read-only lookup
if (auto it = fm.find(99); it != fm.end()) {
    use(it->second);
}

Iterator invalidation. Any insertion or erasure invalidates all iterators, pointers, and references — the same rules as std::vector. With std::map, only the erased node's iterator is invalidated. Code that caches flat_map iterators across mutations is incorrect.

Not accounting for copy cost of large mapped types. Because values sit in a contiguous std::vector, inserting in the middle requires shifting every subsequent element. If T is expensive to copy or move (e.g. a large aggregate with no move constructor), this can eclipse any cache-locality gain.

std::flat_multimap — the Duplicate-Key Variant

std::flat_multimap (C++23, also in <flat_map>) is the parallel adaptor for cases where multiple values share the same key. It has the same template signature as flat_map and uses the same pair of sorted parallel vectors, but it drops the uniqueness constraint: duplicate keys sit side-by-side in the key vector, so all values for a given key occupy a contiguous range in the mapped-value vector.

// Declaration — same template parameters as flat_map
template<
    class Key,
    class T,
    class Compare        = std::less<Key>,
    class KeyContainer   = std::vector<Key>,
    class MappedContainer = std::vector<T>
>
class flat_multimap;

Key differences from flat_map:

Iterating over equal keys with equal_range

equal_range is the canonical way to visit all values for a given key. It returns a std::pair<iterator, iterator> — a half-open range [first, last) containing every element whose key compares equivalent.

#include <flat_map>
#include <string>
#include <print>

int main() {
    // Tags mapped to HTTP status codes (multiple tags per code)
    std::flat_multimap<int, std::string> status_tags{
        {200, "ok"},
        {200, "success"},
        {404, "not-found"},
        {404, "missing"},
        {404, "no-route"},
        {500, "error"},
    };

    // Retrieve all tags for status 404 — O(log n) binary search
    auto [first, last] = status_tags.equal_range(404);
    for (auto it = first; it != last; ++it) {
        std::println("  {}: {}", it->first, it->second);
    }
    // Output:
    //   404: missing
    //   404: no-route
    //   404: not-found

    // count() uses the same binary-search range under the hood
    std::println("{} entries for 404", status_tags.count(404)); // 3

    // lower_bound / upper_bound are equivalent
    auto lo = status_tags.lower_bound(200);
    auto hi = status_tags.upper_bound(200);
    // [lo, hi) spans all 200 entries
}

emplace and unhinted insert always insert at the upper bound of the existing equal-key range, so insertion order is preserved within a key group unless emplace_hint is used to place the element elsewhere.

std::sorted_equivalent tag for pre-sorted data

flat_multimap uses std::sorted_equivalent (not std::sorted_unique) to signal that input data is already sorted but may contain duplicate keys:

std::flat_multimap<int, std::string> fm{
    std::sorted_equivalent,     // data is sorted; duplicates are fine
    {1, 1, 2, 3, 3},
    {"a", "b", "c", "d", "e"},
};
// No re-sort performed — O(n) construction instead of O(n log n)

Using std::sorted_equivalent with data that is not actually sorted is undefined behaviour, the same contract as std::sorted_unique on flat_map.

Heterogeneous Lookup with is_transparent

By default, every lookup in flat_map<std::string, V> requires an std::string key. Passing a string_view or a const char* forces an implicit conversion — allocating a temporary std::string on the heap if the string is too long for SSO. On hot paths with thousands of lookups per second, this cost accumulates.

Heterogeneous lookup eliminates the temporary by letting the binary search compare the key container's elements directly against whatever comparable type you supply. It is enabled by passing a comparator that exposes a nested type named is_transparent.

The two standard-library options are:

• std::less<> (the void specialisation) — enables heterogeneous ordered lookup (available since C++14 for std::map; applies equally to flat_map)
• std::ranges::less — a C++20 range-aware alternative with the same effect

#include <flat_map>
#include <string>
#include <string_view>

// Without heterogeneous lookup — constructs a std::string temporary
std::flat_map<std::string, int> fm_slow{
    {"alpha", 1}, {"beta", 2}, {"gamma", 3}
};
// This call converts the string_view to std::string — potential heap alloc
auto it = fm_slow.find(std::string_view{"alpha"});

// With heterogeneous lookup — no temporary, no allocation
std::flat_map<std::string, int, std::less<>> fm_fast{
    {"alpha", 1}, {"beta", 2}, {"gamma", 3}
};

// find / contains / count / lower_bound / upper_bound / equal_range
// all accept any K comparable to std::string without constructing one
std::string_view key = "beta";
if (auto it2 = fm_fast.find(key); it2 != fm_fast.end()) {
    // it2->second == 2, no string copy was made
}

// Same works with const char*
bool has = fm_fast.contains("gamma");   // no allocation

The mechanism: std::less<> defines using is_transparent = void; and its operator() is a pair of template parameters, so operator()(std::string_view, std::string const&) compiles without conversion. The flat_map lookup functions have template<class K> iterator find(const K& x) overloads that are only enabled when Compare::is_transparent is a valid type (SFINAE-gated).

When this matters most: long strings that exceed SSO (typically >15-22 bytes). The cppstories.com benchmark shows up to 35% speedup for long-string lookups when switching to transparent comparators on std::map. The same gain applies to flat_map since the comparison cost is identical — flat_map's binary search is just fewer cache misses away.

Safety note: Heterogeneous lookup is opt-in because it can silently produce wrong results when the alternate type's ordering is not consistent with the key type's ordering. For example, looking up a double in a flat_map<int, V, std::less<>> would use floating-point comparison, which may not correspond to any stored integer key. Stick to type-safe comparable alternatives (e.g. std::string_view for std::string keys).

extract and replace — Bulk Container Surgery

flat_map exposes extract() and replace() to hand ownership of the underlying containers back and forth. This enables batch mutations that would otherwise require O(n) shifts for each individual insertion or erasure.

API

// Extract — rvalue-qualified: moves both containers out; fm is left empty
containers extract() &&;
// Where containers is the nested struct:
//   struct containers { KeyContainer keys; MappedContainer values; };

// Replace — takes ownership of pre-sorted, same-length containers
void replace(KeyContainer&&, MappedContainer&&);
// Precondition: keys must be sorted and have no duplicates;
// keys.size() == values.size(). Violating this is undefined behaviour.

Pattern: batch mutation of a live map

#include <flat_map>
#include <vector>
#include <algorithm>

void batch_upsert(std::flat_map<int, std::string>& fm,
                  std::vector<std::pair<int, std::string>> updates)
{
    // Step 1: pull the guts out — O(1), just moves the vectors
    auto [ks, vs] = std::move(fm).extract();

    // Step 2: merge updates into the raw vectors (invariant suspended)
    for (auto& [k, v] : updates) {
        auto pos = std::ranges::lower_bound(ks, k);
        auto idx = pos - ks.begin();
        if (pos != ks.end() && *pos == k) {
            vs[idx] = std::move(v);           // update existing
        } else {
            ks.insert(pos, k);
            vs.insert(vs.begin() + idx, std::move(v));  // insert
        }
    }

    // Step 3: put the containers back — O(1)
    fm.replace(std::move(ks), std::move(vs));
    // fm is now valid again with sorted unique keys
}

Pattern: build-then-lock workflow

The idiomatic high-performance pattern is to build the raw vectors externally (where you control sorting and deduplication), then inject them once:

std::flat_map<std::string, int> build_word_index(
    const std::vector<std::string>& tokens)
{
    std::vector<std::string> keys;
    std::vector<int> counts;

    // Accumulate in a temporary unordered_map for O(1) inserts
    std::unordered_map<std::string, int> tmp;
    for (const auto& t : tokens) tmp[t]++;

    keys.reserve(tmp.size());
    counts.reserve(tmp.size());
    for (auto& [k, v] : tmp) {
        keys.push_back(k);
        counts.push_back(v);
    }

    // Sort both vectors in sync
    std::vector<std::size_t> idx(keys.size());
    std::iota(idx.begin(), idx.end(), 0);
    std::ranges::sort(idx, [&](auto a, auto b) {
        return keys[a] < keys[b];
    });

    std::vector<std::string> skeys(keys.size());
    std::vector<int> scounts(keys.size());
    for (std::size_t i = 0; i < idx.size(); ++i) {
        skeys[i]   = std::move(keys[idx[i]]);
        scounts[i] = counts[idx[i]];
    }

    // Inject — bypass O(n log n) flat_map construction
    std::flat_map<std::string, int> fm;
    fm.replace(std::move(skeys), std::move(scounts));
    return fm;
}

replace() does not re-sort or validate its inputs — it blindly trusts that the preconditions are met. If the supplied key vector is not sorted or contains duplicates, the resulting flat_map has undefined behaviour on any subsequent lookup.

Performance Comparison

The numbers below are representative order-of-magnitude guidance based on published Boost flat_map benchmarks and community measurements; your actual results will differ based on hardware, element size, and access pattern. Always profile your own workload.

Iteration (sequential scan, n elements)

Iteration is where flat_map wins most decisively. A sequential pass over flat_map keys reads a single contiguous std::vector<Key> — the CPU prefetcher can feed the pipeline with no stalls. std::map requires following a pointer per node, thrashing the data cache at anything beyond a few hundred elements.

Lookup (random-key find, n elements)

flat_map lookup is binary search (O(log n)) on a contiguous key array. At small-to-medium sizes (under ~4 000 elements) the binary search cost is dominated by cache locality wins, so flat_map often beats both alternatives. At large sizes unordered_map's O(1) average case pulls ahead, and flat_map may even lag map due to TLB misses from touching many pages of the key vector.

Insertion / Erasure

Single-element insert/erase on flat_map is its Achilles' heel: every element to the right of the insertion point must be shifted one position in both the key and value vectors, which is O(n) data movement. For write-heavy workloads with many random insertions, map or unordered_map wins by a wide margin.

Memory per element

flat_map has the lowest memory overhead because there are no per-element node headers, no allocator round-trips per element, and no pointer indirection. For small mapped types (int, float, pointer), the memory saving over map can be 3–5×.

Decision guide

Need duplicate keys?
  Yes → flat_multimap (or multimap if writes are frequent)
  No  → continue

Mostly reads after initial load?
  Yes → flat_map
  No  → continue

n < ~1 000 AND sorted order required?
  Yes → flat_map
  No  → continue

Ordering matters / range queries needed?
  Yes → map
  No  → unordered_map

See Also

• std::flat_set — the set variant using the same flat storage strategy
• std::map — node-based predecessor with O(log n) insert/erase and stable iterators
• std::unordered_map — O(1) average lookup when ordering is not required
• std::flat_multimap — flat adaptor permitting duplicate keys (C++23)
• std::sorted_unique — the tag type used to bypass sort on construction