C++ 命名要求： UnorderedAssociativeContainer (自 C++11 起)
无序关联容器是 Container，提供基于键的快速对象查找。在最坏情况下，复杂度是线性的，但在大多数操作中，平均速度快得多。
无序关联容器通过 Key 参数化； Hash，一个 Hash 函数对象，作为 Key 的哈希函数；以及 Pred，一个 BinaryPredicate，用于评估 Keys 之间的等价性。std::unordered_map 和 std::unordered_multimap 还有一个与 Key 关联的映射类型 T。
如果根据 Pred 两个 Keys 相等，则 Hash 必须为两个键返回相同的值。
如果 Hash::is_transparent 和 Pred::is_transparent 都存在且各命名一个类型，则成员函数 find、contains、count 和 equal_range 接受除 Key 之外的类型参数，并期望 Hash 可以使用这些类型的值进行调用，并且 Pred 是一个透明的比较函数，例如 std::equal_to<>。 (自 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，AllocatorAwareContainer 中 value_type 的要求适用于 key_type 和 mapped_type（而不是 value_type）。
要求
图例
X 容器类型
a 类型为 X 的对象
b 类型为 X 的 const 对象
a_uniq X 中支持唯一键的对象
a_eq X 中支持多个等价键的对象
i, j LegacyInputIterators，表示一个有效范围
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 浮点类型的值
| 表达式 | 返回类型 | 前/要求 | 后/效果 | 复杂度 |
|---|---|---|---|---|
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 | 哈希 | 哈希 | 编译时 | |
X::key_equal | Pred | BinaryPredicate 接受两个 Key 类型的参数并表示等价关系。 | 编译时 | |
X::local_iterator | 一个 LegacyIterator，其类别和类型与 X::iterator 相同 | 可用于遍历单个桶 | 编译时 | |
X::const_local_iterator | 一个 LegacyIterator，其类别和类型与 X::const_iterator 相同 | 可用于遍历单个桶 | 编译时 | |
X(n,hf,eq) | X | hasher 和 key_equal 可拷贝构造 | 使用给定的哈希函数和相等谓词构造一个至少包含 n 个桶的空容器 | 关于 n 呈线性 |
X(n,hf) | X | hasher 可拷贝构造，key_equal 可默认构造 | 使用给定的哈希函数和 key_equal() 作为相等谓词，构造一个至少包含 n 个桶的空容器 | 关于 n 呈线性 |
X(n) | X | hasher 和 key_equal 可默认构造 | 使用 hasher() 作为哈希函数和 key_equal() 作为相等谓词，构造一个至少包含 n 个桶的空容器 | 关于 n 呈线性 |
X() | X | hasher 和 key_equal 可默认构造 | 使用 hasher() 作为哈希函数和 key_equal() 作为相等谓词，构造一个桶数量未指定的空容器 | 常量 |
X(i,j,n,hf,eq) | X | hasher 和 key_equal 可拷贝构造，value_type 可从 *i 就地构造到 X 中 | 使用给定的哈希函数和相等谓词构造一个至少包含 n 个桶的空容器，并将 [i,j) 中的元素插入其中。 | 平均线性，最坏二次（相对于 i 和 j 之间的距离） |
X(i,j,n,hf) | X | key_equal 可默认构造 | 同上，其中 eq=key_equal() | 见上文 |
X(i,j,n) | X | hasher 可默认构造 | 同上，其中 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 可拷贝赋值 且 可拷贝插入到 X 中 | a = X(il) | 见上文 |
此部分不完整
原因：成员函数相关的要求未完成
标准库中的无序关联容器
| pub | std::unordered_set(C++11) | 唯一键的集合，按键哈希 |
| pub | std::unordered_multiset(C++11) | 键的集合，按键哈希 |
| pub | std::unordered_map(C++11) | 键值对的集合，按键哈希，键是唯一的 |
| pub | std::unordered_multimap(C++11) | 键值对的集合，按键哈希 |