C++ Reference ยท Containers
C++ std::flat_map and std::flat_set (C++23)
Reference for C++23 std::flat_map and std::flat_set: sorted-vector associative containers, cache-friendly lookup, slow middle insertion, and invalidation rules.
std::flat_map and std::flat_set arrived in C++23 (headers <flat_map> and <flat_set>). They provide the interface of std::map and std::set, but store their data in sorted contiguous sequences instead of tree nodes. A flat_set<T> is essentially a sorted std::vector<T>. A flat_map<K, V> keeps two parallel containers, one of keys and one of values, both sorted by key. The containers are adaptors: by default they wrap std::vector, but you can supply std::deque or another sequence.
Lookup is a binary search over contiguous memory, which is fast and cache friendly. Iteration is as fast as iterating a vector. The cost is that inserting or erasing in the middle shifts elements, which is O(n). Choose them for data that is built once (or rarely changed) and read often. The multi-key versions are std::flat_multimap and std::flat_multiset.
#include <flat_map> std::flat_map<int, std::string> m = {{3, "c"}, {1, "a"}}; // sorted by key
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template <class Key, class T, class Compare = std::less<Key>, class KeyContainer = std::vector<Key>, class MappedContainer = std::vector<T>> class flat_map; template <class Key, class Compare = std::less<Key>, class KeyContainer = std::vector<Key>> class flat_set; flat_map(std::sorted_unique_t, KeyContainer keys, MappedContainer values); const KeyContainer& keys() const noexcept; const MappedContainer& values() const noexcept; // flat_map only
| Name | Description |
|---|---|
Compare |
Strict weak ordering of keys, as for std::map. |
KeyContainer, MappedContainer |
Underlying sequence containers (contiguous or random access). |
std::sorted_unique |
A tag that promises the input is already sorted without duplicates, so no sort is done. |
Returns: the lookup and insertion members mirror std::map (insert returns an iterator/bool pair, find returns end() if absent). The extra keys() accessor returns a const view of the sorted keys.
Errors / undefined behavior: promising sorted_unique for data that is not sorted or has duplicates is undefined. at() throws std::out_of_range.
Usage notes
- Complexity: lookup is O(log n) via binary search; insert and erase are O(n) because elements shift; building from unsorted data is O(n log n), from sorted data O(n).
- Invalidation: unlike
std::map, any insertion or erasure can invalidate all iterators, pointers and references, as with a vector. Do not keep references across modifications. - Memory: no per-element node and no pointers, so a flat map of small elements uses a fraction of the memory of a
std::map. - Iterating a flat_map: its iterator yields proxy references, not
std::pair<const K, V>&. Writefor (const auto& [k, v] : m)orfor (auto [k, v] : m). The formfor (auto& [k, v] : m)does not compile with GCC 15.2 on this site's runner. - Bulk insert, then use: the common pattern is to fill a vector, then construct the flat container (
sorted_uniqueif you can), then read it many times. - Good for: lookup tables, configuration, small to medium maps, anything iterated more than modified.
- Avoid for: large containers with frequent inserts and erases in random positions; use
std::maporstd::unordered_map. - Availability: C++23 library feature; needs a recent standard library (GCC 15 provides it).
Related
- std::map, std::set, std::vector, Sorting containers
- Lessons: std::map, Modern C++ features