Why C++23’s std::flat_map and std::flat_set Boost Performance and Cache Locality

C++23 introduces two new associative containers— std::flat_map and std::flat_set —designed to provide higher performance and better cache locality.

Flat containers are “flat” because they are implemented on top of sequential containers such as std::vector, unlike traditional std::map and std::set which use balanced binary trees.

The main motivation is cache‑friendliness; for small‑to‑medium sized collections, cache locality often outweighs theoretical asymptotic complexity (O(N) vs O(log N)).

Core advantages:

Memory is contiguous → improved CPU cache hit rate.

Faster traversal and lookup for small data sets.

Smaller memory footprint, no node pointers.

Drawbacks:

Insertion and deletion require element moves → O(N) cost.

Iterators become invalid after insertions or deletions.

Unsuitable for scenarios with frequent modifications.

Below is a simple example demonstrating std::flat_set usage:

#include <flat_set>
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // Construction: automatically deduplicate and sort
    std::flat_set<int> nums{7, 3, 9, 3, 5}; // => {3,5,7,9}
    // Insert new element (returns pair<iterator,bool>)
    auto [it, ok] = nums.insert(4);
    if (ok) std::cout << "Insert 4 succeeded
";
    // Emplace element
    nums.emplace(8);
    // Insert a range (C++23 insert_range)
    std::vector<int> extra{1,2,3};
    nums.insert_range(extra); // auto‑sort and dedup
    // Find and access
    if (nums.contains(5)) std::cout << "Found 5
";
    auto lb = nums.lower_bound(4);
    std::cout << "lower_bound(4): " << *lb << "
";
    // Random access via iterator
    std::cout << "All elements: ";
    for (size_t i = 0; i < nums.size(); ++i) std::cout << nums.begin()[i] << " ";
    std::cout << "
";
    // Erase elements
    nums.erase(3);
    nums.erase(nums.find(9));
    std::cout << "After erase: ";
    for (auto v : nums) std::cout << v << " ";
    std::cout << "
";
    // Extract underlying container (C++23)
    auto backing = std::move(nums).extract();
    std::cout << "Backing size: " << backing.size()
              << ", nums empty: " << std::boolalpha << nums.empty() << "
";
}

In this code you can access elements directly with [] or begin()+n.

Another example shows std::flat_map built on std::vector<std::pair<K,V>>:

#include <flat_map>
#include <iostream>
#include <string>
#include <cassert>

int main() {
    std::flat_map<int, std::string> dict{{1, "one"}, {3, "three"}, {2, "two"}};
    // Insert or update
    dict.emplace(4, "four");
    dict.insert_or_assign(2, "TWO");
    // Access
    std::cout << "dict[3] = " << dict[3] << "
";
    std::cout << "dict.at(2) = " << dict.at(2) << "
";
    // Iterate
    std::cout << "
All key‑value pairs:
";
    for (const auto& [k, v] : dict) std::cout << k << " -> " << v << "
";
    // C++23 keys() / values()
    const auto& keys = dict.keys();
    const auto& vals = dict.values();
    std::cout << "
Access via keys()/values():
";
    for (size_t i = 0; i < keys.size(); ++i)
        std::cout << keys[i] << " => " << vals[i] << "
";
    assert(std::is_sorted(keys.begin(), keys.end()));
}