std::unordered_map
Материал из cppreference.com
Определено в заголовочном файле <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 =[](constauto& key, constauto& value){std::cout<<"Ключ:["<< key <<"] Значение:["<< value <<"]\n";}; std::cout<<"Итерация и печать пар ключ-значение unordered_map,\n""с явным указанием их типов:\n";for(conststd::pair<conststd::string, std::string>& n : u ){ print_key_value(n.first, n.second);} std::cout<<"\nИтерация и печать пар ключ-значение, ""используя структурную привязку C++17:\n";for(constauto&[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(constauto& 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 |
[править]Смотрите также
| коллекция пар ключ-значение, отсортированных по ключам, ключи уникальны (шаблон класса) |
[править]Параметры шаблона
| Этот раздел не завершён Причина: Добавьте описания параметров шаблона. |
