MySmartCoPilot
Ask Go Pro Your pass Pass ends in 7 days

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

C++  Module 10 – Standard containers

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

Use C++23 std::flat_map and std::flat_set for sorted data that is mostly read, build them in bulk with std::sorted_unique, and know what an insertion costs.

  • Intermediate
  • 22 minutes
  • Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
  • By MySmartCoPilot

What you will learn

  • Use flat containers for read-heavy sorted data
  • Build flat containers efficiently from bulk data
  • Explain their insertion cost

Before you start

What you’ll learn · Before you start

What you will learn

  • Use flat containers for read-heavy sorted data
  • Build flat containers efficiently from bulk data
  • Explain their insertion cost

Before you start

On this page

std::flat_map and std::flat_set, new in C++23, are sorted containers with the interface of std::map and std::set, but without nodes. A flat_map keeps its keys in one sorted std::vector and its values in another, at the same positions, and a flat_set keeps one sorted vector. Lookups are binary searches over contiguous memory, so they are fast, a pass over every element is as fast as over a vector, and memory per element is little more than the elements themselves. The cost is insertion: a new key in the middle shifts every later key and value, so a single insertion or erasure takes linear time. Use them for sorted data that is built once, or rarely changed, and then read many times.

This lesson builds and reads a flat_map, shows why the usual loop over a map does not compile with it, measures what each way of loading data costs, compares memory and speed with std::map on a read-heavy workload, and ends with two promises the flat containers expect you to keep.

A sorted map in two vectors

flat_basics.cpp C++ · flat_basics.cpp 
// std::flat_map (C++23) has the interface of std::map, but keeps its keys in one sorted std::vector and its values
// in another, at the same positions. std::flat_set keeps one sorted vector of keys.
#include <flat_map>
#include <flat_set>
#include <print>
#include <string>

int main() {
    std::flat_map<std::string, int> stock{{"pens", 40}, {"ink", 7}, {"paper", 500}};
    stock["clips"] = 120;  // like std::map: operator[] inserts a missing key
    stock.erase("ink");
    std::println("{}", stock);
    std::println("keys {} and values {}", stock.keys(), stock.values());  // the two vectors themselves

    auto it = stock.find("paper");
    std::println("paper: {}, at position {}", it->second, it - stock.begin());  // random access iterators
    std::println("the second key: {}", stock.begin()[1].first);

    for (auto [item, count] : stock) count += 10;  // each element is a pair of references into the two vectors
    std::println("after adding 10 to every count: {}", stock);

    std::flat_set<int> marks{72, 91, 64, 91};
    std::println("{}, first mark at least 70: {}", marks, *marks.lower_bound(70));
#ifdef __cpp_lib_flat_map
    std::println("__cpp_lib_flat_map is defined: this library has std::flat_map");
#endif
}
Both libraries, then a loop that does not compile Python · flat_basics_session.py 
from session import run

# flat_basics.cpp with both compilers and their standard libraries; then flat_proxy.cpp, which does not compile:
# grep keeps each compiler's first error, without the file and line in front.
run("""
clang++ -std=c++23 -Wall -Wextra flat_basics.cpp -o flat_basics && ./flat_basics
g++-16 -std=c++23 -Wall -Wextra flat_basics.cpp -o flat_basics-gcc && ./flat_basics-gcc
clang++ -std=c++23 -Wall -Wextra flat_proxy.cpp -o flat_proxy 2>&1 | grep -m1 -o "error: .*"
g++-16 -std=c++23 -Wall -Wextra flat_proxy.cpp -o flat_proxy-gcc 2>&1 | grep -m1 -o "error: .*"
""")

Output

$ clang++ -std=c++23 -Wall -Wextra flat_basics.cpp -o flat_basics && ./flat_basics
{"clips": 120, "paper": 500, "pens": 40}
keys ["clips", "paper", "pens"] and values [120, 500, 40]
paper: 500, at position 1
the second key: paper
after adding 10 to every count: {"clips": 130, "paper": 510, "pens": 50}
{64, 72, 91}, first mark at least 70: 72
__cpp_lib_flat_map is defined: this library has std::flat_map
$ g++-16 -std=c++23 -Wall -Wextra flat_basics.cpp -o flat_basics-gcc && ./flat_basics-gcc
{"clips": 120, "paper": 500, "pens": 40}
keys ["clips", "paper", "pens"] and values [120, 500, 40]
paper: 500, at position 1
the second key: paper
after adding 10 to every count: {"clips": 130, "paper": 510, "pens": 50}
{64, 72, 91}, first mark at least 70: 72
__cpp_lib_flat_map is defined: this library has std::flat_map
$ clang++ -std=c++23 -Wall -Wextra flat_proxy.cpp -o flat_proxy 2>&1 | grep -m1 -o "error: .*"
error: non-const lvalue reference to type '_If<...>' cannot bind to a temporary of type '_If<...>'
$ g++-16 -std=c++23 -Wall -Wextra flat_proxy.cpp -o flat_proxy-gcc 2>&1 | grep -m1 -o "error: .*"
error: cannot bind non-const lvalue reference of type 'std::pair<const std::__cxx11::basic_string<char>&, int&>&' to an rvalue of type 'std::_Flat_map_impl<std::__cxx11::basic_string<char>, int, std::less<std::__cxx11::basic_string<char> >, std::vector<std::__cxx11::basic_string<char>, std::allocator<std::__cxx11::basic_string<char> > >, std::vector<int, std::allocator<int> >, false>::_Iterator<false>::reference' {aka 'std::pair<const std::__cxx11::basic_string<char>&, int&>'}

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 flat_basics_session.py

Apple clang 21’s libc++ and GCC 16’s libstdc++ both ship <flat_map> and <flat_set>, and both define the feature-test macro __cpp_lib_flat_map, which code can check, after including <version>, before it relies on the header. The interface is the one you know from std::map and std::set: operator[], erase, find, lower_bound and printing with std::println worked unchanged. What is new shows in the output:

  • keys() and values() return the two vectors themselves, read-only: ["clips", "paper", "pens"] and [120, 500, 40]. Code that needs only the keys, or only the values, can use them directly.
  • The iterators are random access, as a vector’s are: it - stock.begin() gave the position of "paper", and stock.begin()[1] read the second element without walking.
  • There is no node and no pair object inside the map. Dereferencing an iterator builds a temporary std::pair<const std::string&, int&>, a pair of references into the two vectors.

That last point explains the two error messages. for (auto& [item, count] : stock) asks for a non-const reference to the temporary pair, which C++ does not allow, and both compilers refuse: Clang with “non-const lvalue reference … cannot bind to a temporary”, GCC naming the pair of references. Write for (auto [item, count] : stock), which copies the pair of references, so count still refers into the map and count += 10 changed the values; or const auto& to read, or auto&&. Code that switches from std::map to std::flat_map hits this error first.

A flat_map as two vectors: keys clips, paper, pens over values 120, 500, 40; inserting ink moves paper and pens up.beforeafter emplace("ink", 7)keys, sortedvalueskeys, sortedvaluesclipspaperpens12050040clipsinknewpapermovedpensmoved1207new500moved40moveda binary search finds position 1;every later key and value moves up

A flat_map is two vectors, and an insertion shifts both

Text description of the diagram

The diagram shows a std::flat_map from names to counts, before and after one insertion.

  1. Before: the keys vector holds clips, paper and pens, in sorted order. The values vector holds 120, 500 and 40, each at the same position as its key.
  2. emplace("ink", 7) finds the place for ink with a binary search: position 1, between clips and paper.
  3. After: the keys vector holds clips, ink, paper and pens, and the values vector holds 120, 7, 500 and 40. To make room, paper and pens moved up one place, and so did their values, 500 and 40.

Every insertion and erasure moves all the keys and values after its position, so it takes time linear in the size of the map.

What an insertion costs, and how to load in bulk

Every insertion into the middle shifts the later keys and values, and so does every erasure. That makes loading data one element at a time quadratic in the worst case. This program loads 20,000 pairs that arrive in random order in four ways:

build.cpp C++ · build.cpp 
// Loading 20,000 key-value pairs. Inserting into a flat_map one pair at a time shifts every later key and value up
// by one place; the range constructor appends everything, sorts once and removes duplicates; and when the data
// already arrives sorted, std::sorted_unique takes two vectors as they are, without sorting or checking anything.
// Times are the fastest of 7 runs; the count of shifted elements is computed, not timed.
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <flat_map>
#include <map>
#include <print>
#include <random>
#include <utility>
#include <vector>

using Clock = std::chrono::steady_clock;

long long check = 0;  // every load adds to it, so the optimiser cannot drop the work

template <class F>
double fastest_ms(F load) {
    double best = 1e300;
    for (int run = 0; run < 7; ++run) {
        auto start = Clock::now();
        check += load();
        std::chrono::duration<double, std::milli> took = Clock::now() - start;
        best = std::min(best, took.count());
    }
    return best;
}

int main() {
    const int n = 20'000;
    std::vector<std::pair<int, int>> rows;
    for (int i = 0; i < n; ++i) rows.emplace_back(i * 3, i);  // distinct keys
    std::mt19937 random(7);
    for (int i = n - 1; i > 0; --i) std::swap(rows[i], rows[random() % (i + 1)]);  // a shuffle every library repeats

    long long shifted = 0;
    double one = fastest_ms([&] {
        std::flat_map<int, int> fm;
        shifted = 0;
        for (auto [key, value] : rows) {
            shifted += fm.end() - fm.lower_bound(key);  // the elements that move up to make room
            fm.emplace(key, value);
        }
        return fm.size() + fm.begin()->second;
    });
    double range = fastest_ms([&] {
        std::flat_map<int, int> fm(rows.begin(), rows.end());
        return fm.size() + fm.begin()->second;
    });
    // Data that arrives sorted, for example from a file written in key order: two vectors, ready before the clock starts.
    auto sorted = rows;
    std::ranges::sort(sorted);
    std::vector<int> sorted_keys, sorted_values;
    for (auto [key, value] : sorted) {
        sorted_keys.push_back(key);
        sorted_values.push_back(value);
    }
    double presorted = fastest_ms([&] {
        auto keys = sorted_keys;  // copies, so that every run starts from the same input
        auto values = sorted_values;
        std::flat_map<int, int> fm(std::sorted_unique, std::move(keys), std::move(values));
        return fm.size() + fm.begin()->second;
    });
    double tree = fastest_ms([&] {
        std::map<int, int> m;
        for (auto [key, value] : rows) m.emplace(key, value);
        return m.size() + m.begin()->second;
    });

    std::println("{} pairs in random order:", n);
    std::println("  flat_map, one emplace at a time:  {:8.3f} ms, {} keys and as many values shifted", one, shifted);
    std::println("  flat_map, range constructor:      {:8.3f} ms", range);
    std::println("  std::map, one emplace at a time:  {:8.3f} ms", tree);
    std::println("the same pairs, already sorted:");
    std::println("  flat_map with std::sorted_unique: {:8.3f} ms, copying the two vectors included", presorted);
    std::println("check: {}", check);
}
Four ways to load 20,000 pairs Python · build_session.py 
from session import run

# build.cpp with -O2, with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra build.cpp -o build
./build
g++-16 -std=c++23 -O2 -Wall -Wextra build.cpp -o build-gcc
./build-gcc
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra build.cpp -o build
$ ./build
20000 pairs in random order:
  flat_map, one emplace at a time:    20.806 ms, 100388524 keys and as many values shifted
  flat_map, range constructor:         1.095 ms
  std::map, one emplace at a time:     3.203 ms
the same pairs, already sorted:
  flat_map with std::sorted_unique:    0.004 ms, copying the two vectors included
check: 560000
$ g++-16 -std=c++23 -O2 -Wall -Wextra build.cpp -o build-gcc
$ ./build-gcc
20000 pairs in random order:
  flat_map, one emplace at a time:    22.443 ms, 100388524 keys and as many values shifted
  flat_map, range constructor:         1.245 ms
  std::map, one emplace at a time:     3.394 ms
the same pairs, already sorted:
  flat_map with std::sorted_unique:    0.004 ms, copying the two vectors included
check: 560000

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 build_session.py

  • One emplace at a time shifted 100,388,524 keys, and as many values, with both libraries: about n²/4 for n insertions in random order, because each new key lands, on average, in the middle of the keys already stored. It was the slowest way to build either container.
  • The range constructor took a small fraction of that time. Like insert(first, last) and insert_range, it appends all the pairs, sorts them once and removes duplicates, and the standard puts the cost of those insertions at N + M log M for M new elements added to a map of N. Prefer them whenever you have the data at hand.
  • std::map, one at a time, sat between the two: every insertion is O(log n), but each allocates a node.
  • std::sorted_unique tells the map that the input is already sorted and free of duplicates. The map then takes the two vectors as they are, without sorting or even checking them, which is why loading 20,000 pairs that arrived sorted took a few microseconds: the time of copying two vectors.

The same rules hold for flat_set, with one container instead of two. To change many elements at once, take the containers out with std::move(fm).extract(), change them, and put them back with replace(keys, values), whose preconditions are the same as sorted_unique’s.

Memory and speed when the data is mostly read

The flat containers were designed for data that is read far more often than it changes. This program stores 50,000 names with an address each, as a symbol table, in a std::map and in a std::flat_map, and counts the bytes each one requests before timing lookups and a full pass:

read_heavy.cpp C++ · read_heavy.cpp 
// A symbol table that is built once and then only read: 50,000 names, each with an address, in a std::map and in a
// std::flat_map. The program counts the bytes each one asked the allocator for, then times lookups of names that are
// present and a full pass over all values. Each round times both containers, one after the other, and the output
// shows the fastest of 15 rounds.
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <flat_map>
#include <format>
#include <functional>
#include <map>
#include <new>
#include <print>
#include <random>
#include <string>
#include <utility>
#include <vector>

inline std::size_t bytes = 0;  // bytes allocated and not yet freed, through Counting

template <class T>
struct Counting {
    using value_type = T;
    Counting() = default;
    template <class U>
    Counting(const Counting<U>&) noexcept {}
    T* allocate(std::size_t n) {
        bytes += n * sizeof(T);
        if (void* p = std::malloc(n * sizeof(T))) return static_cast<T*>(p);
        throw std::bad_alloc{};
    }
    void deallocate(T* p, std::size_t n) noexcept {
        bytes -= n * sizeof(T);
        std::free(p);
    }
    friend bool operator==(Counting, Counting) { return true; }
};

using Address = std::uint32_t;
using Tree = std::map<std::string, Address, std::less<>, Counting<std::pair<const std::string, Address>>>;
using Flat = std::flat_map<std::string, Address, std::less<>, std::vector<std::string, Counting<std::string>>,
                           std::vector<Address, Counting<Address>>>;
using Clock = std::chrono::steady_clock;

template <class F>
double time_ms(F work, long long& check) {
    auto start = Clock::now();
    check += work();
    std::chrono::duration<double, std::milli> took = Clock::now() - start;
    return took.count();
}

int main() {
    const int n = 50'000;
    std::vector<std::pair<std::string, Address>> symbols;
    for (int i = 0; i < n; ++i) symbols.emplace_back(std::format("fn_{:06}", (i * 7919) % 1'000'000), Address(i * 16));

    bytes = 0;
    Tree tree(symbols.begin(), symbols.end());
    std::size_t tree_bytes = bytes;
    bytes = 0;
    Flat flat(symbols.begin(), symbols.end());
    std::size_t flat_bytes = bytes;
    std::println("{} names of {} characters, sizeof(std::string) = {}", n, symbols[0].first.size(), sizeof(std::string));
    std::println("std::map:      {:>8} bytes, {:.1f} per entry", tree_bytes, double(tree_bytes) / n);
    std::println("std::flat_map: {:>8} bytes, {:.1f} per entry", flat_bytes, double(flat_bytes) / n);

    std::mt19937 random(5);
    std::vector<std::string> queries;
    for (int i = 0; i < 16'384; ++i) queries.push_back(symbols[random() % n].first);
    long long check = 0;
    double tree_find = 1e300, flat_find = 1e300, tree_scan = 1e300, flat_scan = 1e300;
    for (int round = 0; round < 15; ++round) {
        tree_find = std::min(tree_find, time_ms([&] { long long s = 0; for (const auto& q : queries) s += tree.find(q)->second; return s; }, check));
        flat_find = std::min(flat_find, time_ms([&] { long long s = 0; for (const auto& q : queries) s += flat.find(q)->second; return s; }, check));
        tree_scan = std::min(tree_scan, time_ms([&] { long long s = 0; for (const auto& [name, address] : tree) s += address; return s; }, check));
        flat_scan = std::min(flat_scan, time_ms([&] { long long s = 0; for (Address a : flat.values()) s += a; return s; }, check));
    }
    const double per_lookup = 1e6 / double(queries.size());  // milliseconds for all queries -> nanoseconds per query
    std::println("one lookup:     std::map {:7.1f} ns, std::flat_map {:7.1f} ns", tree_find * per_lookup, flat_find * per_lookup);
    std::println("one full pass:  std::map {:7.3f} ms, std::flat_map {:7.3f} ms", tree_scan, flat_scan);
    std::println("check: {}", check);
}
A read-only symbol table in std::map and in std::flat_map Python · read_heavy_session.py 
from session import run

# read_heavy.cpp with -O2, with each compiler and its standard library.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra read_heavy.cpp -o read_heavy
./read_heavy
g++-16 -std=c++23 -O2 -Wall -Wextra read_heavy.cpp -o read_heavy-gcc
./read_heavy-gcc
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra read_heavy.cpp -o read_heavy
$ ./read_heavy
50000 names of 9 characters, sizeof(std::string) = 24
std::map:       3200000 bytes, 64.0 per entry
std::flat_map:  1400000 bytes, 28.0 per entry
one lookup:     std::map   247.8 ns, std::flat_map   195.2 ns
one full pass:  std::map   0.810 ms, std::flat_map   0.005 ms
check: 796278449280
$ g++-16 -std=c++23 -O2 -Wall -Wextra read_heavy.cpp -o read_heavy-gcc
$ ./read_heavy-gcc
50000 names of 9 characters, sizeof(std::string) = 32
std::map:       3600000 bytes, 72.0 per entry
std::flat_map:  2359296 bytes, 47.2 per entry
one lookup:     std::map   293.7 ns, std::flat_map   190.6 ns
one full pass:  std::map   0.777 ms, std::flat_map   0.020 ms
check: 796278449280

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 read_heavy_session.py

  • Memory. With libc++, the std::map requested 64 bytes per entry: a 24-byte string and a 4-byte address, plus the node’s three pointers and colour, padded. The flat_map requested 28, exactly the string and the address, because libc++’s range constructor reserved the right size. With libstdc++ the strings are 32 bytes, the map needed 72 bytes per entry, and the flat_map 47.2: its vectors grew by doubling to room for 65,536 entries. The map also made one allocation per entry, while the flat_map allocated only its two vectors, a few times over while they grew.
  • Lookups. flat_map answered each lookup faster with both compilers, though not by a large factor: both containers compare the name with about 16 others, the base-2 logarithm of 50,000, and the flat version saves mostly the jumps from node to node.
  • A full pass over the values was at least 30 times faster with flat_map, because values() is one vector, which the processor reads at full speed, while the map’s pass visits 50,000 nodes scattered in memory.

The trade-offs are the ones the first lesson of this module listed: a std::map keeps its iterators and references valid while it changes and inserts in O(log n), while a flat container invalidates them on every insertion or erasure, and inserts in O(n). The standard says it plainly: the flat containers do not meet the associative containers’ requirements on iterator invalidation.

Two promises to keep

Bulk loading is fast because the flat containers trust you. Two programs show what happens when the trust is misplaced:

broken_promise.cpp C++ · broken_promise.cpp 
// std::sorted_unique is a promise that the keys are sorted and contain no duplicates. Nothing checks it in an
// ordinary build, and a false promise is undefined behaviour: here the keys are not sorted, so binary searches
// look in the wrong half.
#include <flat_map>
#include <print>
#include <vector>

int main() {
    std::vector<int> keys{10, 30, 20, 40};  // not sorted
    std::vector<int> values{1, 3, 2, 4};
    std::flat_map<int, int> m(std::sorted_unique, std::move(keys), std::move(values));
    std::println("{}", m);
    std::println("contains(20): {}, contains(30): {}", m.contains(20), m.contains(30));
}
duplicates.cpp C++ · duplicates.cpp 
// Which value survives when the input repeats a key? std::map's range constructor inserts the pairs in order and
// keeps the first value of each key. flat_map's range constructor sorts the pairs by key, and that sort does not
// have to keep equal keys in their input order, so the value it keeps is not necessarily the first.
#include <cstddef>
#include <flat_map>
#include <map>
#include <print>
#include <random>
#include <utility>
#include <vector>

int main() {
    std::vector<std::pair<int, int>> few{{1, 10}, {2, 20}, {1, 11}, {3, 30}, {1, 12}, {2, 21}};
    std::println("six pairs: std::map {}, std::flat_map {}",
                 std::map<int, int>(few.begin(), few.end()), std::flat_map<int, int>(few.begin(), few.end()));

    // 2,000 pairs with 100 different keys; each value is the pair's position, so the first value is the smallest.
    std::mt19937 random(1);
    std::vector<std::pair<int, int>> rows;
    for (int i = 0; i < 2000; ++i) rows.emplace_back(int(random() % 100), i);
    std::map<int, int> tree(rows.begin(), rows.end());
    std::flat_map<int, int> flat(rows.begin(), rows.end());
    std::size_t different = 0;
    for (auto [key, value] : tree)
        if (flat.at(key) != value) ++different;
    std::println("2000 pairs, 100 keys: the flat_map kept another value than the first for {} keys", different);
}
A false sorted_unique, then duplicates in the input Python · promises_session.py 
from session import run

# broken_promise.cpp in an ordinary build, then in each library's debug mode, which checks the promise; grep keeps
# the line that names the problem. Then duplicates.cpp with both libraries.
run("""
clang++ -std=c++23 -Wall -Wextra broken_promise.cpp -o broken_promise && ./broken_promise
clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG broken_promise.cpp -o broken_promise-debug
./broken_promise-debug 2>&1 | grep -o "libc++ Hardening assertion.*"
g++-16 -std=c++23 -D_GLIBCXX_DEBUG broken_promise.cpp -o broken_promise-gcc-debug
./broken_promise-gcc-debug 2>&1 | grep -o "Assertion .*"
clang++ -std=c++23 -O2 -Wall -Wextra duplicates.cpp -o duplicates && ./duplicates
g++-16 -std=c++23 -O2 -Wall -Wextra duplicates.cpp -o duplicates-gcc && ./duplicates-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra broken_promise.cpp -o broken_promise && ./broken_promise
{10: 1, 30: 3, 20: 2, 40: 4}
contains(20): false, contains(30): false
$ clang++ -std=c++23 -D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG broken_promise.cpp -o broken_promise-debug
$ ./broken_promise-debug 2>&1 | grep -o "libc++ Hardening assertion.*"
libc++ Hardening assertion __is_sorted_and_unique(__containers_.keys) failed: Either the key container is not sorted or it contains duplicates
$ g++-16 -std=c++23 -D_GLIBCXX_DEBUG broken_promise.cpp -o broken_promise-gcc-debug
$ ./broken_promise-gcc-debug 2>&1 | grep -o "Assertion .*"
Assertion 'ranges::is_sorted(_M_cont.keys, _M_comp)' failed.
$ clang++ -std=c++23 -O2 -Wall -Wextra duplicates.cpp -o duplicates && ./duplicates
six pairs: std::map {1: 10, 2: 20, 3: 30}, std::flat_map {1: 10, 2: 20, 3: 30}
2000 pairs, 100 keys: the flat_map kept another value than the first for 95 keys
$ g++-16 -std=c++23 -O2 -Wall -Wextra duplicates.cpp -o duplicates-gcc && ./duplicates-gcc
six pairs: std::map {1: 10, 2: 20, 3: 30}, std::flat_map {1: 10, 2: 20, 3: 30}
2000 pairs, 100 keys: the flat_map kept another value than the first for 93 keys

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 promises_session.py

  • std::sorted_unique must be true. The keys 10, 30, 20, 40 are not sorted, and the ordinary build accepted them. The map then printed its keys out of order and could find neither 20 nor 30, although both were there: every binary search assumed an order that did not exist. The standard makes this undefined behaviour. Both debug modes check the promise: libc++’s says “Either the key container is not sorted or it contains duplicates”, and libstdc++’s fails an is_sorted assertion.
  • The range constructor keeps one value per key, but not necessarily the first. For six pairs, both containers kept the first value of each key. For 2,000 pairs with 100 keys, the flat_map kept another value than the first for 95 keys with libc++ and 93 with libstdc++. std::map inserts the pairs one after another and refuses a key it already has, so it always keeps the first; the flat containers sort the pairs, and the standard does not require that sort to keep equal keys in their input order.

When the input can repeat a key and it matters which value wins, decide it yourself before the map sees the data, which is the exercise below.

Your turn: a read-only symbol table

Write build_symbol_table(rows), which builds a std::flat_map from name to address. The rows arrive in any order, and when a name appears in several rows, the table keeps the address of its first row. Then write address_of, which returns the address of a name, or std::nullopt.

The starter code and its sample tests

C header · symbols.h 

// Starter code for "Your turn": a read-only symbol table, built once from rows that arrive in any order, then only
// read. When a name appears in several rows, the table keeps the address of its first row.
#pragma once
#include <cstdint>
#include <flat_map>
#include <optional>
#include <string>
#include <utility>
#include <vector>

using SymbolTable = std::flat_map<std::string, std::uint64_t>;

inline SymbolTable build_symbol_table(std::vector<std::pair<std::string, std::uint64_t>> rows) {
    // TODO: sort the rows by name, keeping equal names in their input order, keep the first row of each name, and
    // hand the two vectors to the table with std::sorted_unique
    (void)rows;
    return {};
}

inline std::optional<std::uint64_t> address_of(const SymbolTable& table, const std::string& name) {
    // TODO
    (void)table;
    (void)name;
    return std::nullopt;
}

C++ · symbols_tests.cpp 

// Sample tests for symbols.h. Build: clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra symbols_tests.cpp -o symbols_tests
#include <cstdint>
#include <format>
#include <map>
#include <optional>
#include <print>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "symbols.h"

int checks = 0;
int failures = 0;

void check(bool ok, const char* what) {
    ++checks;
    if (!ok) {
        ++failures;
        std::println("FAIL {}", what);
    }
}

int main() {
    SymbolTable t = build_symbol_table({{"main", 0x1000}, {"init", 0x2000}, {"exit", 0x3000}, {"init", 0x4000}});
    check(t.size() == 3, "three different names");
    check(t.keys() == std::vector<std::string>{"exit", "init", "main"}, "the names are sorted");
    check(address_of(t, "init") == 0x2000, "a repeated name keeps the address of its first row");
    check(address_of(t, "main") == 0x1000, "a name that appears once");
    check(!address_of(t, "free").has_value(), "a missing name");
    check(build_symbol_table({}).empty(), "no rows, an empty table");

    // 20,000 rows with 2,000 different names, compared with a std::map that keeps the first row of each name.
    std::mt19937 random(4);
    std::vector<std::pair<std::string, std::uint64_t>> rows;
    std::map<std::string, std::uint64_t> expected;
    for (std::uint64_t i = 0; i < 20'000; ++i) {
        std::string name = std::format("sym{}", random() % 2'000);
        rows.emplace_back(name, i);
        expected.try_emplace(name, i);
    }
    SymbolTable big = build_symbol_table(rows);
    bool same = big.size() == expected.size();
    for (const auto& [name, address] : expected) same = same && address_of(big, name) == address;
    check(same, "20,000 rows: every name keeps the address of its first row");

    std::println("{} of {} checks passed", checks - failures, checks);
    return failures == 0 ? 0 : 1;
}
The sample tests against the starter code Python · symbols_session.py 
from session import run

# The sample tests run against the starter code, before any TODO is done, with the sanitizers switched on.
run("""
clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra symbols_tests.cpp -o symbols_tests && ./symbols_tests
g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra symbols_tests.cpp -o symbols_tests-gcc && ./symbols_tests-gcc
""")

Output

$ clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra symbols_tests.cpp -o symbols_tests && ./symbols_tests
FAIL three different names
FAIL the names are sorted
FAIL a repeated name keeps the address of its first row
FAIL a name that appears once
FAIL 20,000 rows: every name keeps the address of its first row
2 of 7 checks passed
[exit status 1]
$ g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra symbols_tests.cpp -o symbols_tests-gcc && ./symbols_tests-gcc
FAIL three different names
FAIL the names are sorted
FAIL a repeated name keeps the address of its first row
FAIL a name that appears once
FAIL 20,000 rows: every name keeps the address of its first row
2 of 7 checks passed
[exit status 1]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 symbols_session.py

You are done when both compilers print 7 of 7 checks passed. Hints: std::ranges::stable_sort with the projection &std::pair<std::string, std::uint64_t>::first sorts the rows by name and keeps equal names in their input order; then copy the first row of each name into two vectors and hand them to the table with std::sorted_unique. Passing the rows straight to the range constructor passes every check but the last, which compares 20,000 rows with a std::map that keeps each first row.

Check yourself

6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 6 How does a std::flat_map<K, V> store its elements by default?

    Choose one answer.

    Show the answer

    Answer: In two std::vectors, the keys sorted and each value at the same position as its key

    The keys and the values live in two separate sequence containers, std::vector unless you choose others. keys() and values() return them, and a binary search over the keys finds the position of the value.

  2. Question 2 of 6 What does inserting one new key into a std::flat_map of n elements cost?

    Choose one answer.

    Show the answer

    Answer: O(n), because every later key and value moves up one place

    Finding the place is a binary search, O(log n), but making room shifts the rest of both vectors. Inserting 20,000 keys in random order one at a time shifted about 100 million keys and as many values.

  3. Question 3 of 6 Why does for (auto& [key, value] : fm) not compile for a std::flat_map fm?

    Choose one answer.

    Show the answer

    Answer: Dereferencing an iterator returns a temporary pair of references, and auto& cannot bind to a temporary

    No pair object exists to refer to, because keys and values are in separate vectors. auto [key, value] copies the pair of references, so value still refers into the map, and const auto& or auto&& work too.

  4. Question 4 of 6 A file delivers 1,000,000 rows already sorted by key, without duplicates. What is the fastest correct way to build a std::flat_map from it?

    Choose one answer.

    Show the answer

    Answer: Read the keys and values into two vectors and move them into the map with std::sorted_unique

    With std::sorted_unique the map takes the two vectors as they are: no sort, no shifting, not even a check in an ordinary build. The range constructor would work, but it sorts again, and emplacing one row at a time shifts elements on every insertion unless each new key is the largest.

  5. Question 5 of 6 Rows repeat some keys, and the map must keep the first value of each. Which approach does that with every standard library?

    Choose one answer.

    Show the answer

    Answer: std::ranges::stable_sort by key, keep the first row of each key, then build the map with std::sorted_unique

    The range constructor and insert(first, last) sort without promising to keep equal keys in input order, and in the lesson's run they kept a later value for 95 and 93 of 100 keys. stable_sort keeps the input order of equal keys, so the first row of each key is first in its run. sorted_unique on unsorted rows is undefined behaviour.

  6. Question 6 of 6 When is a std::flat_map a better choice than a std::map?

    Choose every answer that is right.

    Show the answer

    Answer:

    • Memory per element matters
    • The program often walks over every element
    • The map is built once and then mostly read

    Contiguous storage makes lookups and full passes faster and saves the node overhead of every element. Each insertion or erasure, though, shifts elements and invalidates iterators and references into the map, which a std::map never does to the elements it keeps.

Interview questions

Fresher · What is std::flat_map, and when would you choose it over std::map?

std::flat_map (C++23) is a sorted associative container with the interface of std::map, built on two sorted sequence containers, by default vectors: one holds the keys and the other the values at the same positions. Lookups are binary searches over contiguous memory, iteration is as fast as over a vector, and there is no per-element node, so it uses much less memory. But inserting or erasing a key shifts the later elements, which takes linear time, and invalidates iterators and references into the map. Choose it for data that is built once, or changed rarely and in bulk, and then read many times, such as a lookup table loaded at start-up. Keep std::map when keys are inserted and erased all the time, or when other code holds references to elements while the map changes.

Key takeaways

  • A flat_map is two sorted vectors, keys and values, with the interface of std::map; a flat_set is one. Both ship with Apple clang 21’s libc++ and with GCC 16.
  • Lookups are O(log n) binary searches over contiguous memory, and a full pass is as fast as a vector’s; one insertion or erasure is O(n) and invalidates iterators and references.
  • Its iterators return a temporary pair of references, so loop with auto [k, v], const auto& or auto&&, never auto&.
  • Load in bulk: inserting 20,000 keys one at a time shifted about 100 million elements, while the range constructor sorts once, and std::sorted_unique takes data that is already sorted as it is.
  • sorted_unique is a promise nobody checks outside the debug modes, and the range constructor may keep any of several values for a repeated key: with 2,000 rows, 95 of 100 keys kept a later value with libc++.

References

Report a problem with this lesson