Новый стандарт 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() в таком случае реализуется как обычный бинарный поиск (со сложностью O(log\ N)). Так вот, так же (но более обобщенно) устроен и 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)

В среднем O(1)

O(log\ N)

O(N)

erase(value)

В среднем O(1)

O(log\ N)

O(N)

find(value)

В среднем O(1)

O(log\ N)

O(log\ N)

Примечание к таблице

В таблице выше, для полноты картины, было приведено сравнение всех имеющихся в стандартной библиотеке ассоциативных контейнеров.

Однако дальше в тексте, главным образом, будут сравниваться лишь упорядоченные контейнеры: std::(multi)set/map и новые плоские контейнеры (которые также являются упорядоченными) std::flat_(multi)set/map.

О неупорядоченных контейнерах — контейнерах, основанных на хэш-таблицах, говориться не будет, так как неупорядоченные и упорядоченные контейнеры — разного поля ягоды. Если вам не нужен порядок, то вам, за очень редкими исключениями (которые будут отмечены в заключении), и не нужны плоские контейнеры — хэш-таблицы во всём будут быстрей.

Асимптотически, казалось бы, мы не очень выигрываем. Тем не менее, по сравнению с (multi)set и (multi)map «плоская» реализация имеет и некоторые плюсы: более быструю итерацию, меньшее потребление памяти и лучшую кэш-локальность.

Но взамен нас неминуемо ждут менее стабильные итераторы, способные инвалидироваться на любой вставке и удалении; невозможность хранения не-копируемых и не-перемещаемых типов; более слабые гарантии безопасности исключений (никто не защитит нас от исключений в конструкторах копирования/перемещения при сдвиге элементов в ходе вставки/удаления) и более медленные вставки и удаления (мало того, что нам нужно поддерживать отсортированность, так ведь при каждой вставке в наш вектор нам нужно двигать элементы)

Более спорный вопрос: получим ли мы более быстрый поиск? (его сложность —O(log\ N)как в плоских, так и не в плоских контейнерах) Один из классиков С++, 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).

Результаты бенчмарков от Zach Laine
Оригинальные изображения: insert, iterate, lookup
Оригинальные изображения: insert, iterate, lookup

В остальном стандартизированные контейнеры отличаются от их предков из Boost и Loki лишь большей обобщенностью: AssocVector не позволяет изменять тип хранилища, в котором будут лежать данные — там всегда используется std::vector; контейнеры из Boost не позволяли этого вплоть до Boost 1.66, но даже сейчас, когда на дворе уже Boost 1.88, в реализации этой фичи до сих пор чинят баги.

Однако, в одной из ранних реализаций плоских контейнеров, ETL, всё же есть одна занятная особенность, заслуживающая упоминания: в целях улучшения производительности операций вставки, в ней плоские контейнеры реализованы не как отсортированные массивы (плоские контейнеры в ETL имеют ограниченный размер, задаваемый как шаблонный параметр) значений, а как массивы указателей на значения. При этом значения, конечно, вынуждены храниться в отдельном контейнере. С одной стороны мы получаем чуть более быструю вставку за счет того, что указатели относительно дешево копировать, а с другой чуть более долгий доступ к элементам за счет того, что до них нам теперь придется ходить через указатель.

Авторы ETL не приводят никаких сравнений производительности своей реализации с какими-либо другими реализациями, поэтому сделаем их самостоятельно.

Попробуем последовательно повставлять N пар с ключом — псевдо(случайно) сгенерированным int64_t, а значением — захардкоженным int64_t{1} и замерим, сколько времени это займет. На всех графиках ниже по оси X — количество пар в контейнере (шт.), по оси Y — время работы программы (в секундах или миллисекундах — см. подписи на графиках) или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}.

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

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный 50-символьный string, значение — int64_t{1}.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный 50-символьный string, значение — int64_t{1}.

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

Графики потребления памяти тут

Для int64_t:

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

:

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

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

Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный std::string, значение — int64_t{1}.
Бенчмарк последовательного поиска N элементов в контейнере в случайном порядке. Ключ — случайный std::string, значение — int64_t{1}.

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

Бенчмарк итерации по N элементам в контейнере. Ключ — случайный int64_t, значение — int64_t{1}.
Бенчмарк итерации по N элементам в контейнере. Ключ — случайный int64_t, значение — int64_t{1}.

По-прежнему быстро!

Нужно ли нам ускорение вставки при том, что по своей природе плоские контейнеры созданы для того, чтобы в них один раз при создании всё вставить и больше не вставлять — вопрос открытый, но, тем не менее, спасибо ETL за интересную реализацию.

Замеры

Наконец, поставим точку в вопросе, быстрее ли в плоских контейнерах поиск, чем не в плоских. Но не будем мелочиться, и сравним плоские контейнеры не только с их не плоскими аналогами, но и с контейнерами, основанными на хэш-таблицах: std::unordered_set, std::unordered_map.

Замеры будем проводить по заветам статьи «Benchmark of major hash maps implementations» за авторством Tessil (Thibaut Goetghebuer-Planchon) — измерим скорость вставки, удаления и поиска для трёх видов ключей-значений: int64_tint64_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_tint64_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 с значениями [0, N) и перемешиваем этот вектор с помощью функции std::shuffle. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

Вставки пар с случайным ключом

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

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

Удаление пар с случайным ключом

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

Поиск пар

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

Итерирование

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

string (15 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

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

Удаление пар с случайным ключом

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

string (50 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

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

Удаление пар с случайным ключом

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

Диапазон 10'000–100'000 (шаг 20'000)
int64_t — int64_t

Вставки в случайной порядке

Перед каждым замером мы создаем std::vector с значениями [0, N) и перемешиваем этот вектор с помощью функции std::shuffle. Затем для каждого значения k в векторе мы вставляем пару ключ-значение (k, 1) в контейнер.

Вставки пар с случайным ключом

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

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

Удаление пар с случайным ключом

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

Поиск пар

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

Итерирование

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

string (15 символов) — int64_t

Вставки пар с случайным ключом

Мы N раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

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

Удаление пар с случайным ключом

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

Поиск пар с случайным ключом

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

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

string (50 символов) — int64_t

Вставки пар с случайным ключом

МыN раз генерируем строку-ключ и вставляем ее в контейнер с значением std::int64_t{1}.

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

Удаление пар с случайным ключом

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Поиск после удаления половины

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

Диапазон 200'000–3'000'000 (шаг 200'000)

Вставлять сотни тысяч и миллионы элементов в плоские контейнеры слишком медленно, поэтому тут я произвел только бенчмарки поиска и итерации.

int64_t — int64_t

Поиск пар

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

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Итерирование

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

string (15 символов) — int64_t

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

string (50 символов) — int64_t

Поиск пар с случайным ключом

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

Поиск несуществующих пар

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

Итак, производить много одиночных вставок в плоские контейнеры, как и ожидалось, очень медленно (я даже не смог дождаться прохождения замеров для N \in [200\ 000, 3\ 000\ 000], поэтому провел замеры вставки и удаления для N \in [20\ 000, 100\ 000]): хоть найти место для вставки занимает O(log \  N), но сложность вставки в вектор — по-прежнему O(N).

Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк последовательной вставки N элементов в контейнер. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

Удаление также ничем не отличается от вставки: плоские контейнеры драматически проигрывают классическим.

Посмотрите сами, если не верите

Осторожно, графики std::flat_map и boost::containers::flat_map сливаются в одну линию!

Бенчмарк последовательного удаления N элементов в рандомном порядке. Ключи и значения — как в предыдущем бенчмарке. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк последовательного удаления N элементов в рандомном порядке. Ключи и значения — как в предыдущем бенчмарке. Ось X — количество элементов. Ось Y — время работы программы.

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

Интересно, но при удалении такой прирост не наблюдается, хотя, казалось бы, операции максимально похожи.

Если смотреть же на скорость поиска, то тут, при малых размерах ключей, например, 8-байтном std::int64_t, и больших объемах, плоские контейнеры существенно превосходят классические упорядоченные контейнеры.

Бенчмарк поиска пар в случайном порядке. Ключи и значения — как в бенчмарке вставки. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключи и значения — как в бенчмарке вставки. Ось X — количество элементов. Ось Y — время работы программы.

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

Бенчмарк поиска пар в случайном порядке. Ключ — случайный 15-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный 15-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

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

Бенчмарк поиска пар в случайном порядке. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

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

Бенчмарк поиска пар в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк поиска пар в случайном порядке. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

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

Если же говорить про итерацию, то тут плоские контейнеры одерживают верх над всеми своими соперниками без исключений.

Бенчмарк итерации по парам. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.
Бенчмарк итерации по парам. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — время работы программы.

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

Граф потребления ОЗУ. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.
Граф потребления ОЗУ. Ключ — случайный int64_t, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.

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

Граф потребления ОЗУ. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.
Граф потребления ОЗУ. Ключ — случайный 50-символьный std::string, значение — int64_t{1}. Ось X — количество элементов. Ось Y — объем занимаемой контейнером оперативной памяти.

Итог

Таким образом, можно сделать следующие выводы:

  • Вставка и удаление элементов из плоских контейнеров это ужасно дорого, и лучше делать это как можно реже.

  • Поиск в плоских контейнерах действительно сильно быстрее, чем в классических упорядоченных ассоциативных, но только при больших объемах данных (> 1'000'000 пар) и маленьких размерах ключей. Если пар меньше (20'000–100'000) или ключи большие, то он быстрее, но не сильно. Если же пар совсем мало (10–100), то они оказываются даже медленнее.

  • График времени итерации по плоским контейнерам невероятно красив — он практически плоский. По скорости итерации плоские контейнеры обгоняют все остальные контейнеры на порядки.

  • Плоские контейнеры занимают меньше памяти, чем классические. Для маленьких ключей — на сотни процентов меньше, для больших — на десятки.

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

Комментарии (3)


  1. dyadyaSerezha
    06.06.2025 14:50

    Спасибо за интересную статью, но не могу не придраться:

    или объем занимаемой контейнером оперативной памяти (в Мбит или Кбит — см. подписи на графиках).

    Не в Мбит/Кбит, а в обыденных мега/кило, то есть, в миллионах и тысячах, но байт.


  1. Jijiki
    06.06.2025 14:50

    классно спасибо) интересно как они поведут себя там где им место в вокселях(пишу так потомучто 6 граней подразумеваю от центроида по логике отрисовки тоже вокселем), там вся последовательность плоская, я на векторе делал), со всеми оптимизациями(воксельными)) там вообще класс выходит

    получается в bvh их тоже можно использовать вроде, надо же только пробежаться ) надо тестить )


  1. Tuxman
    06.06.2025 14:50

    Спасибо за статью. Было бы ещё здорово сравнить с std::pmr контейнерами c
    monotonic_buffer_resource.