Spec-Zone.ru › C++

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, специализация

template<class Iter, class NodeType> struct /*unspecified*/ { Iter position; bool inserted; NodeType node; };
с шаблоновыми аргументами iterator и node_type.

Члены-функции

(конструктор)
создаёт unordered_map
(публичный член-функция)
(деструктор)
удаляет unordered_map
(публичный член-функция)
operator=
присваивает значения контейнеру
(публичный член-функция)
get_allocator
возвращает связанный аллокатор
(публичный член-функция)
Итераторы
begincbegin
возвращает итератор к началу
(публичный член-функция)
endcend
возвращает итератор к концу
(публичный член-функция)
Ёмкость
empty
проверяет, пуст ли контейнер
(публичный член-функция)
size
возвращает количество элементов
(публичный член-функция)
max_size
возвращает максимальное возможное количество элементов
(публичный член-функция)
Модификаторы
clear
очищает содержимое
(публичный член-функция)
insert
вставляет элементы или узлы(с C++17)
(публичный член-функция)
insert_range
(C++23)
вставляет диапазон элементов
(публичный член-функция)
insert_or_assign
(C++17)
вставляет элемент или присваивает существующему элементу, если ключ уже существует
(публичный член-функция)
emplace
создаёт элемент на месте
(публичный член-функция)
emplace_hint
создаёт элементы на месте с подсказкой
(публичный член-функция)
try_emplace
(C++17)
вставляет на месте, если ключ не существует, ничего не делает, если ключ существует
(публичный член-функция)
erase
удаляет элементы
(публичный член-функция)
swap
меняет содержимое
(публичный член-функция)
extract
(C++17)
извлекает узлы из контейнера
(публичный член-функция)
merge
(C++17)
вставляет узлы из другого контейнера
(публичный член-функция)
Поиск
at
доступ к указанному элементу с проверкой границ
(публичный член-функция)
operator[]
доступ к или вставка указанного элемента
(публичный член-функция)
count
возвращает количество элементов, соответствующих заданному ключу
(публичный член-функция)
find
находит элемент с заданным ключом
(публичный член-функция)
contains
(C++20)
проверяет, содержит ли контейнер элемент с заданным ключом
(публичный член-функция)
equal_range
возвращает диапазон элементов, соответствующих заданному ключу
(публичный член-функция)
Интерфейс ведёр
begin(size_type)cbegin(size_type)
возвращает итератор к началу указанного ведра
(публичный член-функция)
end(size_type)cend(size_type)
возвращает итератор к концу указанного ведра
(публичный член-функция)
bucket_count
возвращает количество ведёр
(публичный член-функция)
max_bucket_count
возвращает максимальное количество ведёр
(публичный член-функция)
bucket_size
возвращает количество элементов в определённом ведре
(публичный член-функция)
bucket
возвращает ведро для определённого ключа
(публичный член-функция)
Политика хеширования
load_factor
возвращает среднее количество элементов на ведро
(публичный член-функция)
max_load_factor
управляет максимальным средним количеством элементов на ведро
(публичный член-функция)
rehash
резервирует, по крайней мере, указанное количество ведёр и перегенерирует хеш-таблицу
(публичный член-функция)
reserve
резервирует место для указанного количества элементов и перегенерирует хеш-таблицу
(публичный член-функция)
Наблюдатели
hash_function
возвращает функцию, используемую для хэширования ключей
(публичный член-функция)
key_eq
возвращает функцию, используемую для сравнения ключей на равенство
(публичный член-функция)

Нечленные функции

operator==operator!=
(C++11)(C++11)(удалена в C++20)
сравнивает значения в unordered_map
(функция-шаблон)
std::swap(std::unordered_map)
(C++11)
специализация алгоритма std::swap
(функция-шаблон)
erase_if(std::unordered_map)
(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

См. также

map
коллекция пар ключ-значение, отсортированная по ключам, ключи уникальны
(шаблон класса)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/unordered_map

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API