Привет, Хабр! Еще в C++23 появились «плоские» ассоциативные контейнеры: std::flat_set, std::flat_map и их многоключевые аналоги. Проще говоря, это полные аналоги обычных std::set и std::map, но реализованные иначе – через упорядоченный последовательный контейнер (по умолчанию std::vector). Зачем вообще понадобились эти штуки? Официальная причина – экономия памяти и выигрыш в производительности при чтении данных.

Итак, что это за зверь. На самом деле flat-контейнеры – это не совсем отдельные структуры данных, а своего рода адаптеры контейнеров. Другими словами, они наезжают на уже существующий контейнер и добавляют необходимый порядок. Под капотом flat-контейнеров лежит не красно‑черное дерево или хэш-таблица, а любой последовательный контейнер с итератором произвольного доступа. Проще говоря: возьми, например, std::vector и заставь его всегда быть отсортированным. В итоге получаем вставку через бинарный поиск и сдвиг элементов, а поиск – через тот же бинарный поиск.

У flat-контейнеров две фичи. Во‑первых, они адаптеры: пользователю виден интерфейс ассоциативного контейнера (вставка, find, erase и т.д.), но данные хранятся «плоско», в общем массиве. Во-вторых, ключи (и значения, в случае flat_map) упорядочены в этом массиве – как в std::set/std::map, только без узлов и указателей. Так, std::flat_map<Key, T> на самом деле инкапсулирует два контейнера: один для ключей (KeyContainer), другой для значений (MappedContainer), причем номера элементов в них совпадают. Первые хранятся в отсортированном порядке, вторые – просто под рукой в том же индексе. То есть мы как бы разбиваем std::pair<key, value> на два разных массива: одним держим ключи, вторым – значения.

// Пример «ручной» реализации insert в плоский set (для наглядности):
std::vector<int> vec = {1, 3, 5};
int value = 4;
// Binary search to find insertion point (O(log N))
auto it = std::lower_bound(vec.begin(), vec.end(), value);
// Если такого элемента нет, вставляем
if (it == vec.end() || *it > value) {
    vec.insert(it, value);  // сдвиг О(N)
}
// Теперь vec == {1, 3, 4, 5}

Как видно, для вставки мы делаем бинарный поиск (дешево) и вставку в середину вектора (дорого). Сложность этих операций: поиск и чтение – логарифмические, а вставка/удаление – линейные (из-за сдвига элементов). Формально, flat-контейнеры удовлетворяют требованиям ассоциативного контейнера (есть find, lower_bound и т.п., с логарифмической сложностью поиска), но вставка и удаление выполняются за O(N).

Например, вставка и удаление в std::flat_set или std::flat_map в среднем и в худшем случае линейны.

Тем не менее, у «плоской» реализации есть свои плюсы. Самое весомое – скорость сканирования и итерации. Элементы хранятся рядом в памяти, так что при последовательном обходе CPU кэширует данные очень эффективно. Итераторы у flat-контейнеров – это итераторы произвольного доступа, как у std::vector, т.е можно делать сложные трюки со std::distance, случайным доступом по индексу и т.д. Благодаря этому итерация в flat-set/map может быть существенно быстрее, чем у обычного дерева (особенно для простых типов). Ещё flat-контейнеры экономят память: нет дополнительных указателей и меток, как у узлов дерева. А для небольших объектов (или после shrink_to_fit) это может давать экономию по сравнению с std::map/set. В C++ это ценно, ведь в одном двоичном узле может быть 3–4 указателя, а здесь – лишь массив.

Тем не менее, есть свои проблемы. Самая большая – неустойчивость итераторов. Любая вставка или удаление способна инвалидировать все итераторы и ссылки на элементы, потому что вектор может перенести всю память. Если в std::map вы после вставки можете спокойно продолжить обход, здесь придётся быть осторожным. Ещё flat-контейнеры требуют, чтобы ключи и значения были копируемыми/перемещаемыми. Если вы попытаетесь хранить, например, std::unique_ptr как ключ или значение, компилятор ругнётся: при вставке элементы двигаются, а уникальный указатель нельзя просто скопировать. Слабая гарантированная безопасность исключений: если конструктор ключа/значения бросит исключение во время перемещения элементов, flat-контейнер может оказаться в несогласованном состоянии.

Преимущества flat-контейнеров: быстрая (последовательная) итерация, меньше памяти на элемент, лучшая кэш-локальностью.

Недостатки: дорогая вставка/удаление (O(N)), инвалидация итераторов при любом изменении, нельзя хранить некопируемые/неперемещаемые типы, более слабая гарантия исключений.

// Пример использования std::flat_set:
std::vector<int> init = {3, 1, 4, 1, 5};
std::flat_set<int> fs(std::move(init)); // исходный вектор отсортируется и дубликаты удалятся
// fs теперь содержит {1, 3, 4, 5}

fs.insert(2); 
fs.insert(3); // 3 уже есть, не вставится
for (int x : fs) {
    std::cout << x << " ";  // Выведет 1 2 3 4 5
}

// Пример использования std::flat_map:
std::flat_map<std::string,int> m;
m.insert({"CPU", 10});
m.insert({"GPU", 15});
m.insert({"RAM", 20});

// Обновим и добавим
m["CPU"] = 25;    // обновление существующей пары
m["SSD"] = 30;    // добавление новой
m.erase("GPU");   // удалили ключ GPU

for (auto it = m.begin(); it != m.end(); ++it) {
    std::cout << it->first << " = " << it->second << "\n";
}

flat_map ведёт себя почти как std::map: добавляет новые пары, обновляет значение по ключу, поддерживает оператор [], метод find и т.д. Отличие в том, что всё это выполняется через внутренний std::vector.

Кроме того, у flat-контейнеров есть удобные конструкторы и методы, которых не было у старых аналогов. Так, можно конструировать flat_set или flat_map, передавая целый отсортированный контейнер ключей (и контейнер значений). Если вы точно знаете, что данные уже упорядочены и не содержат дублей, можно использовать тег std::sorted_unique_t (для flat_set/map) или std::sorted_equivalent_t (для flat_multiset/multimap) – тогда конструктор не будет повторно сортировать данные и экономит работу. Пример:

std::vector<int> sortedVec = {1, 2, 3, 4};
std::flat_set<int> fsOk(std::sorted_unique_t{}, sortedVec); 
// Конструктор верно примет данные (уже сортированы), просто сохранит их

// Если бы мы передали сюда несортированный вектор с тегом std::sorted_unique_t{},
// это привело бы к неопределённому поведению.

Если вы создаёте flat_set без тега из неотсортированного вектора, он сам отсортирует и удалит повторения. С тегом std::sorted_unique_t вы берёте на себя ответственность, что вход уже готов к использованию – иначе фатально.

У flat_map есть аналогичные возможности: можно передать два вектора – ключей и значений. Конструктор переместит ключи, отсортирует их (и в том же порядке переставит значения). Например:

std::vector<std::string> keys = {"delta", "alpha", "charlie"};
std::vector<int> values = {4, 1, 3};
std::flat_map<std::string,int> fm(std::move(keys), std::move(values));
// Ключи отсортируются в {"alpha", "charlie", "delta"}, 
// а значения выстроятся соответственно {1, 3, 4}.

И кроме того, flat_map предлагает методы keys() и values(), которые возвращают ссылки на внутренние контейнеры ключей и значений. Это можно использовать, например, чтобы посмотреть все ключи или все значения отдельно.

Немного из истории: идеи flat-контейнеров давно гуляли по C++ сообществу – Boost уже в версии 1.48 добавил boost::container::flat_set и flat_map, а Андреи Александреску выкладывал свой AssocVector. Почти все эти реализации хранили пары {key,value} в одном std::vector<std::pair<K,V>>. Только в C++23 std::flat_map сделали иначе – ключи и значения живут раздельно. Оказалось, такой раздельный дизайн быстрее при вставке мелких пар. При больших данных выигрыш скромнее, зато расход памяти всё ещё низкий.

Заключение

Итак, коротко: flat-контейнеры выгодны, когда у вас статический или редко меняющийся набор данных, и много операций чтения/итерирования. Если же вам постоянно что-то в них добавлять или удалять – может быть разумнее std::map или std::unordered_map. Как говорят, «если нужен упорядоченный набор и частая вставка – это для вас» (сарказм: нет, осторожнее – лучше обычный set), а flat-контейнеры – когда коллекцию собрали однажды и потом только читают.

На этом всё. Надеюсь, статья помогла разобраться в нюансах flat_set и flat_map. Используйте их с умом – и они отплатят быстрой и компактной работой. Удачных проектов и приятного кода!

Освоить C++ с нуля до сложных и высокопроизводительных проектов вам помогут эксперты индустрии на специализации Otus "C++ Developer". Если не уверены в выбранном направлении или хочется больше узнать об особенностях обучения, читайте отзывы выпускников.

А чтобы узнать больше о курсах по C++ и получить доступ к записям открытых уроков, переходите в телеграм-бот.