首页 > 代码库 > 无序关联容器(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的最小整数