Плоские контейнеры в C++23

Новый стандарт 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

Если же сравнивать асимптотическую сложность операций в плоских и не плоских контейнерах, то получим следующее:

Асимптотически, казалось бы, мы не очень выигрываем. Тем не менее, по сравнению с (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'; } 

В чём же 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).

Результаты бенчмарков от 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, используйте хэш-таблицу по вашему вкусу, разве что если ваш случай не критичен к скорости итерации — тут плоские контейнеры не знают равных.