flat_maps — это новый контейнерный адаптер в C++23. Как и std::map, это ассоциативный упорядоченный контейнер, что означает, что он позволяет вам вставлять пары ключ-значение и искать ключи позже. В то время как std::map реализован с использованием сбалансированных двоичных деревьев, std::flat_map поддерживает пару отсортированных векторов, один первый для ключей, а второй для значений. Это означает, что std::map имеет лучшую асимптотическую сложность, но std::flat_map может по-прежнему работать лучше из-за удобства кэширования непрерывной памяти. Чтобы лучше это понять, давайте посмотрим, как именно реализован std::flat_map.

Как именно реализован std::flat_map?

std::flat_map реализован с использованием двух контейнеров последовательности (по умолчанию std::vector). Один контейнер содержит ключи в отсортированном порядке, а второй контейнер поддерживает все значения в соответствующем порядке.

Это означает, что вставка выполняется за O(n), потому что, если мы вставляем в начало, нам придется сместить все предыдущие элементы назад. Если вы вставляете сзади, вставка будет O (1), если нет распределения. Это делает его особенно эффективным, если ваш ввод уже отсортирован. Аналогичная логика применяется для удаления.

Это помогает нам понять следующие асимптотические сложности:

+-----------+----------+---------------+
| Operation | std::map | std::flat_map  |
+-----------+----------+---------------+
| Create    | O(nlgn)  | O(nlgn)       |
| Insert    | O(lgn)   | O(n)          |
| Delete    | O(lgn)   | O(n)          |
| Lookup    | O(lgn)   | O(lgn)        |
+-----------+----------+---------------+

Когда полезен std::flat_map?

std::flat_map был представлен потому, что поиск по ключам в непрерывной памяти более удобен для кэширования, чем выполнение многих разыменований памяти, требуемых std::map при обходе двоичного дерева. Однако в приведенной выше таблице сложностей видно, что случайная вставка и удаление являются дорогостоящими операциями, по крайней мере, для больших размеров.

Эмпирическое правило состоит в том, чтобы использовать flat_maps, когда вставки и удаления происходят редко и в основном требуются поиск и итерация. Это случаи использования, когда std::flat_map сияет, и вы можете извлечь выгоду из его удобства для кэширования.

Как использовать std::flat_map?

Плоская карта в основном используется как std::map. Есть некоторые предостережения относительно стабильности итератора, и извлечение узлов не поддерживается. Вы можете посмотреть в стандарте для более подробной информации.

std::flat_map<int, int> my_map;
map[0] = 500;
map[4] = 3;

Закрытие комментариев

Вместе с std::flat_map комитет также представил std::flat_multimap, std::flat_set и std::flat_multiset в cpp23. Как вы можете себе представить, мультиверсии допускают дублирование ключей, а наборы поддерживают только один массив ключей без значений.

Также обратите внимание, что довольно легко свернуть собственную версию flat_map, используя std::pair и один вектор. Наличие двух отдельных векторов более удобно для кэширования, поэтому оно используется в стандарте.

Если вам понравилась эта статья и вы заинтересованы в написании высокопроизводительного программного обеспечения, масштабируемого для десятков процессоров, рассмотрите возможность присоединиться к нашей команде в Pure Storage. У нас есть офисы в Маунтин-Вью, Праге и Бангалоре, и мы всегда ищем первоклассных специалистов, которые помогут нам сформировать будущее хранения данных.

Ссылки на литературу