В 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 ассоциативных контейнеров. Да-да, целых двенадцать штук!
Классифицировать ассоциативные контейнеры можно, ответив на три простых вопроса:
Чтобы объяснить эти характеристики производительности, мне нужно дать вам немного больше информации об ассоциативных контейнерах.
Такое упорядочение имеет ряд интересных следствий для упорядоченных ассоциативных контейнеров:
std::map<int, std::string> int2String{ {3, "three"}, {2, "two"}, {1, "one"},
{5, "five"}, {6, "six"}, {4, "four"}, {7, "seven"} };
Самобалансирующееся бинарное дерево поиска может иметь следующую структуру:
Неупорядоченные ассоциативные контейнеры хранят свои ключи в корзинах. То, в какую корзину попадает ключ, определяется хэш-функцией, которая сопоставляет ключ с уникальным числом. Это число делится по модулю на количество корзин. Если в одну и ту же корзину попадают разные ключи, это называется коллизией. Хорошая хэш-функция равномерно распределяет ключи. Значение просто ассоциируется с ключом.
Использование хэш-функции влечет ряд очень важных следствий для неупорядоченных ассоциативных контейнеров:
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.
Новые плоские ассоциативные контейнеры называются контейнерными адаптерами, поскольку для ключей и значений им требуются отдельные контейнеры последовательностей. Эти последовательности должны поддерживать итераторы произвольного доступа. По умолчанию используется 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 станет доступен.
habr.com
Итак, теперь в 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 — неупорядоченными ассоциативными контейнерами.Классифицировать ассоциативные контейнеры можно, ответив на три простых вопроса:
- Отсортированы ли ключи?
- Имеет ли ключ связанное с ним значение?
- Может ли ключ отображаться более одного раза?
Чтобы объяснить эти характеристики производительности, мне нужно дать вам немного больше информации об ассоциативных контейнерах.
Упорядоченные ассоциативные контейнеры
Ключи упорядоченных ассоциативных контейнеров упорядочены. По умолчанию ключи сравниваются при помощи операции “меньше” (<), и контейнеры сортируются в порядке возрастания.Такое упорядочение имеет ряд интересных следствий для упорядоченных ассоциативных контейнеров:
- Ключ должен поддерживать выбранный способ упорядочения.
- Ассоциативные контейнеры обычно реализуются в виде красно-черных деревьев. Это самобалансирующиеся бинарные деревья поиска.
- Время доступа к ключу и, соответственно, к значению является логарифмическим.
std::map<int, std::string> int2String{ {3, "three"}, {2, "two"}, {1, "one"},
{5, "five"}, {6, "six"}, {4, "four"}, {7, "seven"} };
Самобалансирующееся бинарное дерево поиска может иметь следующую структуру:
Неупорядоченные ассоциативные контейнеры
Основная идея, стоящая за неупорядоченными ассоциативными контейнерами, заключается в том, что ключ распределяется по корзинам (bucket) с помощью хэш-функции. Значение просто прикрепляется к ключу.Неупорядоченные ассоциативные контейнеры хранят свои ключи в корзинах. То, в какую корзину попадает ключ, определяется хэш-функцией, которая сопоставляет ключ с уникальным числом. Это число делится по модулю на количество корзин. Если в одну и ту же корзину попадают разные ключи, это называется коллизией. Хорошая хэш-функция равномерно распределяет ключи. Значение просто ассоциируется с ключом.
Использование хэш-функции влечет ряд очень важных следствий для неупорядоченных ассоциативных контейнеров:
- Хэш-функция для ключа должна быть доступна.
- Для решения проблемы коллизий ключи должны поддерживать сравнение на равенство.
- Время выполнения хэш-функции является константой. Поэтому, если ключи распределены равномерно, то время доступа к ключам неупорядоченного ассоциативного контейнера константно.
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++23: четыре новых ассоциативных контейнера
В C++23 появились четыре новых ассоциативных контейнера: std::flat_map , std::flat_multimap , std::flat_set и std::flat_multiset , которые являются полноценной заменой упорядоченных ассоциативных...
habr.com