11. 关联容器
支持关键字查找和访问，两个主要的关联容器类型是map和set。
- map：元素是关键字-值对（key-value），关键字起到索引的作用，值表示与索引相关联的数据；
- set：只包含一个关键字，支持搞笑的关键字查询操作（检查一个给定的关键字是否在set中）；
标准库提供8个关联容器：
对于这八个不同的关联容器，每个容器：
- 或者是一个set或者是一个map；
- 或者要求不重复的关键字，或者允许重复的关键字（multi）；
- 或者按顺序保存元素，或者无序保存（unordered，使用哈希函数组织元素）；
11.1 使用关联容器
11.2 关联容器概述
11.2.1 定义关联容器
11.2.2 关键字类型的要求
11.2.3 pair类型
11.3 关联容器操作
11.3.1 关联容器迭代器
11.3.2 添加元素
11.3.3 删除元素
11.3.4 map的下标操作
11.3.5 访问元素
11.3.6 一个单词转换的map
11.4 无序容器
11.1 使用关联容器
map类型通常被称为关联数组，关联数组的下标不必是整数，可以通过一个关键字查找值。set是关键字的简单集合。
map：单词计数程序
word_count的关键字是string类型，值为size_t类型。
set：使用set保存想忽略的单词，只统计其他单词的出现次数
当单词不在set中时，find返回指向尾后元素的迭代器，因此用exclude.find(word)==exclude.end()进行判断。
11.2 关联容器概述
关联容器和迭代器都是双向的。
11.2.1 定义关联容器
map的定义需要指明关键字类型以及值类型，set的定义只需要指明关键字类型。
authors的关键字为第一个元素，值为第二个元素。
11.2.2 关键字类型的要求
有序容器的关键字类型：关键字严格弱序
11.2.3 pair类型
pair是一个标准库类型，定义在头文件utility中。一个pair保存两个数据成员：
pair的数据成员是public的，两个成员分别命名为first和second，使用普通的成员访问符号访问它们：
11.3 关联容器操作
11.3.1 关联容器迭代器
解引用一个关联容器的迭代器时，得到一个类型为容器的value_type的值的引用。
另外set的迭代器是const的，可以使用set迭代器读取元素的值，但不能修改。通常不对关联容器使用泛型算法，因为关键字是const的，不能将关联容器传递给修改或重排容器元素的算法。
11.3.2 添加元素
对于不包含重复关键字的类型，插入一个已存在的元素对容器没有影响：
insert或emplace的返回值是一个pair，first成员是一个迭代器指向具有给定关键字的元素，second成员是一个bool值指出元素是插入成功(1)还是已经存在于容器中(0)。
11.3.3 删除元素
对于保存不重复关键字的容器，erase返回一个bool值说明像要删除的元素是否在容器中。
11.3.4 map的下标操作
map进行下标操作时会获得一个mapped_type对象，解引用一个map迭代器会得到一个value_type对象。
11.3.5 访问元素
lower_bound和upper_bound不适用于无序容器，下标和at操作只适用于非const的map和unordered_map。
11.3.6 一个单词转换的map
为了进行单词转换将使用三个函数：
- word_transform管理整个过程，接受两个ifstream参数，第一个参数绑定到单词转换文件（映射规则），第二个参数绑定到要转换的文本文件；
- buildMap读取转换规则文件并创建一个map；
- transform接受一个string，如果存在转换返回转换后的内容；
word_transform：
buildMap：
transform：
11.4 无序容器
无序容器在存储上组织为一组桶，每个桶保存0/1/多个元素，无序容器使用一个哈希函数将元素映射到桶。容器首先计算元素的哈希值，然后将具有一个特定哈希值的所有元素都保存在一个桶中（即哈希值相同的元素在同一个桶里）。无序容器的性能依赖于哈希函数的质量与桶的数量和大小。
