Новый стандарт C++, C++23, впервые с C++11 расширил всем привычную линейку контейнеров: помимо знакомых array
, vector
, (unordered_)set
, (unordered_)map
и прочим в нее теперь входят непонятные flat_set
, flat_map
, flat_multiset
и flat_multimap
. Ответим на вопросы, что это за контейнеры, когда они могут быть полезны, сравним дизайн стандартизированных «плоских» контейнеров с дизайном плоских контейнеров из Boost и ETL и, конечно, произведём замеры и сравним производительность flat_
и не flat_
контейнеров.
Важно сказать, что на самом деле все эти «плоские» контейнеры даже не контейнеры в строгом смысле, а лишь адаптеры контейнеров: подобно stack
и queue
они не реализуют какую-то собственную уникальную структуру хранения данных, а лишь вводят свой дополнительный порядок поверх структуры, предоставляемой другим контейнером.
И прежде чем начать рассмотрение каждого из «плоских» контейнеров по отдельности, не менее важно понять одну общую для них всех вещь: они называются »плоскими», потому что они действительно плоские — под капотом у них лежат не красно-черные (или AVL) деревья, как у std::(multi)set
и std::(multi)map
и не хэш-таблицы, как у std::unordered_(multi)set
и std::unordered_(multi)map
, а последовательные контейнеры.
Например, как бы вы реализовали set
, если вы бы не знали о вышеупомянутых деревьях? Легко: берем std::vector
и реализуем insert
так, чтобы он поддерживал этот вектор в отсортированном состоянии. То есть, примерно так:
template <typename ...>
std::pair<iterator, bool> flat_set<...>::insert(const K& value) {
// Ищем в контейнере value или же подходящее место для его вставки
auto it = std::lower_bound(
vec.begin(), vec.end(), value
); // Бинарный поиск, O(log N)
// Если не нашли совсем или нашли не то, то вставляем
if (it == vec.end() || value < *it) {
vec.insert(
it, std::move(value)
); // O(N) и потенциальная реаллокация :(
return std::pair<iterator, bool>{std::move(it), true};
}
// Иначе возвращаем найденное
return std::pair<iterator, bool>{std::move(it), false};
}
А find()
в таком случае реализуется как обычный бинарный поиск (со сложностью ). Так вот, так же (но более обобщенно) устроен и
flat_set
, и flat_multiset
(в его случае вместо lower_bound
используется upper_bound
и новый элемент вставляется безусловно), и flat_map
и flat_multimap
(но в их случае мы оперируем двумя контейнерами: одним для хранения ключей, другим для хранения значений).
Аналогично, даже не меняя реализации, вместо std::vector
мы могли бы использовать std::deque
. В общем, любой последовательный контейнер. Именно поэтому плоские контейнеры и являются адаптерами: разные контейнеры под капотом могут иметь разные плюсы и минусы, поэтому нет причин жестко завязываться на какой-то единственный из них. И именно поэтому их определение выглядит вот так:
template<
class Key,
class Compare = std::less<Key>,
class KeyContainer = std::vector<Key> // Контейнер для ключей
> class flat_set; // Точно такое же для flat_multiset
template<
class Key,
class T,
class Compare = std::less<Key>,
class KeyContainer = std::vector<Key>, // Контейнер для ключей
class MappedContainer = std::vector<T> // Контейнер для значений
> class flat_map; // Точно такое же для flat_multimap
Если же сравнивать асимптотическую сложность операций в плоских и не плоских контейнерах, то получим следующее:
std::unordered_(multi)set/map |
std::(multi)set/map |
std::flat_(multi)set/map |
|
insert(value) |
В среднем |
||
erase(value) |
В среднем |
||
find(value) |
В среднем |
Примечание к таблице
В таблице выше, для полноты картины, было приведено сравнение всех имеющихся в стандартной библиотеке ассоциативных контейнеров.
Однако дальше в тексте, главным образом, будут сравниваться лишь упорядоченные контейнеры: std::(multi)set/map
и новые плоские контейнеры (которые также являются упорядоченными) std::flat_(multi)set/map
.
О неупорядоченных контейнерах — контейнерах, основанных на хэш-таблицах, говориться не будет, так как неупорядоченные и упорядоченные контейнеры — разного поля ягоды. Если вам не нужен порядок, то вам, за очень редкими исключениями (которые будут отмечены в заключении), и не нужны плоские контейнеры — хэш-таблицы во всём будут быстрей.
Асимптотически, казалось бы, мы не очень выигрываем. Тем не менее, по сравнению с (multi)set
и (multi)map
«плоская» реализация имеет и некоторые плюсы: более быструю итерацию, меньшее потребление памяти и лучшую кэш-локальность.
Но взамен нас неминуемо ждут менее стабильные итераторы, способные инвалидироваться на любой вставке и удалении; невозможность хранения не-копируемых и не-перемещаемых типов; более слабые гарантии безопасности исключений (никто не защитит нас от исключений в конструкторах копирования/перемещения при сдвиге элементов в ходе вставки/удаления) и более медленные вставки и удаления (мало того, что нам нужно поддерживать отсортированность, так ведь при каждой вставке в наш вектор нам нужно двигать элементы)
Более спорный вопрос: получим ли мы более быстрый поиск? (его сложность —как в плоских, так и не в плоских контейнерах) Один из классиков С++, Matt Austern, в своей статье (2000 год) заявляет, что получим:
Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality are very different. Using g++ (...) it takes X seconds to perform a million lookups in a sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover, the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).
Но более новые бенчмарки (2014 год; впрочем, на меньших объемах данных) показывают обратное (boost::container::flat_map
, исключая один нюанс, о котором будет сказано чуть позже, идеологически устроен так же, как стандартизированный std::flat_map
):


Однако, оставим этот вопрос на потом. А сейчас, с сформированным пониманием, зачем нам в принципе могут понадобиться эти контейнеры, рассмотрим интерфейс всех этих новый адаптеров.
Интерфейс
К счастью, интерфейс flat_set
, flat_multiset
, flat_map
и flat_multimap
задумывался так, чтобы на них можно было просто взять и заменить их не «плоские» аналоги (то есть, другие упорядоченные ассоциативные контейнеры — std::set
, std::map
и иже с ними), так что интерфейсы плоских и не плоских контейнеров практически совпадают.
Например, простенький демонстрационный пример с страницы std::set на cppreference без проблем скомпилируется (и вывод, конечно, будет тем же самым), если все вхождения std::set
заменить на std::flat_set
(godbolt).
Тот самый пример (в оригинале)
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <string_view>
template<typename T>
std::ostream& operator<<(std::ostream& out, const std::set<T>& set)
{
if (set.empty())
return out << "{}";
out << "{ " << *set.begin();
std::for_each(std::next(set.begin()), set.end(), [&out](const T& element)
{
out << ", " << element;
});
return out << " }";
}
int main()
{
std::set<int> set{1, 5, 3};
std::cout << set << '\n';
set.insert(2);
std::cout << set << '\n';
set.erase(1);
std::cout << set << "\n\n";
std::set<int> keys{3, 4};
for (int key : keys)
{
if (set.contains(key))
std::cout << set << " does contain " << key << '\n';
else
std::cout << set << " doesn't contain " << key << '\n';
}
std::cout << '\n';
std::string_view word = "element";
std::set<char> characters(word.begin(), word.end());
std::cout << "There are " << characters.size() << " unique characters in " << std::quoted(word) << ":\n" << characters << '\n';
}
И точно так же в любом коде все вхождения std::map
можно заменить на std::flat_map
и всё заработает. Так же возьмем пример с страницы на cppreference (godbolt).
Пример (почти в оригинале)
#include <iostream>
#include <map>
#include <string>
#include <string_view>
void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
std::cout << comment;
// Iterate using C++17 facilities
for (const auto& [key, value] : m)
std::cout << '[' << key << "] = " << value << "; ";
std::cout << '\n';
}
int main()
{
// Create a map of three (string, int) pairs
std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
print_map("1) Initial map: ", m);
m["CPU"] = 25; // update an existing value
m["SSD"] = 30; // insert a new value
print_map("2) Updated map: ", m);
// Using operator[] with non-existent key always performs an insert
std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
print_map("4) Updated map: ", m);
m.erase("GPU");
print_map("5) After erase: ", m);
std::erase_if(m, [](const auto& pair){ return std::get<1>(pair) > 25; });
print_map("6) After erase: ", m);
std::cout << "7) m.size() = " << m.size() << '\n';
m.clear();
std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n';
}
Почему я написал «почти»: на самом деле это не оригинальный код с cppreference. Я внес в него правку: поменял строку №33. Изначально в ней был фрагмент pair.second > 25
, а не std::get<1>(pair) > 25
. Мне пришлось это сделать из-за того, что компилятор (как gcc, так и clang) стал ругаться, что pair
(аргумент лямбда-функции) это std::tuple
, а не std::pair
. Фича это или баг — непонятно. Стандарт определяет тип const_reference
у std::flat_map
как pair<const key_type&, mapped_type&>
, а не tuple
[flat.multimap.defn]
P.S. Впоследствии выяснилось, что, по всей видимости, это особенности libstdc++. При использовании libc++ ошибок не возникает. См. godbolt и обсуждение в @procxx (Telegram)
В чём же flat_set
все-таки отличается от set
:
У
flat_set
есть конструкторы, которые принимают контейнер-хранилище, который может быть как отсортирован, так и нет (в этом случаеflat_set
отсортирует его и даже удалит дубликаты за вас). Пример доступен под спойлером и на godbolt.
Пример
#include <vector>
#include <flat_set>
int main() {
std::vector<int> elements = {0, 1, 2, 3, 4, 5};
{
// Код ниже работает, т.к.
// std::vector — контейнер по умолчанию для flat_set
// Если мы попробуем передать, например, std::deque,
// то нас ждёт облом
std::flat_set<int> flat_set(elements);
}
{
// А вот этот не работает
// std::set<int> set(elements);
}
{
// Но лучше сделать так, чтобы конструктор не занимался
// лишней сортировкой
std::flat_set<int> flat_set(
std::sorted_unique_t{},
elements
);
}
}
Метод
flat_set::extract
вместо того, чтобы извлекать узлы (которых уflat_set
нет), извлекает контейнер-хранилище. Пример доступен под спойлером и на godbolt.
Пример
#include <flat_map>
#include <print>
int main() {
std::vector<std::string> keys = {
"one", "two", "three"
};
std::vector<int> values = {
1, 2, 3
};
std::flat_map flat_map(
std::move(keys), std::move(values)
);
std::println("{}", flat_map);
/*
Определение containers:
struct containers
{
key_container_type keys;
mapped_container_type values;
};
*/
auto containers = std::move(flat_map).extract();
// Заметьте, keys и values отсортированы, так как ранее они
// отсортировались в конструкторе
// Так что мы можем воспользоваться replace
// (он ожидает отсортированные данные)
flat_map.replace(
std::move(containers.keys),
std::move(containers.values)
);
std::println("{}", flat_map);
}
Аналогично, вместо перегрузок
insert
, принимающих узлы, уflat_set
введён методreplace
, заменяющий контейнер-хранилище на переданный в аргументе (важный нюанс: передаваемый как аргумент контейнер должен быть отсортирован и в нем не должно быть пар с повторяющимися ключами, иначе будет UB). Пример доступен под спойлером и на godbolt.
Пример
#include <cassert>
#include <flat_set>
/*
void replace( container_type&& cont );
*/
int main() {
std::vector<int> keys{1, 2, 3};
std::flat_set<int> flat_set;
assert(flat_set.empty());
flat_set.replace(std::move(keys));
assert(flat_set.size() == 3);
assert(keys.empty());
}
Как мы уже видели в примере с конструктором, у нас появились новые теги:
std::sorted_unique_t
дляflat_set
(илиflat_map
) иstd::sorted_equivalent_t
дляflat_multiset
(илиflat_multimap
) для тех случаев, когда мы точно знаем, что передаваемые нами данные отсортированы. Пример доступен под спойлером и на godbolt.
Пример
#include <flat_set>
int main() {
std::flat_set<int> flat_set;
// Тут всё хорошо, insert отсортирует
// данные за нас
flat_set.insert({
15, 27, 18, 7, 41
});
// Тут тоже всё хорошо, так как данные
// отсортированы
flat_set.insert(
std::sorted_unique_t{},
{1, 2, 3, 4, 5}
);
// А тут мы нарушили контракт. У нас UB
flat_set.insert(
std::sorted_unique_t{},
{68, 6, 4, 3, 20}
);
}
Аналогично отличаются интерфейсы flat_map
и map
, только конструкторы, методы extract
и replace
оперируют не одним контейнером, а двумя: одним для ключей, другим для значений. Кроме того, у flat_map
определены методы keys
и values
, возвращающие ссылки на соответствующие контейнеры. Пример доступен под спойлером и на godbolt.
Пример
#include <flat_map>
#include <print>
int main() {
std::vector<std::string> keys = {
"one", "two", "three"
};
std::vector<int> values = {
1, 2, 3
};
std::flat_map flat_map(
std::move(keys), std::move(values)
);
std::println("{}", flat_map);
/*
Тип containers:
struct containers
{
key_container_type keys;
mapped_container_type values;
};
*/
auto containers = std::move(flat_map).extract();
// Заметьте, keys и values отсортированы, так как ранее они
// отсортировались в конструкторе
// Так что мы можем воспользоваться replace
// (он ожидает отсортированные данные)
flat_map.replace(
std::move(containers.keys),
std::move(containers.values)
);
std::println("{}", flat_map);
}
Вывод программы:
{"one": 1, "three": 3, "two": 2}
{"one": 1, "three": 3, "two": 2}
Отличие от аналогов
Несмотря на то, что плоские контейнеры были приняты только в C++23 и реализованы в основных компиляторах (gcc 15, clang 21) лишь недавно, они известны в сообществе C++ давно: о них писал и Matt Austern, и Andrei Alexandrescu. А последний даже реализовал flat_map
в своей библиотеке Loki под названием AssocVector.
Кроме того, flat_set
и flat_map
вошли даже в Boost 1.48 больше 12 лет назад под названиями boost::container::flat_set
, boost::container::flat_map
вместе со своими mutli
версиями (из менее популярных проектов плоские контейнеры также реализованы в ETL и Chromium).
Почти единственное, чем отличаются AssocVector
и boost::container::flat_map
от своих стандартизированных версий — способом хранения данных. Если std::flat_map
хранит ключи и значения в отдельных контейнерах, то AssocVector
и boost::container::flat_map
хранят их в одном контейнере в виде пар (а-ля std::vector<std::pair<K, V>>
).
Почему std::flat_map
так отличается от своих предков? Неожиданно, но flat_map
был сделан именно так, потому что такое расположение элементов в памяти, внезапно, ускоряет вставку маленьких пар ключ-значение на 40-60% по сравнению с классическим дизайном.
Под спойлером приведены результаты бенчмарков, проведенных Zach Laine, автором std::flat_map
, и приведенных в оригинальном пропозале P0429R1 «A standard flat_map» (split_map_t
в легенде — современный std::flat_map
в реализации Zach Laine).
В остальном стандартизированные контейнеры отличаются от их предков из Boost и Loki лишь большей обобщенностью: AssocVector
не позволяет изменять тип хранилища, в котором будут лежать данные — там всегда используется std::vector
; контейнеры из Boost не позволяли этого вплоть до Boost 1.66, но даже сейчас, когда на дворе уже Boost 1.88, в реализации этой фичи до сих пор чинят баги.
Однако, в одной из ранних реализаций плоских контейнеров, ETL, всё же есть одна занятная особенность, заслуживающая упоминания: в целях улучшения производительности операций вставки, в ней плоские контейнеры реализованы не как отсортированные массивы (плоские контейнеры в ETL имеют ограниченный размер, задаваемый как шаблонный параметр) значений, а как массивы указателей на значения. При этом значения, конечно, вынуждены храниться в отдельном контейнере. С одной стороны мы получаем чуть более быструю вставку за счет того, что указатели относительно дешево копировать, а с другой чуть более долгий доступ к элементам за счет того, что до них нам теперь придется ходить через указатель.
Авторы ETL не приводят никаких сравнений производительности своей реализации с какими-либо другими реализациями, поэтому сделаем их самостоятельно.
Попробуем последовательно повставлять пар с ключом — псевдо(случайно) сгенерированным
int64_t
, а значением — захардкоженным int64_t{1}
и замерим, сколько времени это займет. На всех графиках ниже по оси X — количество пар в контейнере (шт.), по оси Y — время работы программы (в секундах или миллисекундах — см. подписи на графиках) или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

Потом сделаем то же самое, но теперь ключом будет 50-символьный std::string
.

Что-же, рост производительности по сравнению с std::flat_map
виден невооруженным глазом. При этом потребление оперативной памяти всё так же остается низким и вырастает не так уж и значительно, максимум на 10–20%.
Графики потребления памяти тут
Для int64_t
:

Для std::string
(50 символов):
:

Графики для удаления выглядят точь-в-точь как графики для вставки, и поэтому приведены не будут. Поэтому сразу перейдем к замерам скорости поиска и итерации.
Сгенерируем по тому же принципу ключи, значения, вставим их в массив, а потом попробуем найти в контейнере все вставленные пары, но в случайном порядке — не в том, в котором они были вставлены.


Видим, что поиск отдельных элементов действительно стал намного медленнее. Но если мы замерим скорость итерации, то этот график нас порадует (в этом случае замеры производились только для int64_t
).

По-прежнему быстро!
Нужно ли нам ускорение вставки при том, что по своей природе плоские контейнеры созданы для того, чтобы в них один раз при создании всё вставить и больше не вставлять — вопрос открытый, но, тем не менее, спасибо ETL за интересную реализацию.
Замеры
Наконец, поставим точку в вопросе, быстрее ли в плоских контейнерах поиск, чем не в плоских. Но не будем мелочиться, и сравним плоские контейнеры не только с их не плоскими аналогами, но и с контейнерами, основанными на хэш-таблицах: std::unordered_set
, std::unordered_map
.
Замеры будем проводить по заветам статьи «Benchmark of major hash maps implementations» за авторством Tessil (Thibaut Goetghebuer-Planchon) — измерим скорость вставки, удаления и поиска для трёх видов ключей-значений: int64_t
— int64_t
, string
(15 случайных символов) — int64_t
, string
(50 случайных символов) — int64_t
. При этом сделаем это при разном количестве пар: 200'000 пар, 400'000 пар, и так далее до 3'000'000 пар с шагом 200'000 (кроме этого я сделал замеры для 10–100 пар с шагом 10 и для 20'000–100'000 пар с шагом 20'000, но потом решил, что подробно обсуждать эти результаты бессмысленно — по большей части они совпадают с результатами для 200'000–3'000'000 пар, поэтому речи о них далее вестись не будет, хоть их результаты вы так же можете посмотреть под спойлером ниже). Кроме того, отдельно измерим скорость итерации для ключей-значений int64_t
— int64_t.
Каждое измерение будем повторять пять раз, а в качестве итогового значения выбирать наилучший результат. Исходники всех бенчмарков доступны на github, замеры производились на Linux 6.8.0, Intel® Xeon® Gold 6354 3 ГГц, 8 Гб ОЗУ, компилятор: clang 21.0.0, опции компиляции: -stdlib=libc++ -O3 -march=native -std=c++23
.
Если вам интересно посмотреть результаты целиком, добро пожаловать под спойлер (осторожно, очень много букв и графиков). А далее мы лишь подведем итоги.
Результаты бенчмарков
Диапазон 10–100 (шаг 10)
На всех графиках ниже по оси X — количество пар в контейнере (шт.), по оси Y — время работы программы (в секундах или микросекундах — см. подписи на графиках) или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).
int64_t — int64_t
Вставки в случайной порядке
Перед каждым замером мы создаем std::vector
с значениями и перемешиваем этот вектор с помощью функции
std::shuffle
. Затем для каждого значения в векторе мы вставляем пару ключ-значение
в контейнер.

Вставки пар с случайным ключом
Перед каждым замером мы создаем std::vector
размером , где каждое значение случайным образом генерируется единым генератором (псевдо)случайных чисел из всех возможных положительных значений, которые может содержать
int64_t
. Затем для каждого значения в векторе мы вставляем пару ключ-значение
в контейнер.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов таким же образом, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Итерирование
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t
Вставки пар с случайным ключом
Мы раз генерируем строку-ключ и вставляем ее в контейнер с значением
std::int64_t{1}
.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

string (50 символов) — int64_t
Вставки пар с случайным ключом
Мы раз генерируем строку-ключ и вставляем ее в контейнер с значением
std::int64_t{1}
.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Диапазон 10'000–100'000 (шаг 20'000)
int64_t — int64_t
Вставки в случайной порядке
Перед каждым замером мы создаем std::vector
с значениями и перемешиваем этот вектор с помощью функции
std::shuffle
. Затем для каждого значения в векторе мы вставляем пару ключ-значение
в контейнер.

Вставки пар с случайным ключом
Перед каждым замером мы создаем std::vector
размером , где каждое значение случайным образом генерируется единым генератором (псевдо)случайных чисел из всех возможных положительных значений, которые может содержать
int64_t
. Затем для каждого значения в векторе мы вставляем пару ключ-значение
в контейнер.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов таким же образом, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Итерирование
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t
Вставки пар с случайным ключом
Мы раз генерируем строку-ключ и вставляем ее в контейнер с значением
std::int64_t{1}
.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

График использования оперативной памяти приведен ниже.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

string (50 символов) — int64_t
Вставки пар с случайным ключом
Мы раз генерируем строку-ключ и вставляем ее в контейнер с значением
std::int64_t{1}
.

График использования оперативной памяти приведен ниже.

Удаление пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в предыдущем тесте «Вставки пар с случайным ключом». Затем мы удаляем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Поиск после удаления половины
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом», а затем случайным образом удаляем половину этих значений. Затем мы пытаемся найти все исходные значения в другом порядке, что приводит к 50% совпадений и 50% промахов.

Диапазон 200'000–3'000'000 (шаг 200'000)
Вставлять сотни тысяч и миллионы элементов в плоские контейнеры слишком медленно, поэтому тут я произвел только бенчмарки поиска и итерации.
int64_t — int64_t
Поиск пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки в случайной порядке». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы считываем каждую пару ключ-значение в случайном порядке, отличном от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных элементов, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Итерирование
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы итерируемся по контейнеру, при этом считывая все пары ключ-значение.

string (15 символов) — int64_t
Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор
случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

string (50 символов) — int64_t
Поиск пар с случайным ключом
Перед каждым замером мы вставляем элементов в контейнер, как в тесте «Вставки пар с случайным ключом». Затем мы ищем каждый ключ один за другим в случайном порядке, отличным от того, в котором они были вставлены.

Поиск несуществующих пар
Перед каждым замером мы вставляем элементов таким же образом, как в тесте «Вставки пар с случайным ключом». Затем мы генерируем другой вектор случайных строк, отличающийся от вставленных элементов, и пытаемся найти эти неизвестные элементы в контейнере.

Итак, производить много одиночных вставок в плоские контейнеры, как и ожидалось, очень медленно (я даже не смог дождаться прохождения замеров для , поэтому провел замеры вставки и удаления для
): хоть найти место для вставки занимает
, но сложность вставки в вектор — по-прежнему
.

Удаление также ничем не отличается от вставки: плоские контейнеры драматически проигрывают классическим.
Посмотрите сами, если не верите
Осторожно, графики std::flat_map
и boost::containers::flat_map
сливаются в одну линию!

Единственный интересный момент тут — подтверждение наблюдений Zach Laine, что flat map с двумя контейнерами под капотом (std::flat_map
) обгоняет flat map с одним контейнером под капотом (boost::containers::flat_map
) по скорости вставки элементов. Но ни о каких 40–60% ускорения тут речи, конечно, не идет. Максимальный наблюдаемый прирост производительности — 12%.
Интересно, но при удалении такой прирост не наблюдается, хотя, казалось бы, операции максимально похожи.
Если смотреть же на скорость поиска, то тут, при малых размерах ключей, например, 8-байтном std::int64_t
, и больших объемах, плоские контейнеры существенно превосходят классические упорядоченные контейнеры.

Как и при 15-символьным ключе std::string
.

Однако при 50-символьном ключе std::string
производительность плоских контейнеров значительно ухудшается и уже не многим становится лучше производительности классических упорядоченных контейнеров.

На условно маленьких (20'000–100'000 пар) же объемах невысокий прирост производительности наблюдается при абсолютно всех сценариях: даже с маленьким, 8-битным, ключом, std::flat_map
лишь незначительно превосходит boost::map
.

А на совсем маленьких объемах (10–100 пар) всё еще хуже: плоские контейнеры как с ключом int64_t
, так и с ключом std::string
становятся аутсайдерами и если кого-то и обгоняют, то очень неуверенно.
Если же говорить про итерацию, то тут плоские контейнеры одерживают верх над всеми своими соперниками без исключений.

Без лишних слов также отметим, что, ожидаемо, плоские контейнеры потребляют меньше памяти, чем не плоские.

Но классические контейнеры тоже не так плохи и при больших ключах (50-символьный std::string
) разница в потреблении памяти становится уже не такой большой.

Итог
Таким образом, можно сделать следующие выводы:
Вставка и удаление элементов из плоских контейнеров это ужасно дорого, и лучше делать это как можно реже.
Поиск в плоских контейнерах действительно сильно быстрее, чем в классических упорядоченных ассоциативных, но только при больших объемах данных (> 1'000'000 пар) и маленьких размерах ключей. Если пар меньше (20'000–100'000) или ключи большие, то он быстрее, но не сильно. Если же пар совсем мало (10–100), то они оказываются даже медленнее.
График времени итерации по плоским контейнерам невероятно красив — он практически плоский. По скорости итерации плоские контейнеры обгоняют все остальные контейнеры на порядки.
Плоские контейнеры занимают меньше памяти, чем классические. Для маленьких ключей — на сотни процентов меньше, для больших — на десятки.
И дать совет: если вам нужен упорядоченный ассоциативный контейнер и вы можете инициализировать его при создании — используйте один из плоских контейнеров, ассимптотически они ничем не хуже простых, но по константе выигрывают. Иначе используйте std::(multi)map
и std::(multi)set
. Если же вам даже не важен порядок — значит, вам не нужны ни плоские контейнеры, ни std::(multi)map
и std::(multi)set
, используйте хэш-таблицу по вашему вкусу, разве что если ваш случай не критичен к скорости итерации — тут плоские контейнеры не знают равных.
Комментарии (3)
Jijiki
06.06.2025 14:50классно спасибо) интересно как они поведут себя там где им место в вокселях(пишу так потомучто 6 граней подразумеваю от центроида по логике отрисовки тоже вокселем), там вся последовательность плоская, я на векторе делал), со всеми оптимизациями(воксельными)) там вообще класс выходит
получается в bvh их тоже можно использовать вроде, надо же только пробежаться ) надо тестить )
Tuxman
06.06.2025 14:50Спасибо за статью. Было бы ещё здорово сравнить с
std::pmr
контейнерами c
monotonic_buffer_resource
.
dyadyaSerezha
Спасибо за интересную статью, но не могу не придраться:
Не в Мбит/Кбит, а в обыденных мега/кило, то есть, в миллионах и тысячах, но байт.