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 均存在且各指名类型，则成员函数 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>。

无序关联容器中的元素被组织到桶（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)	同上

本节未完成 原因：考虑成员函数的要求

标准库中的无序关联容器

unordered_set (C++11 起)	唯一键的集合，按照键生成散列 (类模板)
unordered_multiset (C++11 起)	键的集合，按照键生成散列 (类模板)
unordered_map (C++11 起)	键值对的集合，按照键生成散列，键是唯一的 (类模板)
unordered_multimap (C++11 起)	键值对的集合，按照键生成散列 (类模板)