std::unordered_map
Определено в заголовочном файле <unordered_map> | ||
|---|---|---|
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;
| (1) | (с C++11) |
namespace pmr {
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>
> using unordered_map =
std::unordered_map<Key, T, Hash, KeyEqual,
std::pmr::polymorphic_allocator<std::pair<const Key, T>>>;
}
| (2) | (с C++17) |
std::unordered_map — это ассоциативный контейнер, содержащий пары ключ-значение с уникальными ключами. Поиск, вставка и удаление элементов имеют среднюю сложность в постоянное время.
Внутри элементы не отсортированы в каком-либо определённом порядке, но организованы в корзины. В какую корзину попадет элемент, полностью зависит от хэша его ключа. Ключи с одинаковым хэш-кодом попадают в одну и ту же корзину. Это позволяет быстро получить доступ к отдельным элементам, так как после вычисления хэша можно сразу определить, в какой корзине находится элемент.
Два ключа считаются эквивалентными, если предикат равенства ключей для карты возвращает true при передаче этих ключей. Если два ключа эквивалентны, функция хэширования должна возвращать одинаковое значение для обоих ключей.
std::unordered_map удовлетворяет требованиям контейнера, контейнера с управлением аллокатором, неупорядоченного ассоциативного контейнера.
Деактивация итераторов
| Операции | Деактивированные итераторы |
|---|---|
Все операции чтения, 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 | Итератор прямой итерации для value_type |
const_iterator | Итератор прямой итерации для const value_type |
local_iterator | Тип итератора, категория, значение, разность, указатель и типы ссылок которого такие же, как у iterator. Эта итерацияможет использоваться для перебора элементов внутри одной корзины, но не между ними |
const_local_iterator | Тип итератора, категория, значение, разность, указатель и типы ссылок которого такие же, как у const_iterator. Эта итерацияможет использоваться для перебора элементов внутри одной корзины, но не между ними |
node_type (с C++17) | Специализация обработчика узла, представляющая узел контейнера |
insert_return_type (с C++17) | Тип, описывающий результат вставки node_type, специализация
|
Члены-функции
создаёт unordered_map (публичный член-функция) |
|
удаляет unordered_map (публичный член-функция) |
|
| присваивает значения контейнеру (публичный член-функция) |
|
| возвращает связанный аллокатор (публичный член-функция) |
|
Итераторы |
|
| возвращает итератор к началу (публичный член-функция) |
|
| возвращает итератор к концу (публичный член-функция) |
|
Ёмкость |
|
| проверяет, пуст ли контейнер (публичный член-функция) |
|
| возвращает количество элементов (публичный член-функция) |
|
| возвращает максимальное возможное количество элементов (публичный член-функция) |
|
Модификаторы |
|
| очищает содержимое (публичный член-функция) |
|
| вставляет элементы или узлы(с C++17) (публичный член-функция) |
|
|
(C++23) | вставляет диапазон элементов (публичный член-функция) |
|
(C++17) | вставляет элемент или присваивает существующему элементу, если ключ уже существует (публичный член-функция) |
| создаёт элемент на месте (публичный член-функция) |
|
| создаёт элементы на месте с подсказкой (публичный член-функция) |
|
|
(C++17) | вставляет на месте, если ключ не существует, ничего не делает, если ключ существует (публичный член-функция) |
| удаляет элементы (публичный член-функция) |
|
| меняет содержимое (публичный член-функция) |
|
|
(C++17) | извлекает узлы из контейнера (публичный член-функция) |
|
(C++17) | вставляет узлы из другого контейнера (публичный член-функция) |
Поиск |
|
| доступ к указанному элементу с проверкой границ (публичный член-функция) |
|
| доступ к или вставка указанного элемента (публичный член-функция) |
|
| возвращает количество элементов, соответствующих заданному ключу (публичный член-функция) |
|
| находит элемент с заданным ключом (публичный член-функция) |
|
|
(C++20) | проверяет, содержит ли контейнер элемент с заданным ключом (публичный член-функция) |
| возвращает диапазон элементов, соответствующих заданному ключу (публичный член-функция) |
|
Интерфейс ведёр |
|
| возвращает итератор к началу указанного ведра (публичный член-функция) |
|
| возвращает итератор к концу указанного ведра (публичный член-функция) |
|
| возвращает количество ведёр (публичный член-функция) |
|
| возвращает максимальное количество ведёр (публичный член-функция) |
|
| возвращает количество элементов в определённом ведре (публичный член-функция) |
|
| возвращает ведро для определённого ключа (публичный член-функция) |
|
Политика хеширования |
|
| возвращает среднее количество элементов на ведро (публичный член-функция) |
|
| управляет максимальным средним количеством элементов на ведро (публичный член-функция) |
|
| резервирует, по крайней мере, указанное количество ведёр и перегенерирует хеш-таблицу (публичный член-функция) |
|
| резервирует место для указанного количества элементов и перегенерирует хеш-таблицу (публичный член-функция) |
|
Наблюдатели |
|
| возвращает функцию, используемую для хэширования ключей (публичный член-функция) |
|
| возвращает функцию, используемую для сравнения ключей на равенство (публичный член-функция) |
|
Нечленные функции
|
(C++11)(C++11)(удалена в C++20) | сравнивает значения в unordered_map (функция-шаблон) |
|
(C++11) | специализация алгоритма std::swap (функция-шаблон) |
|
(C++20) | удаляет все элементы, удовлетворяющие определённым условиям (функция-шаблон) |
Руководства по выводу | (с C++17) |
Примечания
| Макрокоманда проверки наличия функции | Значение | Std | Функция |
|---|---|---|---|
__cpp_lib_containers_ranges | 202202L | (C++23) | Создание и вставка диапазонов для контейнеров |
Пример
#include <iostream>
#include <string>
#include <unordered_map>
int main()
{
// Create an unordered_map of three strings (that map to strings)
std::unordered_map<std::string, std::string> u =
{
{"RED", "#FF0000"},
{"GREEN", "#00FF00"},
{"BLUE", "#0000FF"}
};
// Helper lambda function to print key-value pairs
auto print_key_value = [](const auto& key, const auto& value)
{
std::cout << "Key:[" << key << "] Value:[" << value << "]\n";
};
std::cout << "Iterate and print key-value pairs of unordered_map, being\n"
"explicit with their types:\n";
for (const std::pair<const std::string, std::string>& n : u)
print_key_value(n.first, n.second);
std::cout << "\nIterate and print key-value pairs using C++17 structured binding:\n";
for (const auto& [key, value] : u)
print_key_value(key, value);
// Add two new entries to the unordered_map
u["BLACK"] = "#000000";
u["WHITE"] = "#FFFFFF";
std::cout << "\nOutput values by key:\n"
"The HEX of color RED is:[" << u["RED"] << "]\n"
"The HEX of color BLACK is:[" << u["BLACK"] << "]\n\n";
std::cout << "Use operator[] with non-existent key to insert a new key-value pair:\n";
print_key_value("new_key", u["new_key"]);
std::cout << "\nIterate and print key-value pairs, using `auto`;\n"
"new_key is now one of the keys in the map:\n";
for (const auto& n : u)
print_key_value(n.first, n.second);
}Возможный вывод:
Iterate and print key-value pairs of unordered_map, being explicit with their types: Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000] Iterate and print key-value pairs using C++17 structured binding: Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000] Output values by key: The HEX of color RED is:[#FF0000] The HEX of color BLACK is:[#000000] Use operator[] with non-existent key to insert a new key-value pair: Key:[new_key] Value:[] Iterate and print key-value pairs, using `auto`; new_key is now one of the keys in the map: Key:[new_key] Value:[] Key:[WHITE] Value:[#FFFFFF] Key:[BLACK] Value:[#000000] Key:[BLUE] Value:[#0000FF] Key:[GREEN] Value:[#00FF00] Key:[RED] Value:[#FF0000]
Отчёты об ошибках
Следующие отчёты об ошибках, меняющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.
| DR | Применено к | Поведение, опубликованное | Правильное поведение |
|---|---|---|---|
| LWG 2050 | C++11 | определения reference, const_reference, pointerи const_pointer основывались на allocator_type | основывались на value_type иstd::allocator_traits |
См. также
| коллекция пар ключ-значение, отсортированная по ключам, ключи уникальны (шаблон класса) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/unordered_map