std::flat_map / std::flat_set

std::flat_map<K, V>/std::flat_set<K> — ассоциативные контейнеры с полностью совместимым интерфейсом std::map/std::set (find, lower_bound, upper_bound, operator[] для map), но физически хранящие элементы в отсортированном непрерывном массиве, а не в узлах дерева. Для map это обычно пара параллельных векторов — отдельно ключи, отдельно значения (layout "structure of arrays") — а не вектор пар {key, value}. Контраст стоит проводить не с деревом, а с хэш-таблицей из std::unordered_map (см. cpp11/unordered-containers.html): unordered_map даёт амортизированный O(1) через хэширование ценой отсутствия порядка, а flat_map сохраняет тот же формальный O(log n), что у map/set, но меняет физическую раскладку данных в памяти, а не алгоритмическую сложность.std::flat_map<K, V>/std::flat_set<K> are associative containers with a fully compatible std::map/std::set interface (find, lower_bound, upper_bound, operator[] for map), but physically storing elements in a sorted contiguous array rather than in tree nodes. For map, this is typically a pair of parallel vectors — keys separately, values separately (a "structure of arrays" layout) — rather than a vector of {key, value} pairs. The contrast worth drawing isn't with a tree but with the hash table behind std::unordered_map (see cpp11/unordered-containers.html): unordered_map gives amortized O(1) via hashing at the cost of no ordering, while flat_map keeps the same formal O(log n) as map/set but changes the physical data layout in memory, not the algorithmic complexity.

std::map<int, std::string> m = {{1, "a"}, {2, "b"}};
m.find(1);
// каждый узел — отдельная аллокация, обход — переходы по указателям// each node is a separate allocation, traversal follows pointers around

std::flat_map<int, std::string> m = {{1, "a"}, {2, "b"}};
m.find(1);
// тот же вызов, тот же результат — но бинарный поиск идёт по// the same call, the same result — but the binary search runs over
// непрерывному массиву ключей, кэш-дружелюбно// a contiguous array of keys, cache-friendly

Формально одинаковая асимптотика std::map и flat_map скрывает большую разницу в реальной производительности:The formally identical asymptotics of std::map and flat_map hide a large gap in real-world performance:

По умолчанию std::flat_map<K, V> хранит данные в двух отдельных std::vector — std::vector<K> для ключей и std::vector<V> для значений, оба отсортированы синхронно по ключу (layout можно кастомизировать через шаблонный параметр container_type, но vector — значение по умолчанию). Поиск — обычный бинарный поиск по вектору ключей; найденный индекс используется для доступа к соответствующему значению во втором векторе. std::flat_set<K> проще — один отсортированный std::vector<K>.By default, std::flat_map<K, V> stores its data in two separate std::vectors — a std::vector<K> for keys and a std::vector<V> for values, both sorted in lockstep by key (the layout is customizable via a container_type template parameter, but vector is the default). Lookup is an ordinary binary search over the vector of keys; the found index is then used to access the corresponding value in the second vector. std::flat_set<K> is simpler — a single sorted std::vector<K>.

#include <flat_map>

std::flat_map<int, std::string> m = {{3, "c"}, {1, "a"}, {2, "b"}};
// конструктор сортирует пары по ключу один раз — 1, 2, 3// the constructor sorts the pairs by key once — 1, 2, 3

auto it = m.find(2);           // бинарный поиск по внутреннему массиву ключей// binary search over the internal array of keys
if (it != m.end()) std::println("{}", it->second);   // "b"// "b"

auto lb = m.lower_bound(2);   // тот же интерфейс, что у std::map// the same interface as std::map

Массовая инициализация (как в примере выше) сортирует данные один раз за O(n log n), после чего каждый отдельный поиск — O(log n) бинарным поиском. Именно поэтому flat_map особенно уместен в сценарии "построили один раз (например, из отсортированных или почти отсортированных данных), потом много читаем" — единовременная сортировка при построении амортизируется по всем последующим поискам.Bulk initialization (as in the example above) sorts the data once in O(n log n), after which every individual lookup is O(log n) via binary search. This is exactly why flat_map particularly suits the "built once (say, from sorted or nearly-sorted data), read many times" scenario — the one-time sort at construction is amortized across all subsequent lookups.

• cppreference — std::flat_map
• cppreference — std::flat_set
• WG21 P0429 — A Standard flat_map