Mastering std::flat_map and std::flat_set in C++23

The std::flat_map and std::flat_set containers, introduced in C++23, were primarily added to provide associative containers that offer better performance and memory locality for specific use cases compared to their traditional counterparts, std::map and std::set

What are std::flat_map and std::flat_set?

Unlike std::map and std::set which are typically implemented as balanced binary search trees (e.g., red-black trees), and std::unordered_map/std::unordered_set which use hash tables, **std::flat_map and std::flat_set are container adaptors built on top of sequence containers, most commonly std::vector.**

The main reason for their introduction is cache-friendliness. In real-world performance, cache locality often matters more than theoretical asymptotic complexity (O(N) vs. O(logN)), especially for containers with a small to medium number of elements.

std::flat_set and std::flat_map are designed to feel very much like their traditional counterparts(std::set, std::map), but their contiguous memory layout gives them the capability for random access and changes the performance characteristics of deletion.

Lets check usage with detailed example:-

// g++ -std=c++23 flat_set_demo.cpp && ./a.out
#include <flat_set>     // C++23
#include <iostream>
#include <string>
#include <typeinfo>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

int main() {
    // 1) CONSTRUCTION
    std::flat_set<int> s1;                               // default
    std::flat_set<int> s2{ 7, 3, 9, 3, 5 };              // dedup + sort -> {3,5,7,9}
    std::flat_set<int> s3(s2.begin(), s2.end());         // range
    std::flat_set<int> s4 = s3;                          // copy
    std::flat_set<int> s5 = std::move(s4);               // move

    // 2) INSERT / EMPLACE / INSERT WITH HINT / INSERT_RANGE (C++23)
    // insert → pair<iterator,bool>
    auto [it1, ok1] = s1.insert(4);
    auto [it2, ok2] = s1.insert(2);
    auto [it3, ok3] = s1.insert(4); // duplicate → ok3=false

    // emplace → pair<iterator,bool>
    auto [eit, eok] = s1.emplace(8);

    // insert with hint (iterator) - can be ignored, but may help
    auto it_hint = s1.insert(s1.begin(), 6);

    // insert_range (C++23) - inserts a whole range
    std::vector<int> more{1, 3, 5, 7, 9};
    s1.insert_range(more); // {1,2,3,4,5,6,7,8,9}

    // 3) ELEMENT/LOOKUP - find / count / contains (C++23 for flat_set)
    if (auto it = s1.find(7); it != s1.end())
        cout << "found 7 at index " << (it - s1.begin()) << '\n';

    cout << "count(7) = " << s1.count(7) << " (set semantics → 0 or 1)\n";
    cout << boolalpha << "contains(10)? " << s1.contains(10) << '\n';   // C++23

    // 4) BOUNDS - lower/upper/equal_range
    auto lb = s1.lower_bound(4);  // first not less than 4
    auto ub = s1.upper_bound(4);  // first greater than 4
    auto [lb2, ub2] = s1.equal_range(4);
    cout << "lower_bound(4): " << (lb != s1.end() ? *lb : -1) << '\n';
    cout << "upper_bound(4): " << (ub != s1.end() ? *ub : -1) << '\n';
    cout << "equal_range(4): [" 
         << (lb2 != s1.end() ? *lb2 : -1) << ", "
         << (ub2 != s1.end() ? *ub2 : -1) << ")\n";

    // 5) RANDOM-ACCESS ITERATION (flat containers have random-access iterators)
    cout << "\ns1 (indexing with begin()+i): ";
    for (ptrdiff_t i = 0; i < static_cast<ptrdiff_t>(s1.size()); ++i)
        cout << *(s1.begin() + i) << (i + 1 == s1.size() ? '\n' : ' ');

    // 6) ERASE
    s1.erase(3);                     // by key
    if (auto it = s1.find(5); it != s1.end())
        s1.erase(it);                // by iterator
    // by range
    if (auto itA = s1.lower_bound(8); itA != s1.end())
        s1.erase(itA, s1.end());

    cout << "after erase: ";
    for (int v : s1) cout << v << ' ';
    cout << '\n';

    // 7) OBSERVERS - key_comp / value_comp
    auto kc = s1.key_comp();
    auto vc = s1.value_comp();
    cout << boolalpha
         << "key_comp(2,4): " << kc(2,4) << ", value_comp(4,2): " << vc(4,2) << '\n';

    // 8) EXTRACT (C++23) - move out the UNDERLYING CONTIGUOUS CONTAINER
    //    After extracting, s1 becomes empty. The returned container is typically std::vector<int>.
    auto backing = std::move(s1).extract(); // container_type (e.g., std::vector<int>)
    cout << "extracted backing.size() = " << backing.size()
         << ", s1.empty() = " << s1.empty() << '\n';

    // Because it's a real vector, you can use data() / operator[] directly
    if (!backing.empty()) {
        cout << "backing[0] = " << backing[0] << ", *data() = " << *backing.data() << '\n';
    }

    // 9) REPLACE (C++23) - replace underlying container (must be sorted & unique!)
    std::vector<int> fresh{ 10, 20, 30, 40 }; // already sorted and unique
    // std::flat_set requires the replacement to be sorted_unique, or UB.
    s1.replace(std::move(fresh));
    cout << "after replace: ";
    for (int v : s1) cout << v << ' ';
    cout << '\n';

    // 10) CAPACITY / UTILITIES
    cout << "size=" << s1.size() << ", empty=" << s1.empty() << '\n';
    s1.clear();
    cout << "after clear(), size=" << s1.size() << '\n';

    // 11) RETURN-TYPE CHECKS (platform-specific mangled names, but useful)
    std::flat_set<int> demo{1,2,3};
    cout << "\nReturn type checks (mangled):\n";
    cout << "insert:      " << typeid(demo.insert(4)).name() << '\n';      // pair<iterator,bool>
    cout << "emplace:     " << typeid(demo.emplace(5)).name() << '\n';     // pair<iterator,bool>
    cout << "find:        " << typeid(demo.find(2)).name() << '\n';        // iterator
    cout << "equal_range: " << typeid(demo.equal_range(2)).name() << '\n'; // pair<it,it>

    // 12) SANITY: ordering + uniqueness
    assert(std::is_sorted(demo.begin(), demo.end()));
    demo.insert(2); // duplicate ignored
    assert(demo.count(2) == 1);

    cout << "\nAll good.\n";
}

OUTPUT:-

found 7 at index 6
count(7) = 1 (set semantics → 0 or 1)
contains(10)? false
lower_bound(4): 4
upper_bound(4): 5
equal_range(4): [4, 5)

s1 (indexing with begin()+i): 1 2 3 4 5 6 7 8 9
after erase: 1 2 4 6 7 
key_comp(2,4): true, value_comp(4,2): false
extracted backing.size() = 5, s1.empty() = true
backing[0] = 1, *data() = 1
after replace: 10 20 30 40 
size=4, empty=false
after clear(), size=0

Return type checks (mangled):
insert:      St4pairIN9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEbEE
emplace:     St4pairIN9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEbEE
find:        N9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEE
equal_range: St4pairIN9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEEESF_E

All good.

// g++ -std=c++23 flat_map_demo.cpp && ./a.out
#include <flat_map>   // C++23 header
#include <iostream>
#include <string>
#include <typeinfo>
#include <vector>
#include <cassert>

using namespace std;

int main() {
    // 1️CONSTRUCTION
    std::flat_map<int, std::string> fm1;                             // Default constructor
    std::flat_map<int, std::string> fm2 = {{1, "one"}, {2, "two"}};  // Initializer list
    std::flat_map<int, std::string> fm3(fm2.begin(), fm2.end());     // Range constructor

    // 2️INSERTION
    auto [it1, inserted1] = fm1.insert({3, "three"}); // returns pair<iterator,bool>
    fm1.insert_or_assign(4, "four");                  // inserts or assigns
    fm1.insert_or_assign(4, "FOUR");                  // overwrites "four"
    fm1.emplace(5, "five");                           // constructs in place
    fm1.insert(fm2.begin(), fm2.end());               // range insertion

    // 3️ELEMENT ACCESS
    cout << "fm1[3] = " << fm1[3] << endl;            // operator[] inserts default if not found
    cout << "fm1.at(2) = " << fm1.at(2) << endl;      // throws out_of_range if missing

    // 4️ITERATION
    cout << "\nIterating full flat_map:\n";
    for (const auto& [k, v] : fm1)
        cout << k << " -> " << v << '\n';

    // 5️LOOKUP FUNCTIONS
    if (auto it = fm1.find(4); it != fm1.end())
        cout << "Found key 4 -> " << it->second << '\n';

    cout << "count(2): " << fm1.count(2) << '\n';
    auto lb = fm1.lower_bound(3);
    cout << "lower_bound(3): " << (lb != fm1.end() ? to_string(lb->first) : "end") << '\n';
    auto ub = fm1.upper_bound(3);
    cout << "upper_bound(3): " << (ub != fm1.end() ? to_string(ub->first) : "end") << '\n';

    auto [lb2, ub2] = fm1.equal_range(3);
    cout << "equal_range(3): ["
         << (lb2 != fm1.end() ? to_string(lb2->first) : "end") << ", "
         << (ub2 != fm1.end() ? to_string(ub2->first) : "end") << ")\n";

    // 6️NEW IN C++23 — KEYS() and VALUES()
    // These provide direct access to underlying sorted vectors (contiguous memory)
    const auto& key_view = fm1.keys();     // returns const reference to underlying keys container
    const auto& value_view = fm1.values(); // returns const reference to underlying values container

    cout << "\nAccessing via keys() and values():\n";
    for (size_t i = 0; i < key_view.size(); ++i)
        cout << "key[" << i << "]=" << key_view[i]
             << ", value[" << i << "]=" << value_view[i] << '\n';

    // Direct contiguous access (like std::vector)
    cout << "First key via data(): " << key_view.data()[0] << '\n';
    cout << "First value via data(): " << value_view.data()[0] << '\n';

    // 7️ERASE / MODIFY
    fm1.erase(2); // erase by key
    fm1.erase(fm1.find(3)); // erase by iterator

    cout << "\nAfter erase:\n";
    for (auto& [k, v] : fm1) cout << k << " -> " << v << '\n';

    // 8️MERGE AND EXTRACT
    std::flat_map<int, std::string> fmA = {{1, "A"}, {2, "B"}};
    std::flat_map<int, std::string> fmB = {{2, "two"}, {3, "three"}};
    fmA.merge(fmB); // moves non-duplicate keys from fmB
    cout << "\nAfter merge fmA:\n";
    for (auto& [k, v] : fmA) cout << k << " -> " << v << '\n';

    auto node = fmA.extract(1); // returns node_type
    cout << "Extracted node key: " << node.key()
         << ", value: " << node.mapped() << '\n';
    fmB.insert(std::move(node));

    // 9️OBSERVERS
    auto kc = fmA.key_comp();
    cout << "key_comp(1,2): " << kc(1, 2) << '\n';

    // 10 COMPARISONS
    cout << boolalpha;
    cout << "fmA == fmB? " << (fmA == fmB) << '\n';
    cout << "fmA < fmB? " << (fmA < fmB) << '\n';

    // 11 RETURN TYPE CHECKS (typeid output)
    cout << "\nReturn type checks:\n";
    cout << "insert(): " << typeid(fm1.insert({10, "ten"})).name() << '\n';
    cout << "find(): " << typeid(fm1.find(1)).name() << '\n';
    cout << "equal_range(): " << typeid(fm1.equal_range(1)).name() << '\n';
    cout << "keys(): " << typeid(fm1.keys()).name() << '\n';
    cout << "values(): " << typeid(fm1.values()).name() << '\n';

    // 12 CHECK CONTIGUITY
    assert(std::is_sorted(key_view.begin(), key_view.end()));
    cout << "\nKeys and values are contiguous and sorted.\n";

    return 0;
}

OUTPUT:-

fm1[3] = three
fm1.at(2) = two

Iterating full flat_map:
1 -> one
2 -> two
3 -> three
4 -> FOUR
5 -> five

Found key 4 -> FOUR
count(2): 1
lower_bound(3): 3
upper_bound(3): 4
equal_range(3): [3, 4)

Accessing via keys() and values():
key[0]=1, value[0]=one
key[1]=2, value[1]=two
key[2]=3, value[2]=three
key[3]=4, value[3]=FOUR
key[4]=5, value[4]=five
First key via data(): 1
First value via data(): one

After erase:
1 -> one
4 -> FOUR
5 -> five

After merge fmA:
1 -> A
2 -> B
3 -> three
Extracted node key: 1, value: A
key_comp(1,2): true
fmA == fmB? false
fmA < fmB? true

Return type checks:
insert(): St4pairIN9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEbEE
find(): N9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEE
equal_range(): St4pairIN9__gnu_cxx17__normal_iteratorIPKSt4pairIKiSsESt9flat_mapIiSsSt4lessIiESaISt4pairIKiSsEEEEESF_E
keys(): RKSt6vectorIiSaIiEE
values(): RKSt6vectorISsSaISsEE

Keys and values are contiguous and sorted.

Where Traditional std::map / std::set Excel, Where std::flat_map/std::flat_set

1. std::flat_map: The Configuration Manager (Read-Heavy)

• Use Case: Storing application-wide configuration parameters (e.g., {"Timeout": 5000, "MaxRetries": 3, "LogLevel": "INFO"}).

Why std::flat_map is better:

• Fixed Size: Configuration maps are typically small and loaded once at startup.
• High Read Frequency: Parameters are read many times throughout the application’s runtime.
• Benefit: The contiguous memory ensures lookups are cache-friendly, making repeated reads significantly faster than traversing the pointers of a tree-based std::map.

2. std::flat_set: The Permissions Validator (Static Lookups)

• Use Case: Storing a static set of user permissions (e.g., {"ADMIN", "VIEW_LOGS", "EDIT_PROFILE"}) that needs fast validation checks.

Why std::flat_set is better:

• Membership Test: The primary operation is contains(permission), which uses a fast binary search (O(logN)) on a contiguous block of memory.
• Memory Efficiency: It requires less memory than a std::set because it avoids the pointer and node overhead, which is excellent for a small, non-changing list.

3. std::map: The Dynamic Cache/Registry (Write-Heavy)

• Use Case: Implementing a dynamic lookup registry where components register and unregister frequently, such as a connection pool or event subscriber list.

Why std::map is better:

• Frequent Modifications: This task involves many insert (register) and erase (unregister) calls.
• Benefit: std::map performs these modifications in O(logN) time, whereas std::flat_map would require slow O(N) element shifting for every change.

4. std::set: The Real-Time Deduplicator (Unpredictable Changes)

• Use Case: Tracking unique IDs or session keys in a high-throughput system where IDs arrive and expire rapidly and unpredictably.

Why std::set is better:

• Modification Stability: Its O(logN) insertion/deletion time is essential for smooth, predictable performance under high load.
• Iterator Stability: Iterators and references to elements are not invalidated when other elements are inserted or deleted, which is important when managing related data structures (flat containers invalidate iterators on modification).