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. У нас есть офисы в Маунтин-Вью, Праге и Бангалоре, и мы всегда ищем первоклассных специалистов, которые помогут нам сформировать будущее хранения данных.
Ссылки на литературу
- Определение std::flat_map в стандарте C++: https://eel.is/c++draft/flat.map
- Ни одна из стандартных библиотек не реализовала std::flat_map по состоянию на октябрь 2023 года, но вы можете найти соответствующую стандарту реализацию, с которой можно поиграться, в репозитории github ответственной рабочей группы комитета C++ https://github.com. /WG21-SG14/SG14/blob/master/SG14/flat_map.h».
- https://en.cppreference.com/w/cpp/header/flat_map
- Интересный доклад Артура О'Дуайера, в котором упоминаются flat_maps и гарантии исключений. Это помогает понять, почему потребовалось так много времени для стандартизации std::flat_map. https://www.youtube.com/watch?v=b9ZYM0d6htg
- Резюме проблем, возникших у комитета с более ранним предложением по std::flat_map https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1727r0.pdf
- У Boost уже давно есть собственная версия flat_map https://www.boost.org/doc/libs/1_80_0/doc/html/boost/container/flat_map.html