C++ 具名要求：无序关联容器 (UnorderedAssociativeContainer)
无序关联容器是提供基于键的快速对象查找的容器 (Container) 。最坏情况的复杂度为线性，但平均而言大多数操作则快得多。
无序关联容器基于以下各项参数化：Key；Hash，表现为 Key 上散列函数的散列 (Hash) 函数对象；Pred，评估 Key 间的等价性的二元谓词 (BinaryPredicate) 。std::unordered_map 与 std::unordered_multimap 也拥有与 Key 关联的被映射类型 T。
若两个 Key 按照 Pred 比较为相等，则 Hash 必须对两个键返回相同值。
|
若 Hash::is_transparent 与 Pred::is_transparent 均存在且各指名类型，则成员函数 |
(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>。
无序关联容器中的元素被组织到桶（bucket）中，拥有相同散列值的键将归于相同的桶中。桶数在容器大小增加时增加，以保持每个桶中的平均元素数在某个确定值之下。
重散列会使迭代器失效，并可能导致元素被重排到不同的桶中，但它不使元素的引用失效。
无序关联容器满足知分配器容器 (AllocatorAwareContainer) 的要求。对于 std::unordered_map 与 std::unordered_multimap，知分配器容器 (AllocatorAwareContainer) 中 value_type 的要求应用到 key_type 和 mapped_type（而非到 value_type）。
要求
凡例 | |
X
|
容器类型 |
a
|
X 类型的对象
|
b
|
X 类型的 const 对象
|
a_uniq
|
（当 X 支持唯一键时）X 中的对象
|
a_eq
|
（当 X 支持多重键时）X 中的对象
|
i, j
|
指代有效范围的遗留输入迭代器 (LegacyInputIterator) |
p, q2
|
指向 a 的有效 const_iterator
|
q, q1
|
指向 a 的指代有效范围的可解引用 const_iterator
|
il
|
std::initializer_list<X::value_type> 类型的对象 |
t
|
X::value_type 类型的对象
|
k
|
X::key_type 类型的对象
|
hf
|
X::hasher 类型的 const 对象
|
eq
|
X::key_equal 类型的 const 对象
|
n
|
X::size_type 类型的值
|
z
|
float 类型的值 |
| 表达式 | 返回类型 | 前条件/要求 | 后条件/效果 | 复杂度 |
|---|---|---|---|---|
| X::key_type | Key |
编译时 | ||
| X::mapped_type | T |
仅 std::unordered_map 与 std::unordered_multimap | 编译时 | |
| X::value_type | Key |
仅 std::unordered_set 与 std::unordered_multiset。于 X 可擦除 (Erasable) |
编译时 | |
| X::value_type | std::pair<const Key, T> | 仅 std::unordered_map 与 std::unordered_multimap。于 X 可擦除 (Erasable) |
编译时 | |
| X::hasher | Hash |
散列 (Hash) | 编译时 | |
| X::key_equal | Pred
|
接收两个 Key 类型的实参并表达等价关系的二元谓词 (BinaryPredicate) 。 |
编译时 | |
| X::local_iterator | 类别和类型与 X::iterator 相同的遗留迭代器 (LegacyIterator) |
可用于在单个桶上迭代 | 编译时 | |
| X::const_local_iterator | 类别和类型与 X::const_iterator 相同的遗留迭代器 (LegacyIterator) |
可用于在单个桶上迭代 | 编译时 | |
| X(n,hf,eq) | X |
hasher 与 key_equal 可复制构造 (CopyConstructible) |
用给定的散列函数和相等谓词，构造至少有 n 个桶的空容器 |
与 n 成线性
|
| X(n,hf) | X |
hasher 可复制构造 (CopyConstructible) ， key_equal 可默认构造 (DefaultConstructible) |
用给定的散列函数并以 key_equal() 为相等谓词，构造至少有 n 个桶的空容器 |
与 n 成线性
|
| X(n) | X |
hasher 与 key_equal 可默认构造 (DefaultConstructible) |
以 hasher() 为散列函数并以 key_equal() 为相等谓词，构造至少有 n 个桶的空容器 |
与 n 成线性
|
| X() | X |
hasher 与 key_equal 可默认构造 (DefaultConstructible) |
以 hasher() 为散列函数并以 key_equal() 为相等谓词，构造有未指定桶数的空容器 |
常数 |
| X(i,j,n,hf,eq) | X |
hasher 与 key_equal 可复制构造 (CopyConstructible) ，value_type 从 *i 可就位构造 (EmplaceConstructible) 到 X |
用给定的散列函数和相等谓词，构造至少有 n 个桶的空容器，并插入来自 [i,j) 的元素到它。 |
平均为线性，最坏为（对 i 与 j 间的的距离的）平方
|
| X(i,j,n,hf) | X |
key_equal 可默认构造 (DefaultConstructible) |
如上，有 eq=key_equal() | 同上 |
| X(i,j,n) | X |
hasher 可默认构造 (DefaultConstructible) |
如上，有 hf=hasher() | 同上 |
| X(i,j) | X |
如上，拥有未指定的桶数 | 同上 | |
| X(il) | X |
X(il.begin(),il.end() | 同上 | |
| X(il,n) | X |
X(il.begin(),il.end(),n | 同上 | |
| X(il,n,hf) | X |
X(il.begin(),il.end(),n,hf | 同上 | |
| X(il,n,hf,eq) | X |
X(il.begin(),il.end(),n,hf,eq | 同上 | |
| X(b) | X |
复制构造函数，亦复制散列函数、谓词和最大加载因子 | 平均为线性，最坏为（对 b.size() 的）平方
| |
| a = b | X& |
复制赋值，亦复制散列函数、谓词和最大加载因子 | 平均为线性，最坏为（对 b.size() 的）平方
| |
| a = il | X& |
value_type 可复制赋值 (CopyAssignable) 且可复制插入 (CopyInsertable) 到 X |
a = X(il) | 同上 |
| 本节未完成 原因：考虑成员函数的要求 |
标准库中的无序关联容器
| (C++11 起) |
唯一键的集合，按照键生成散列 (类模板) |
| (C++11 起) |
键的集合，按照键生成散列 (类模板) |
| (C++11 起) |
键值对的集合，按照键生成散列，键是唯一的 (类模板) |
| (C++11 起) |
键值对的集合，按照键生成散列 (类模板) |
