Question

前面说过，无序关联容器（unordered_set、unordered_multiset、unordered_map 和 unordered_multimap）使用键和哈希表，以便能够快速存取数据。下面简要地介绍这些概念。哈希函数（hash function）将键转换为索引值。例如，如果键为 string 对象，哈希函数可能将其中每个字符的数字编码相加，再计算结果除以 13 的余数，从而得到一个 0～12 的索引。而无序容器将使用 13 个桶（bucket）来存储 string，所有索引为 4 的 string 都将存储在第 4 个桶中。如果您要在容器中搜索键，将对键执行哈希函数，进而只在索引对应的桶中搜索。理想情况下，应有足够多的桶，每个桶只包含为数不多的 string。

C++11 库提供了模板 hash<key>，无序关联容器默认使用该模板。为各种整型、浮点型、指针以及一些模板类（如 string）定义了该模板的具体化。

表 G.11 列出了用于这些容器的类型。

无序关联容器的接口类似于关联容器。具体地说，表 G.10 也适用于无序关联容器，但存在如下例外：不需要方法 lower_bound( ) 和 upper_bound( )，构造函数 X(i, j, c) 亦如此。常规关联容器是经过排序的，这让它们能够使用表示“小于”概念的比较谓词。这种比较不适用于无序关联容器，因此它们使用基于概念“等于”的比较谓词。

表 G.11 为无序关联容器定义的类型

类 型	值
X::key_type	Key，键类型
X::key_equal	Pred，一个二元谓词，检查两个类型为 Key 的参数是否相等
X::hasher	Hash，一个这样的二元函数对象，即如果 hf 的类型为 Hash，k 的类型为 Key，则 hf(k) 的类型为 std::size_t
X::local_iterator	一个类型与 X::iterator 相同的迭代器，但只能用于一个桶
X::const_local_iterator	一个类型与 X::const_iterator 相同的迭代器，但只能用于一个桶
X::mapped_type	T，关联数据类型（仅限于 map 和 multimap）

除表 G.10 所示的方法外，无序关联容器还包含其他一些必不可少的方法，如表 G.12 所示。在该表中，X 为无序关联容器类，a 是类型为 X 的对象，b 可能是类型为 X 的常量对象，a_uniq 是类型为 unordered_set 或 unordered_map 的对象，a_eq 是类型为 unordered_multiset 或 unordered_multimap 的对象，hf 是类型为 hasher 的值，eq 是类型为 key_equal 的值，n 是类型为 size_type 的值，z 是类型为 float 的值。与以前一样，i 和 j 也是指向 value_type 元素的输入迭代器，[i, j]是一个有效的区间，p 和 q2 是指向 a 的迭代器，q 和 q1 是指向 a 的可解除引用迭代器，[q1, q2]是有效区间，t 是 X::value_type 值（可能是一对），k 是 X::key_type 值，而 il 是 initializer_list<value_type>对象。

表 G.12 为无序关联容器定义的操作

操 作	描 述
X(n, hf, eq)	创建一个至少包含 n 个桶的空容器，并将 hf 用作哈希函数，将 eq 用作键值相等谓词。如果省略了 eq，则将 key_equal( ) 用作键值相等谓词；如果也省略了 hf，则将 hasher( ) 用作哈希函数
X a(n, hf, eq)	创建一个名为 a 的空容器，它至少包含 n 个桶，并将 hf 用作哈希函数，将 eq 用作键值相等谓词。如果省略 eq，则将 key_equal( ) 用作键值相等谓词；如果也省略了 hf，则将 hasher( ) 用作哈希函数
X(i, j, n, hf, eq)	创建一个至少包含 n 个桶的空容器，将 hf 用作哈希函数，将 eq 用作键值相等谓词，并插入区间[i, j]中的元素。如果省略了 eq，将 key_equal( ) 用作键值相等谓词；如果省略了 hf，将 hasher( ) 用作哈希函数；如果省略了 n，则包含桶数不确定
X a(i, j, n, hf, eq)	创建一个名为 a 的的空容器，它至少包含 n 个桶，将 hf 用作哈希函数，将 eq 用作键值相等谓词，并插入区间[i, j]中的元素。如果省略了 eq，将 key_equal( ) 用作键值相等谓词；如果省略了 hf，将 hasher( ) 用作哈希函数；如果省略了 n，则包含桶数不确定
b.hash_function( )	返回 b 使用的哈希函数
b.key_eq( )	返回创建 b 时使用的键值相等谓词
b.bucket_count( )	返回 b 包含的桶数
b.max_bucket_count ( )	返回一个上限数，它指定了 b 最多可包含多少个桶
b.bucket(k)	返回键值为 k 的元素所属桶的索引
b.bucket_size(n)	返回索引为 n 的桶可包含的元素数
b.begin(n)	返回一个迭代器，它指向索引为 n 的桶中的第一个元素
b.end(n)	返回一个迭代器，它指向索引为 n 的桶中的最后一个元素
b.cbegin(n)	返回一个常量迭代器，它指向索引为 n 的桶中的第一个元素
b.cend(n)	返回一个常量迭代器，它指向索引为 n 的桶中的最后一个元素
b.load_factor()	返回每个桶包含的平均元素数
b.max_load_factor()	返回负载系数的最大可能取值；超过这个值后，容器将增加桶
b.max_load_factor(z)	可能修改最大负载系统，建议将它设置为 z
a.rehash(n)	将桶数调整为不小于 n，并确保 a.bucket_count( ) > a.size( ) / a.max_load_factor( )
a.reserve(n)	等价于 a.rehash(ceil(n/a.max_load_factor( )))，其中 ceil(x) 返回不小于 x 的最小整数