C++23: четыре новых ассоциативных контейнера

В C++23 появились четыре новых ассоциативных контейнера: std::flat_map, std::flat_multimap, std::flat_set и std::flat_multiset, которые являются полноценной заменой упорядоченных ассоциативных контейнеров std::map, std::multimap, std::set и std::multiset. Они были добавлены в C++23 по двум причинам: расход памяти и производительность.

Итак, теперь в C++23 мы имеем 12 ассоциативных контейнеров. Да-да, целых двенадцать штук!

• C++98: std::map, std::set, std::multimap и std::multiset

• C++11: std::unordered_map, std::unordered_set, std::unordered_multimap и std::unordered_multiset

• C++23: std::flat_map, std::flat_set, std::flat_multimap и std::flat_multiset

Чтобы мое изложение не теряло систематичности, начну я с ассоциативных контейнеров C++98 и C++11.

Ассоциативный контейнер

Общим для всех ассоциативных контейнеров является то, что они связывают ключ со значением. Таким образом, имея ключ, мы можем получить значение. Ассоциативные контейнеры версии C++98 называются упорядоченными ассоциативными контейнерами, а контейнеры версии C++11 — неупорядоченными ассоциативными контейнерами.

Классифицировать ассоциативные контейнеры можно, ответив на три простых вопроса:

• Отсортированы ли ключи?

• Имеет ли ключ связанное с ним значение?

• Может ли ключ отображаться более одного раза?

Следующая таблица с 2^3 = 8 строками содержит ответы на эти три вопроса. В этой таблице я также ответил на четвертый дополнительный вопрос. Каково среднее время доступа?

Чтобы объяснить эти характеристики производительности, мне нужно дать вам немного больше информации об ассоциативных контейнерах.

Упорядоченные ассоциативные контейнеры

Ключи упорядоченных ассоциативных контейнеров упорядочены. По умолчанию ключи сравниваются при помощи операции “меньше” (<), и контейнеры сортируются в порядке возрастания.

Такое упорядочение имеет ряд интересных следствий для упорядоченных ассоциативных контейнеров:

• Ключ должен поддерживать выбранный способ упорядочения.

• Ассоциативные контейнеры обычно реализуются в виде красно-черных деревьев. Это самобалансирующиеся бинарные деревья поиска.

• Время доступа к ключу и, соответственно, к значению является логарифмическим.

Наиболее часто используемым упорядоченным ассоциативным контейнером является std::map:

std::map<int, std::string> int2String{ {3, "three"}, {2, "two"}, {1, "one"},
                                       {5, "five"}, {6, "six"}, {4, "four"}, {7, "seven"} };

Самобалансирующееся бинарное дерево поиска может иметь следующую структуру:

Неупорядоченные ассоциативные контейнеры

Основная идея, стоящая за неупорядоченными ассоциативными контейнерами, заключается в том, что ключ распределяется по корзинам (bucket) с помощью хэш-функции. Значение просто прикрепляется к ключу.

Неупорядоченные ассоциативные контейнеры хранят свои ключи в корзинах. То, в какую корзину попадает ключ, определяется хэш-функцией, которая сопоставляет ключ с уникальным числом. Это число делится по модулю на количество корзин. Если в одну и ту же корзину попадают разные ключи, это называется коллизией. Хорошая хэш-функция равномерно распределяет ключи. Значение просто ассоциируется с ключом.

Использование хэш-функции влечет ряд очень важных следствий для неупорядоченных ассоциативных контейнеров:

• Хэш-функция для ключа должна быть доступна.

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

• Время выполнения хэш-функции является константой. Поэтому, если ключи распределены равномерно, то время доступа к ключам неупорядоченного ассоциативного контейнера константно.

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

std::unordered_map<std::string, int> str2Int{ {"Grimm",491634333356}, {"Grimm-Jaud", 49160123335}, 
                                              {"Schmidt",4913333318},{"Huber",490001326} };

На графике показано распределение ключей по их корзинам с помощью хэш-функции:

В C++23 появилась полноценная замена упорядоченных ассоциативных контейнеров std::map, std::multimap, std::set и std::multiset — четыре ассоциативных контейнера std::flat_map, std::flat_multimap, std::flat_set и std::flat_multiset.

Контейнеры-адаптеры

“Плоские” ассоциативные контейнеры C++23 имеют тот же интерфейс, что и их родственники из C++98.

Новые плоские ассоциативные контейнеры называются контейнерными адаптерами, поскольку для ключей и значений им требуются отдельные контейнеры последовательностей. Эти последовательности должны поддерживать итераторы произвольного доступа. По умолчанию используется std::vector, но можно использовать и std::array, или std::deque.

В следующем фрагменте кода показан пример объявления std::flat_map и std::flat_set:

template<class Key, class T, 
        class Compare = less<Key>,
        class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
class flat_map;

template<class Key, 
         class Compare = less<Key>, 
         class KeyContainer = vector<Key>>
class flat_set;

Основной причиной появления контейнеров-адаптеров является их производительность.

Сравнение контейнеров-адаптеров и их неплоских вариантов

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

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

Пока я не могу продемонстрировать вам какие-либо цифры касательно новых плоских ассоциативных контейнеров, поскольку ни один компилятор их не поддерживает. Я обновлю свой бенчмарк из "More special Friends with std::map and std::unordered_map", когда std::flat_map станет доступен.

Что дальше?

std::mdspan — это невладеющее многомерное представление непрерывной последовательности объектов. Непрерывная последовательность объектов может быть обычным C-массивом, указателем с размером, std::array, std::vector или std::string.

Материал подготовлен в преддверии старта курса "C++ Developer. Professional" для разработчиков с опытом. Если вам интересно узнать, соответствует ли ваш уровень знаний C++ программе курса, пройдите вступительное тестирование.