std::unordered_map
Определено в заголовочном файле <unordered_map>
|
||
template< class Key, |
(1) | (начиная с C++11) |
namespace pmr { template <class Key, |
(2) | (начиная с C++17) |
std::unordered_map
это ассоциативный контейнер, содержащий пары ключ-значение с уникальными ключами. Поиск, вставка и удаление элементов имеют среднюю постоянную сложность.
Внутри элементы не сортируются в каком-либо определённом порядке, а организованы в сегменты. В какой сегмент помещается элемент, полностью зависит от хеша его ключа. Ключи с одинаковым хэш-кодом находятся в одном сегменте. Это обеспечивает быстрый доступ к отдельным элементам, поскольку после вычисления хэша он обращается к точному сегменту, в котором размещ��н элемент.
Два ключа считаются эквивалентными, если предикат равенства ключей карты возвращает true при передаче этих ключей. Если два ключа эквивалентны, хэш-функция должна возвращать одно и то же значение для обоих ключей.
std::unordered_map
соответствует требованиям Container, AllocatorAwareContainer, UnorderedAssociativeContainer.
Содержание |
[править] Аннулирование итератора
Операции | Недействителен |
---|---|
Все операции только для чтения, swap, std::swap | Ни один |
clear, rehash, reserve, operator= | Все |
insert, emplace, emplace_hint, operator[] | Только если вызывает перехэширование |
erase | Только на стёртый элемент |
[править] Примечание
- Функции обмена не делают недействительными ни один из итераторов внутри контейнера, но они делают недействительным итератор, отмечающий конец области обмена.
- Ссылки и указатели на любой ключ или данные, хранящиеся в контейнере, становятся недействительными только при удалении этого элемента, даже если соответствующий итератор становится недействительным.
[править] Параметры шаблона
Этот раздел не завершён Причина: Добавьте описания параметров шаблона. |
[править] Типы элементы
Тип элемент | Определение |
key_type
|
Key
|
mapped_type
|
T
|
value_type
|
std::pair<const Key, T> |
size_type
|
Беззнаковый целочисленный тип (обычно std::size_t) |
difference_type
|
Знаковый целочисленный тип (обычно std::ptrdiff_t) |
hasher
|
Hash
|
key_equal
|
KeyEqual
|
allocator_type
|
Allocator
|
reference
|
value_type&
|
const_reference
|
const value_type& |
pointer
|
std::allocator_traits<Allocator>::pointer |
const_pointer
|
std::allocator_traits<Allocator>::const_pointer |
iterator
|
LegacyForwardIterator в value_type
|
const_iterator
|
LegacyForwardIterator в const value_type |
local_iterator
|
Тип итератора, category, value, difference, pointer и ссылочные типы которого совпадают с типами iterator . Этот итераторможно использовать для итерации по одному сегменту, но не по сегментам. |
const_local_iterator
|
Тип итератора, category, value, difference, pointer и ссылочные типы которого совпадают с типами const_iterator . Этот итератор можно использовать для итерации по одному сегменту, но не по сегментам.
|
node_type (начиная с C++17)
|
специализация дескриптора узла, представляющая узел контейнера |
insert_return_type (начиная с C++17)
|
тип, описывающий результат вставки node_type , специализацияtemplate <class Iter, class NodeType> struct /*неопределена*/ { |
[править] Функции элементы
(C++11) |
создаёт unordered_map (public функция-элемент) |
(C++11) |
уничтожает unordered_map (public функция-элемент) |
(C++11) |
присваивает значения контейнеру (public функция-элемент) |
(C++11) |
возвращает связанный аллокатор (public функция-элемент) |
Итераторы | |
(C++11) |
возвращает итератор на начало (public функция-элемент) |
(C++11) |
возвращает итератор на конец (public функция-элемент) |
Ёмкость | |
(C++11) |
проверяет, пуст ли контейнер (public функция-элемент) |
(C++11) |
возвращает количество элементов (public функция-элемент) |
(C++11) |
возвращает максимально возможное количество элементов (public функция-элемент) |
Модификаторы | |
(C++11) |
очищает содержимое (public функция-элемент) |
(C++11) |
вставляет элементы или узлы (начиная с C++17) (public функция-элемент) |
(C++23) |
вставляет ряд элементов (public функция-элемент) |
(C++17) |
вставляет элемент или присваивает текущему элементу, если ключ уже существует (public функция-элемент) |
(C++11) |
создаёт элемент на месте (public функция-элемент) |
(C++11) |
создаёт элементы на месте, используя подсказку (public функция-элемент) |
(C++17) |
вставляет "на месте", если ключ не существует, ничего не делает, если ключ существует (public функция-элемент) |
(C++11) |
удаляет элементы (public функция-элемент) |
(C++11) |
обменивает содержимое (public функция-элемент) |
(C++17) |
извлекает узлы из контейнера (public функция-элемент) |
(C++17) |
сливает с узлами из другого контейнера (public функция-элемент) |
Просмотр | |
(C++11) |
предоставляет доступ к указанному элементу с проверкой границ (public функция-элемент) |
(C++11) |
предоставляет доступ к или вставляет указанному элементу (public функция-элемент) |
(C++11) |
возвращает количество элементов, соответствующих определённому ключу (public функция-элемент) |
(C++11) |
ищет элемент с определённым ключом (public функция-элемент) |
(C++20) |
проверяет, содержит ли контейнер элемент с определённым ключом (public функция-элемент) |
(C++11) |
возвращает диапазон элементов, соответствующих определённому ключу (public функция-элемент) |
Интерфейс сегментов | |
возвращает итератор на начало указанного сегмента (public функция-элемент) | |
возвращает итератор на конец указанного сегмента (public функция-элемент) | |
(C++11) |
возвращает количество сегментов (public функция-элемент) |
(C++11) |
возвращает максимальное количество сегментов (public функция-элемент) |
(C++11) |
возвращает количество элементов в конкретном сегменте (public функция-элемент) |
(C++11) |
возвращает сегмент для конкретного ключа (public функция-элемент) |
Политика хеширования | |
(C++11) |
возвращает среднее количество элементов на сегмент (public функция-элемент) |
(C++11) |
управляет максимальным средним количеством элементов на сегмент (public функция-элемент) |
(C++11) |
резервирует как минимум указанное количество сегментов и регенерирует хеш-таблицу (public функция-элемент) |
(C++11) |
резервирует место по крайней мере для указанного количества элементов и регенерирует хеш-таблицу (public функция-элемент) |
Наблюдатели | |
(C++11) |
возвращает функцию, используемую для хэширования ключей (public функция-элемент) |
(C++11) |
возвращает функцию, используемую для сравнения ключей на равенство (public функция-элемент) |
[править] Функции, не являющиеся элементами
(удалено в C++20) |
сравнивает значения в unordered_map (шаблон функции) |
специализация алгоритма std::swap (шаблон функции) | |
(C++20) |
стирает все элементы, соответствующие определённым критериям (шаблон функции) |
Принципы вывода |
(начиная с C++17) |
[править] Примечание
Макрос тест функциональности | Значение | Стандарт | Комментарий |
---|---|---|---|
__cpp_lib_containers_ranges |
202202L | (C++23) | Создание и вставка диапазонов для контейнеров |
[править] Пример
#include <iostream> #include <string> #include <unordered_map> int main() { // Создание unordered_map из трёх строк (которые сопоставляются со строками) std::unordered_map<std::string, std::string> u = { {"КРАСНЫЙ","#FF0000"}, {"ЗЕЛЁНЫЙ","#00FF00"}, {"СИНИЙ","#0000FF"} }; // Вспомогательная лямбда-функция для печати пар ключ-значение auto print_key_value = [](const auto& key, const auto& value) { std::cout << "Ключ:[" << key << "] Значение:[" << value << "]\n"; }; std::cout << "Итерация и печать пар ключ-значение unordered_map,\n" "с явным указанием их типов:\n"; for( const std::pair<const std::string, std::string>& n : u ) { print_key_value(n.first, n.second); } std::cout << "\nИтерация и печать пар ключ-значение, " "используя структурную привязку C++17:\n"; for( const auto& [key, value] : u ) { print_key_value(key, value); } // Добавление двух новых записей в unordered_map u["ЧЁРНЫЙ"] = "#000000"; u["БЕЛЫЙ"] = "#FFFFFF"; std::cout << "\nВывод значений по ключу:\n" "Шестнадцатиричное значение цвета КРАСНЫЙ:[" << u["КРАСНЫЙ"] << "]\n" "Шестнадцатиричное значение цвета ЧЁРНЫЙ:[" << u["ЧЁРНЫЙ"] << "]\n\n"; std::cout << "Используйте operator[] с несуществующим ключом, " "чтобы вставить новую пару ключ-значение:\n"; print_key_value("новый_ключ", u["новый_ключ"]); std::cout << "\nИтерация и печать пар ключ-значение, используя `auto`;\n" "новый_ключ теперь является одним из ключей в карте:\n"; for( const auto& n : u ) { print_key_value(n.first, n.second); } }
Возможный вывод:
Итерация и печать пар ключ-значение unordered_map, с явным указанием их типов: Key:[СИНИЙ] Value:[#0000FF] Key:[ЗЕЛЁНЫЙ] Value:[#00FF00] Key:[КРАСНЫЙ] Value:[#FF0000] Итерация и печать пар ключ-значение, используя структурную привязку C++17: Key:[СИНИЙ] Value:[#0000FF] Key:[ЗЕЛЁНЫЙ] Value:[#00FF00] Key:[КРАСНЫЙ] Value:[#FF0000] Вывод значений по ключу: Шестнадцатиричное значение цвета КРАСНЫЙ:[#FF0000] Шестнадцатиричное значение цвета ЧЁРНЫЙ:[#000000] Используйте operator[] с несуществующим ключом, чтобы вставить новую пару ключ-значение: Key:[новый_ключ] Value:[] Итерация и печать пар ключ-значение, используя `auto`; новый_ключ теперь является одним из ключей в карте: Key:[новый_ключ] Value:[] Key:[БЕЛЫЙ] Value:[#FFFFFF] Key:[ЧЁРНЫЙ] Value:[#000000] Key:[СИНИЙ] Value:[#0000FF] Key:[ЗЕЛЁНЫЙ] Value:[#00FF00] Key:[КРАСНЫЙ] Value:[#FF0000]
[править] Отчёты о дефектах
Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:
Номер | Применён | Поведение в стандарте | Корректное поведение |
---|---|---|---|
LWG 2050 | C++11 | определения reference , const_reference , pointer иconst_pointer были основаны на allocator_type
|
на основе value_type и std::allocator_traits
|
[править] Смотрите также
коллекция п��р ключ-значение, отсортированных по ключам, ключи уникальны (шаблон класса) |
[править] Параметры шаблона
Этот раздел не завершён Причина: Добавьте описания параметров шаблона. |