G.4 无序关联容器（C++(www.cppentry.com)11）
前面说过，无序关联容器（unordered_set、unordered_multiset、unordered_map和unordered_multimap）使用键和哈希表，以便能够快速存取数据。下面简要地介绍这些概念。哈希函数（hash function）将键转换为索引值。例如，如果键为string对象，哈希函数可能将其中每个字符的数字编码相加，再计算结果除以13的余数，从而得到一个0～12的索引。而无序容器将使用13个桶（bucket）来存储string，所有索引为4的string都将存储在第4个桶中。如果您要在容器中搜索键，将对键执行哈希函数，进而只在索引对应的桶中搜索。理想情况下，应有足够多的桶，每个桶只包含为数不多的string。
C++(www.cppentry.com)11库提供了模板hash<key>，无序关联容器默认使用该模板。为各种整型、浮点型、指针以及一些模板类（如string）定义了该模板的具体化。
表G.11列出了用于这些容器的类型。
无序关联容器的接口类似于关联容器。具体地说，表G.10也适用于无序关联容器，但存在如下例外：不需要方法lower_bound( )和upper_bound( )，构造函数X(i, j, c) 亦如此。常规关联容器是经过排序的，这让它们能够使用表示"小于"概念的比较谓词。这种比较不适用于无序关联容器，因此它们使用基于概念"等于"的比较谓词。
表G.11为无序关联容器定义的类型
|
类 型< xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /> |
值 |
|
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的最小整数 |