STL-关联容器

c++ primer 第11章

关联容器和顺序容器有根本的不同：关联容器中的元素是按关键字来保存和访问的。

关联容器类型：分为有序和无序

有序：

map　　关联数组；保存键值对

set　　关键字即值，即只保存关键字的容器

multimap　　关键字可重复出现的map

multiset　　关键字可重复出现的set

无序：

unordered_map　　用哈希函数组织的map

unordered_set　　用哈希函数组织的set

unordered_multimap　　哈希组织的map，且关键字可以重复出现

unordered_multiset　　哈希组织的set，且关键字可以重复出现

使用关联容器：map形式两个模板参数map<key_type, value_type>，set形式一个模板参数set<key_type>。

关联容器的迭代器都是双向的。

关联容器的默认构造函数创建一个指定类型的空容器，可以列表初始化，对于map的列表初始化：{ {key,val}, {key,val}....}。

关联容器的参数：map有2个，set有1个，此时它们的比较函数是默认的，默认比较函数是“<"运算符，可以加上我们自己的比较函数：

set<int, my_compare>st;

pair类型：

定义在utility头文件中。

有两个数据成员：first和second。在声明时指定这两个成员的类型pair<int, double>p；

pair操作：

pair<T1, T2>p;　　p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化。

pair<T1, T2>p( v1, v2);　　p是一个成员类型为T1和T2的pair；first和second成员分别用v1、v2进行初始化。

pair<T1, T2>p={v1,v2};　　等价于pair<T1, T2>p{v1, v2};

make_pair(v1, v2);　　返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来。

p.first　　返回p的名为first的公有数据成员。

p.second　　返回p的名为second的公有数据成员。

p1 relop p2　　关系运算符（<,>,<=,>=）按字典序定义：

p1==p2　p1!=p2　　当first和second成员分别相等时，两个pair相等。相等性判断利用元素的==运算符实现。

关联容器操作：

key_type　　此容器类型的关键字类型。

map_type　　每个关键字关联的类型；只适用于map。

value_type　　对于set，与key_type相同；对于map，为pair<const key_type, mapped_type>

set的迭代器是const的

有序map和set的添加/删除操作：insert（emplace)/erase，添加时可以用值、迭代器、列表、迭代器范围，删除时可用值、迭代器和迭代器范围。

map下标操作：[]和at。

访问元素：

lower_bound和upper_bound不适用于无序容器。

下标和at操作只适用于非const的map和unordered_map。

c.find(k)　　返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器。

c.count(k)　　返回关键字等于k的元素的数量。对于不允许重复关键字的容器，返回值永远是0或1。

c.lower_bound(k)　　返回一个迭代器，指向第一个关键字不小于k的元素。

c.upper_bound(k)　　返回一个迭代器，指向第一个关键字大于k的元素。

c.equal_range(k)　　返回一个迭代器pair，表示关键字等于k的元素范围。若k不存在，pair的两个成员均为c.end()。

无序容器：

4个无序容器使用哈希函数和关键字类型的==运算符。在关键字类型的元素没有明显的序关系的情况下，无序容器非常有用。

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

对于相同的参数，哈希函数产生相同结果。对于不同的参数也可能产生相同结果。当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。

无序容器提供了一组管理桶的函数。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

无序容器管理操作：

桶接口：

c.bucket_count()　　正在使用的桶的数目。

c.max_bucket_count()　　容器能容纳的最多的桶的数量。

c.bucket_size(n)　　第n个桶中有多少个元素。

c.bucket(k)　　关键字为k的元素在哪个桶中。

桶迭代：

local_iterator　　可以用来访问桶中元素的迭代器类型

const_local_iterator　　桶迭代器的const版本

c.begin(n), c.end(n)　　桶n的首元素迭代器和尾后迭代器

c.cbegin(n), c.cend(n)　　与前两个函数类似，但返回const_local_iterator

哈希策略：

c.load_factor()　　每个桶的平均元素数量，返回float值

c.max_load_factor()　　c试图维护的平均桶大小，返回float值。c会在需要时添加新的桶，以使得load_factor<=max_load_factor重组存储，使得bucket_count>=n

c.rehash(n)　　重组存储，使得bucket_count>=n且bucket_count>size/max_load_factor

c.reserve(n)　　重组存储，使得c可以保存n个元素且不必rehash。