Flat containers: flat_map and inplace_vector

std::map and std::vector are the defaults, and both make a hidden choice: map allocates a node per element and chases pointers on every lookup; vector keeps its elements on the heap. C++23 and C++26 add containers that make the opposite choice:

• std::flat_map / std::flat_set (C++23): a sorted map stored in plain vectors. Lookups are a binary search over contiguous memory.
• std::inplace_vector<T, N> (C++26): a vector whose storage is inside the object. It never allocates; its capacity is fixed at N.

Neither is "better". Each trades something away, and the skill is knowing what.

1. What a flat_map looks like inside

A flat_map<K, V> holds two containers — by default std::vector<K> and std::vector<V> — kept sorted by key, with keys()[i] belonging to values()[i]:

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

int main() {
    std::flat_map<std::string, int> ages{{"cy", 41}, {"ana", 30}, {"bo", 25}};
    std::println("keys:   {}", ages.keys());
    std::println("values: {}", ages.values());
    for (const auto& [name, age] : ages) std::print("{}={} ", name, age);
    std::println();
}

There are no pair objects in memory: iterating yields a proxy whose first and second refer into the two vectors. Storing keys separately means a lookup's binary search touches only keys — dense, cache-friendly, and prefetcher-friendly.

2. What it costs

The insert cost is the catch. Inserting n keys one at a time into an empty flat_map is 1 + 2 + … + n shifts: O(n²). And because inserting may reallocate the underlying vectors, every iterator, pointer and reference into the map is invalidated by an insert or erase — unlike std::map, where they survive.

auto& age = ages["ana"];   // reference into ages.values()
ages["dee"] = 52;          // may reallocate values(): `age` now dangles

3. Building one: sort once, then hand it over

The way to fill a flat_map with many elements is to not insert them one by one. Put them in vectors, sort, remove duplicates, and give the result to the map. If you promise the data is already sorted and unique with the tag std::sorted_unique, the constructor does no work at all:

#include <algorithm>
#include <flat_map>
#include <print>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> keys{"ana", "bo", "cy"};   // sorted, unique
    std::vector<int> values{30, 25, 41};
    std::flat_map<std::string, int> m(std::sorted_unique, std::move(keys), std::move(values));
    std::println("{} entries, bo={}", m.size(), m.at("bo"));

    // Without the tag, the constructor sorts and deduplicates for you…
    std::flat_map<std::string, int> n(std::vector<std::string>{"cy", "ana", "cy"},
                                      std::vector<int>{1, 2, 3});
    // …but WHICH "cy" survives is unspecified.
    std::println("{} entries", n.size());
}

That last comment matters. When duplicates need a policy ("the first one wins", "the largest wins"), apply it yourself before building the map.

Worked example: first occurrence wins

Input: unsorted (name, value) pairs where a name may repeat; the first occurrence must win.

#include <cstddef>
#include <flat_map>
#include <print>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

std::flat_map<std::string, int> build(std::vector<std::pair<std::string, int>> in) {
    // 1. Sort positions by (name, position): equal names stay in input order.
    std::vector<std::size_t> order(in.size());
    for (std::size_t i = 0; i < order.size(); ++i) order[i] = i;
    std::ranges::sort(order, [&](std::size_t a, std::size_t b) {
        return std::tie(in[a].first, a) < std::tie(in[b].first, b);
    });
    // 2. Keep the first of each run of equal names.
    std::vector<std::string> keys;
    std::vector<int> values;
    for (std::size_t i : order) {
        if (!keys.empty() && keys.back() == in[i].first) continue;
        keys.push_back(std::move(in[i].first));
        values.push_back(in[i].second);
    }
    // 3. Already sorted and unique: no work for the constructor.
    return {std::sorted_unique, std::move(keys), std::move(values)};
}

int main() {
    auto m = build({{"x", 1}, {"a", 2}, {"x", 3}, {"a", 4}, {"m", 5}});
    for (const auto& [k, v] : m) std::print("{}={} ", k, v);
    std::println();
}

The tie-break on position makes the sort key unique, so an ordinary (unstable) sort gives a stable result. std::ranges::stable_sort by name followed by std::ranges::unique does the same job.

Total cost: one O(n log n) sort and a linear pass, versus O(n²) for n inserts.

4. Transparent lookup

With the default comparator std::less<std::string>, find takes a const std::string&, so looking up a std::string_view doesn't even compile — and looking up a const char* quietly builds a temporary std::string (an allocation, for long keys). std::less<> is transparent: it compares any two things that have <, and the map's lookup functions then accept any key-like type.

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

int main() {
    std::flat_map<std::string, int> m{{"key", 1}};
    std::string_view k = "key";
    return m.contains(k);   // error: no conversion from string_view to string
}

#include <flat_map>
#include <functional>
#include <print>
#include <string>
#include <string_view>

int main() {
    std::flat_map<std::string, int, std::less<>> m{{"key", 1}};
    std::string_view k = "key";
    std::println("{}", m.contains(k));   // no temporary std::string
}

The same applies to std::map, std::set and std::flat_set (std::unordered_map needs a transparent hash and equality — see the hash-map skill).

5. flat_set, and the other members

std::flat_set<K> stores sorted unique keys in one adapted sequence. flat_multiset retains equivalent duplicate keys; flat_multimap retains all key/value pairs in its parallel key/value sequences. These are C++23 containers. Their iterators and references have flat-storage invalidation rules, rather than the stable-node guarantees of map/set.

For the map variants, keys() / values() expose read-only access to the underlying containers. extract() moves those containers out and leaves the map empty; replace(keys,values) installs containers whose ordering and multiplicity satisfy the selected map type's preconditions. The set variants have a single underlying key container rather than separate keys and values.

The unique types use std::sorted_unique; the multi types use std::sorted_equivalent when the caller has already established the required invariant. Neither tag sorts arbitrary input. Continue with duplicate-key and flat-container practice for real flat_set, flat_multiset and flat_multimap exercises, inclusive bounds, bulk construction and duplicate-preserving results.

6. When to choose which

7. inplace_vector: a vector that never allocates

std::inplace_vector<T, N> has the interface of a vector, but its elements live inside the object, like std::array's. Unlike std::array, its size varies from 0 to N, and elements beyond the size don't exist (no default construction).

#include <inplace_vector>
#include <print>

int main() {
    std::inplace_vector<int, 4> v{1, 2};
    v.push_back(3);
    std::println("size {} capacity {}", v.size(), v.capacity());

    v.push_back(4);                       // now full
    if (auto r = v.try_push_back(5); !r)  // empty optional: no room
        std::println("full, 5 not added");
    try {
        v.push_back(5);                   // throws when full
    } catch (const std::bad_alloc&) {
        std::println("push_back threw bad_alloc");
    }
}

What happens at capacity depends on which function you call:

Why use it?

• No heap at all: embedded code, real-time paths and signal handlers where new is forbidden or unpredictable.
• Bounded by design: "at most 8 path components", "up to 16 pending events" — the capacity documents and enforces the limit.
• Lives where its owner lives: on the stack or inside another object, so no pointer chasing, and if T is trivially copyable, so is the whole inplace_vector (copy it with memcpy, put it in shared memory).

The cost: sizeof is always at least N * sizeof(T), even when empty, and moving it moves every element (there's no pointer to steal).

Faded example — your turn

Collect at most 4 words from a sentence, without allocating. Return std::nullopt if there are more. What goes in the loop?

std::optional<std::inplace_vector<std::string_view, 4>> words(std::string_view s) {
    std::inplace_vector<std::string_view, 4> out;
    for (auto w : s | std::views::split(' ')) {
        std::string_view word(w.begin(), w.end());
        if (word.empty()) continue;
        /* ??? */
    }
    return out;
}

Summary

• flat_map = sorted keys and values in two vectors: fast lookups and iteration, O(n) inserts, and every insert invalidates every iterator.
• Build in bulk: sort, apply your duplicate policy, construct with std::sorted_unique. Never insert n elements one at a time.
• Use std::less<> so lookups take string_view without allocating.
• inplace_vector<T, N>: vector interface, fixed capacity, no allocation. When full: push_back throws, try_push_back returns an empty optional, unchecked_push_back is undefined behaviour.