首页 > 代码库 > 无序关联容器（C++11）
无序关联容器（C++11）
2012-11-27 15:22 张海龙/袁国忠 译 人民邮电出版社 字号：T|T
《C++Primer Plus（第6版）（中文版）》附录G标准模板库方法和函数：本附录总结了STL容器方法和通用的STL算法函数。本节为大家介绍无序关联容器（C++11）。
AD：
G.4 无序关联容器（C++11）
前面说过，无序关联容器（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的最小整数 |