C++ именованные требования: UnorderedAssociativeContainer (с C++11)
Неупорядоченные ассоциативные контейнеры — это контейнеры, которые обеспечивают быстрый поиск объектов по ключам. В худшем случае сложность линейная, но в среднем значительно быстрее для большинства операций.
Неупорядоченные ассоциативные контейнеры параметризуются Key; Hash, объектом-функцией хеширования, которая действует как функция хеширования для Key; и Pred, бинарным предикатом, оценивающим эквивалентность между Key. std::unordered_map и std::unordered_multimap также имеют связанный тип отображения T для Key.
Если два Key равны в соответствии с Pred, то Hash должно возвращать одинаковое значение для обоих ключей.
| Если и | (с C++20) |
std::unordered_map и std::unordered_set могут содержать не более одного элемента с данным ключом, std::unordered_multiset и std::unordered_multimap вместо этого могут содержать несколько элементов с одинаковым ключом (которые всегда должны быть смежными при итерациях).
Для std::unordered_set и std::unordered_multiset тип значения совпадает с типом ключа, и iterator и const_iterator являются константными итераторами. Для std::unordered_map и std::unordered_multimap тип значения — std::pair<const Key, T>.
Элементы неупорядоченного ассоциативного контейнера организованы в ведра; ключи с одинаковым хешем будут находиться в одном ведре. Количество ведер увеличивается при увеличении размера контейнера, чтобы среднее количество элементов в каждом ведре оставалось ниже определенного значения.
Перехеширование делает недействительными итераторы и может привести к переупорядочению элементов в разных ведрах, но не делает недействительными ссылки на элементы.
Неупорядоченные ассоциативные контейнеры удовлетворяют требованиям AllocatorAwareContainer. Для std::unordered_map и std::unordered_multimap требования value_type в AllocatorAwareContainer применяются к key_type и mapped_type (не к value_type).
Требования
Легенда |
|
X | Класс неупорядоченного ассоциативного контейнера |
a | Значение типа X |
a2 | Значение типа с узлами, совместимыми с типом X |
b | Значение типа X или const X |
a_uniq | Значение типа X при поддержке уникальных ключей X |
a_eq | Значение типа X при поддержке эквивалентных ключей X |
a_tran | Значение типа X или const X при наличии обоих qualified-id X::key_equal::is_transparent и X::hasher::is_transparent, которые обозначают типы |
i, j | Входные итераторы, которые ссылаются на value_type |
[i, j) | Действительный диапазон |
rg (с C++23) | Значение типа R, моделирующего container-compatible-range<value_type> |
p, q2 | Действительные константные итераторы на a |
q, q1 | Действительные обратимые константные итераторы на a |
r | Действительный обратимый итератор на a |
[q1, q2) | Действительный диапазон в a |
il | Значение типа std::initializer_list<value_type> |
t | Значение типа X::value_type |
k | Значение типа key_type |
hf | Значение типа hasher или const hasher |
eq | Значение типа key_equal или const key_equal |
ke | Значение, такое что
где |
kx (с C++23) | Значение, такое что
где |
n | Значение типа size_type |
z | Значение типа float |
nh (с C++17) | Ссылка на временное значение типа X::node_type |
Типы
| Название | Тип | Требования | Примечания |
|---|---|---|---|
X::key_type |
Key | ||
X::mapped_type |
T |
std::unordered_map и std::unordered_multimap только | |
X::value_type |
Key |
std::unordered_set и std::unordered_multiset только. Erasable в X | |
std::pair<const Key, T> |
std::unordered_map и std::unordered_multimap только. Erasable в X | ||
X::hasher |
Hash | Хеширование | |
X::key_equal |
Pred |
CopyConstructible; BinaryPredicate, принимающая два аргумента типа Key и выражающая отношение эквивалентности | |
X::local_iterator | LegacyIterator | Категория и типы такие же, как X::iterator | Можно использовать для итерации по одному ведру, но не по всем ведрам |
X::const_local_iterator | LegacyIterator | Категория и типы такие же, как X::const_iterator |
|
X::node_type (с C++17) | Специализация шаблона класса node-handle | Общедоступные вложенные типы такие же, как соответствующие типы в X |
Члены и операторы
| Выражение | Результат | Предпосылки | Эффекты | Возвращаемое значение | Сложность |
|---|---|---|---|---|---|
X(n, hf, eq) | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и eq в качестве предиката равенства ключей | O(n) |
|||
X(n, hf) |
key_equal является DefaultConstructible | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и key_equal() в качестве предиката равенства ключей | O(n) |
||
X(n) |
hasher и key_equal являются DefaultConstructible | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей | O(n) |
||
X a = X();X a; |
hasher и key_equal являются DefaultConstructible | Создаёт пустой контейнер с неопределённым количеством корзин, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей | Постоянная | ||
X(i, j, n, hf, eq) |
value_type является EmplaceConstructible в X из *i | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и eq в качестве предиката равенства ключей, и вставляет элементы из [i, j) в него | Средний случай O(N) (N — std::distance(i, j)), худший случай O(N2) |
||
X(i, j, n, hf) |
key_equal является DefaultConstructible. value_type является EmplaceConstructible в X из *i | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из [i, j) в него | Средний случай O(N) (N — std::distance(i, j)), худший случай O(N2) |
||
X(i, j, n) |
hasher и key_equal являются DefaultConstructible. value_type является EmplaceConstructible в X из *i | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из [i, j) в него | Средний случай O(N) (N — std::distance(i, j)), худший случай O(N2) |
||
X(i, j) |
hasher и key_equal являются DefaultConstructible. value_type является EmplaceConstructible в X из *i | Создаёт пустой контейнер с неопределённым количеством корзин, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из [i, j) в него | Средний случай O(N) (N — std::distance(i, j)), худший случай O(N2) |
||
X(std::from_range,(с C++23) |
value_type является EmplaceConstructible в X из *ranges::begin(rg) | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и eq в качестве предиката равенства ключей, и вставляет элементы из rg в него | Средний случай O(N) (N — ranges::distance(rg)), худший случай O(N2) |
||
X(std::from_range,(с C++23) |
key_equal является DefaultConstructible. value_type является EmplaceConstructible в X из *ranges::begin(rg) | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hf в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из rg в него | Средний случай O(N) (N — ranges::distance(rg)), худший случай O(N2) |
||
X(std::from_range,(с C++23) |
hasher и key_equal являются DefaultConstructible. value_type является EmplaceConstructible в X из *ranges::begin(rg) | Создаёт пустой контейнер с по меньшей мере n корзинами, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из rg в него | Средний случай O(N) (N — ranges::distance(rg)), худший случай O(N2) |
||
X(std::from_range,(с C++23) |
hasher и key_equal являются DefaultConstructible. value_type является EmplaceConstructible в X из *ranges::begin(rg) | Создаёт пустой контейнер с неопределённым количеством корзин, используя hasher() в качестве функции хеширования и key_equal() в качестве предиката равенства ключей, и вставляет элементы из rg в него | Средний случай O(N) (N — ranges::distance(rg)), худший случай O(N2) |
||
X(il) |
X(il.begin(), il.end()) | ||||
X(il, n) |
X(il.begin(), il.end(), n) | ||||
X(il, n, hf) |
X(il.begin(), il.end(), n, hf) | ||||
X(il, n, hf, eq) |
X(il.begin(), il.end(), n, hf, eq) | ||||
X(b) | Контейнер; Копирует функцию хеширования, предикат и максимальный коэффициент заполнения | Средний случай линейный по b.size(), худший случай O(N2) |
|||
a = b |
X& | Контейнер; копирует функцию хеширования, предикат и максимальный коэффициент заполнения | Средний случай линейный по b.size(), худший случай O(N2) |
||
a = il |
X& |
value_type является CopyInsertable в X и CopyAssignable | Присваивает диапазон [il.begin(), il.end()) в a. Все существующие элементы a либо присваиваются, либо уничтожаются | Средний случай линейный по il.size(), худший случай O(N2) |
|
b.hash_function() |
hasher |
Функция хеширования b | Постоянная | ||
b.key_eq() |
key_equal |
Предикат равенства ключей b | Постоянная | ||
a_uniq.emplace(args) |
std::pair< |
value_type является EmplaceConstructible в X из args | Вставляет объект value_type t сконструированный с std::forward<Args>(args)..., если и только если в контейнере нет элемента с ключом, эквивалентным ключу t | Компонент bool возвращаемой пары — true, если и только если вставка произошла, а итератор-компонент пары указывает на элемент с ключом, эквивалентным ключу t | Средний случай O(1), худший случай O(a_uniq.size()) |
a_eq.emplace(args) |
iterator |
value_type является EmplaceConstructible в X из args | Вставляет объект value_type, t построенный с помощью std::forward<Args>(args)... | Итератор, указывающий на недавно вставленный элемент | Среднее время O(1), наихудший случай O(a_eq.size()) |
a.emplace_hint(p, args) |
iterator |
value_type является EmplaceConstructible в X из args |
a.emplace( | Итератор, указывающий на элемент с ключом, эквивалентным ключу недавно вставленного элемента. const_iterator p — подсказка, указывающая, с чего следует начать поиск. Реализации могут игнорировать подсказку | Среднее время O(1), наихудший случай O(a.size()) |
a_uniq.insert(t) |
std::pair< | Если t — неконстантное rvalue, value_type является MoveInsertable в X; в противном случае, value_type является CopyInsertable в X | Вставляет t, если и только если в контейнере нет элемента с ключом, эквивалентным ключу t | Компонент bool возвращаемой пары указывает, произошла ли вставка, а компонент iterator указывает на элемент с ключом, эквивалентным ключу t | Среднее время O(1), наихудший случай O(a_uniq.size()) |
a_eq.insert(t) |
iterator | Если t — неконстантное rvalue, value_type является MoveInsertable в X; в противном случае, value_type является CopyInsertable в X | Вставляет t | Итератор, указывающий на недавно вставленный элемент | Среднее время O(1), наихудший случай O(a_eq.size()) |
a.insert(p, t) |
iterator | Если t — неконстантное rvalue, value_type является MoveInsertable в X; в противном случае, value_type является CopyInsertable в X |
a.insert(t). Итератор p — подсказка, указывающая, с чего следует начать поиск. Реализации могут игнорировать подсказку | Итератор, указывающий на элемент с ключом, эквивалентным ключу t | Среднее время O(1), наихудший случай O(a.size()) |
a.insert(i, j) |
void |
value_type является EmplaceConstructible в X из *i. Ни i, ни j не являются итераторами в a |
a.insert(t) для каждого элемента в[i, j) | Среднее время O(N), где N — std::distance(i, j), наихудший случай O(N·(a.size() + 1)) |
|
a.insert_range(rg)(since C++23) |
void |
value_type является EmplaceConstructible в X из *ranges::begin(rg). rg и a не перекрываются |
a.insert(t) для каждого элемента t в rg | Среднее время O(N), где N — ranges::distance(rg), наихудший случай O(N·(a.size() + 1)) |
|
a.insert(il) |
a.insert(il.begin(), il.end()) | ||||
a_uniq.insert(nh)(since C++17) |
insert_return_type |
nh пусто или
| Если nh пусто, не оказывает никакого эффекта. Иначе, вставляет элемент, принадлежащий nh, если и только если в контейнере нет элемента с ключом, эквивалентным nh.key(). Обеспечивает: Если nh пусто, inserted равно false, position равно end(), и node пусто. В противном случае, если вставка произошла, inserted равно true, position указывает на вставленный элемент, и node пусто; если вставка не удалась, inserted равно false, node сохраняет предыдущее значение nh, и position указывает на элемент с ключом, эквивалентным nh.key() | Среднее время O(1), наихудший случай O(a_uniq.size()) |
|
a_eq.insert(nh)(since C++17) |
iterator |
nh пусто или
| Если nh пусто, не оказывает никакого эффекта и возвращает a_eq.end(). В противном случае, вставляет элемент, принадлежащий nh, и возвращает итератор, указывающий на вновь вставленный элемент. Обеспечивает: nh пусто | Среднее время O(1), наихудший случай O(a_eq.size()) |
|
a.insert(q, nh)(since C++17) |
iterator |
nh пусто или
| Если nh пусто, не оказывает никакого эффекта и возвращает a.end(). В противном случае, вставляет элемент, принадлежащий nh, если и только если в контейнере с уникальными ключами нет элемента с ключом, эквивалентным nh.key(); всегда вставляет элемент, принадлежащий nh, в контейнерах с эквивалентными ключами. Итератор q — подсказка, указывающая, с чего следует начать поиск. Реализации могут игнорировать подсказку. Обеспечивает: nh пусто, если вставка удалась, неизменен, если вставка не удалась | Итератор, указывающий на элемент с ключом, эквивалентным nh.key() | Среднее время O(1), наихудший случай O(a.size()) |
a.extract(k)(since C++17) |
node_type | Удаляет элемент в контейнере с ключом, эквивалентным k | node_type владеющий элементом, если он найден, в противном случае пустое node_type | Среднее время O(1), наихудший случай O(a.size()) |
|
a_tran.extract(kx)(since C++23) |
node_type | Удаляет элемент в контейнере с ключом, эквивалентным kx | node_type владеющий элементом, если он найден, в противном случае пустое node_type | Среднее время O(1), наихудший случай O(a_tran.size()) |
|
a.extract(q)(since C++17) |
node_type | Удаляет элемент, на который указывает q | node_type владеющий этим элементом | Среднее время O(1), наихудший случай O(a.size()) |
|
a.merge(a2)(since C++17) |
void |
a.get_allocator()==a2.get_allocator() | Пытается извлечь каждый элемент из a2 и вставить его в a с использованием хеш-функции и предиката равенства ключей a. В контейнерах с уникальными ключами, если в a есть элемент с ключом, эквивалентным ключу элемента из a2, то этот элемент не извлекается из a2. Обеспечивает: Указатели и ссылки на перенесенные элементы из a2 ссылаются на те же элементы, но как члены a. Итераторы, ссылающиеся на перенесенные элементы, и все итераторы, ссылающиеся на a, будут недействительными, но итераторы на элементы, оставшиеся в a2, останутся действительными | Среднее время O(N), где N — a2.size(), наихудший случай O(N·(a.size() + 1)) |
|
a.erase(k) |
size_type | Удаляет все элементы с ключом, эквивалентным k | Количество удаленных элементов | Среднее время O(a.count(k)), наихудший случай O(a.size()) |
|
a_tran.erase(kx)(since C++23) |
size_type | Удаляет все элементы с ключом, эквивалентным kx | Количество удаленных элементов | Среднее время O(a_tran.count(kx)), наихудший случай O(a_tran.size()) |
|
a.erase(q) |
iterator | Удаляет элемент, на который указывает q | Итератор, следующий сразу после q перед удалением | Среднее время O(1), наихудший случай O(a.size()) |
|
a.erase(r)(since C++17) |
iterator | Удаляет элемент, на который указывает r | Итератор, следующий сразу после r перед удалением | Среднее время O(1), наихудший случай O(a.size()) |
a.erase(q1, q2) |
iterator | Удаляет все элементы в диапазоне[q1, q2) | Итератор, следующий за удалёнными элементами до удаления | Среднее время линейно от std::distance(q1, q2), наихудший случай O(a.size()) |
|
a.clear() |
void | Удаляет все элементы в контейнере. Гарантирует: a.empty() равно true | Линейно от a.size() |
||
b.find(k) |
iterator; const_iterator для константного b | Итератор, указывающий на элемент с ключом, эквивалентным k, или b.end() если такого элемента нет | Средний случай O(1), наихудший случай O(b.size()) |
||
a_tran.find(ke)(с C++17)? |
iterator; const_iterator для константного a_tran | Итератор, указывающий на элемент с ключом, эквивалентным ke, или a_tran.end() если такого элемента нет | Средний случай O(1), наихудший случай O(a_tran.size()) |
||
b.count(k) |
size_type | Количество элементов с ключом, эквивалентным k | Средний случай O(b.count(k)), наихудший случай O(b.size()) |
||
a_tran.count(ke)(с C++17)? |
size_type | Количество элементов с ключом, эквивалентным ke | Средний случай O(a_tran.count(ke)), наихудший случай O(a_tran.size()) |
||
b.contains(k)(с C++20)? |
b.find(k) != b.end() | ||||
a_tran.contains(ke)(с C++20)? |
a_tran.find(ke) != a_tran.end() | ||||
b.equal_range(k) |
std::pair<;
| Диапазон, содержащий все элементы с ключами, эквивалентными k. Возвращает
| Средний случай O(b.count(k)), наихудший случай O(b.size()) |
||
a_tran.equal_range(ke)(с C++20)? |
std::pair<;
| Диапазон, содержащий все элементы с ключами, эквивалентными ke. Возвращает
| Средний случай O(a_tran.count(ke)), наихудший случай O(a_tran.size()) |
||
b.bucket_count() |
size_type | Количество бакетов, которое b содержит | Постоянное | ||
b.max_bucket_count() |
size_type | Верхняя граница количества бакетов, которое b может содержать | Постоянное | ||
b.bucket(k) |
size_type |
b.bucket_count() > 0 | Индекс бакета, в котором будут найдены элементы с ключами, эквивалентными k, если таковые существуют. Результат в [0, b.bucket_count()) | Постоянное | |
b.bucket_size(n) |
size_type |
n находится в [0, b.bucket_count()) | Количество элементов в n-м бакете | O(b.bucket_size(n)) |
|
b.begin(n) |
local_iterator; const_local_iterator для константного b |
n находится в [0, b.bucket_count()) | Итератор, ссылающийся на первый элемент в бакете. Если бак пуст, то b.begin(n) == b.end(n) | Постоянное | |
b.end(n) |
local_iterator; const_local_iterator для константного b |
n находится в [0, b.bucket_count()) | Итератор, который является значением "после конца" для бакета | Постоянное | |
b.cbegin(n) |
const_local_iterator |
n находится в [0, b.bucket_count()) | Итератор, ссылающийся на первый элемент в бакете. Если бак пуст, то b.cbegin(n) == b.cend(n) | Постоянное | |
b.cend(n) |
const_local_iterator |
n находится в [0, b.bucket_count()) | Итератор, который является значением "после конца" для бакета | Постоянное | |
b.load_factor() |
float | Среднее количество элементов на бакет | Постоянное | ||
b.max_load_factor() |
float | Положительное число, к которому контейнер стремится, чтобы коэффициент заполнения был меньше или равен ему. Контейнер автоматически увеличивает количество бакетов по мере необходимости, чтобы поддерживать коэффициент заполнения ниже этого числа | Постоянное | ||
a.max_load_factor(z) |
void |
z положительно. Может изменить максимальный коэффициент заполнения контейнера, используя z в качестве подсказки | Постоянное | ||
a.rehash(n) |
void | Гарантирует:
| Средний случай линейно от a.size(), наихудший случай O(N2) |
||
a.reserve(n) |
a.rehash(std::ceil( |
Неупорядоченные ассоциативные контейнеры в стандартной библиотеке
|
(C++11) | множество уникальных ключей, хэшируемых по ключам (шаблон класса) |
|
(C++11) | множество ключей, хэшируемых по ключам (шаблон класса) |
|
(C++11) | множество пар ключ-значение, хэшируемых по ключам, ключи уникальны (шаблон класса) |
|
(C++11) | множество пар ключ-значение, хэшируемых по ключам (шаблон класса) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer
