16.6 关联容器
除了vector之外，最有用的标准库容器恐怕就是map了。一个map就是一个（键，值）对的有序序列，你可以基于一个关键字在其中查找对应的值；例如my_phone_book["Nicholas"]应该是Nicholas的电话号码。在流行度的竞争中，map唯一的潜在竞争对手是unordered_map（见16.6.4节），它是一种针对字符串关键字优化过的map。类似map和unordered_map的数据结构有很多名字，例如关联数组（associative array）、哈希表（hash table）和红黑树（red-black tree）等。流行的和有用的概念似乎总是有很多名称。在标准库中，我们将这类数据结构统称为关联容器（associative container）。
标准库提供了8个关联容器：
关联容器
map （键，值）对的有序容器
set 关键字的有序容器
unordered_map （键，值）对的无序容器
unordered_set 关键字的无序容器
multimap 关键字可以出现多次的map
multiset 关键字可以出现多次的set
unordered_multimap 关键字可以出现多次的unordered_map
unordered_multiset 关键字可以出现多次的unordered_set
这些容器可以在<map>、<set>、< unordered_map >和< unordered_set >中找到。
16.6.1 map
思考一个概念上简单的例子：建立一个单词在文本中出现次数的列表。最明显的方式是维护一个我们看到单词的列表并维护每个单词遇到的次数。当我们读入一个新单词时，首先查看是否曾经见到过它；如果见过，将其计数器加一；否则，将它插入列表并赋值为1。我们可以使用list或vector来完成它，但是我们不得不为读取的每个单词进行一次查找。这可能很慢。map存储关键字的方式令判断关键字是否存在变得很容易，这使得搜索部分在我们的任务中变得微不足道：
这个程序中真正有趣的部分是++words[s]。正如我们在main()第一行中看到的，words是一个（string, int）对的map；也就是说，words将string映射到int。换句话说，给定一个string，words可以令我们访问对应的int。当我们用string（保存输入的单词）来对words进行下标操作时，words[s]得到对应s的int的引用。让我们来看一个具体的例子：
如果我们没见到过字符串"sultan"，"sultan"将会被插入words，伴随着int的默认值0。现在，words会有一项（"sultan", 0）。因此结果就是，如果我们之前未见到过"sultan"，则++words["sultan"]会将值1与字符串"sultan"相关联。详细来说：map会发现"sultan"不在其中，它插入一个（"sultan", 0）对，然后++会将该值加一，得到1。
我们现在回过头来再看这个程序：++words[s]得到我们输入的每个单词，并将其对应的值加一。当新单词第一次出现时，它会得到值1。现在，这个循环的含义就清晰了：
这个循环读取输入的每个单词（用空格分隔），并计算每个单词的出现次数。现在我们要做的就是生成输出了。我们可以遍历一个映射，就像遍历其他STL容器那样。一个map<string,int>的元素是pair<string,int>。每个pair的第一个元素名为f?irst，第二个元素名为second，因此输出循环为
作为测试，我们可以将第1版《The C++ Programming Language》的开篇句子输入程序：
C++ is a general purpose programming language designed to make programming more enjoyable for the serious programmer. Except for minor details, C++ is a superset of the C programming language. In addition to the facilities provided by C, C++ provides f?lexible and eff?icient facilities for def?ining new types.
我们得到输出
如果我们不想区分大小写字母或者希望去掉标点符号，我们可以这样做：参见习题13。
16.6.2 map概览
那么，映射是什么呢？映射的实现有很多种方式，但是STL实现映射通常采用平衡二叉搜索树，更具体一些——红黑树。我们将不会探究其细节，但是现在你知道了技术术语，这样，如果你想了解更多知识，就可以通过书籍或互联网来查找。
一棵树由多个节点构成（与链表由链接构成相似，参见15.4节）。一个Node保存一个关键字和对应的值，并且指向两个子节点。
这就是map<Fruit,int>在内存中的样子，假设我们插入了（Kiwi, 100）、（Qunice, 0）、（Plum, 8）、（Apple, 7）、（Grape, 2345）和（Orange, 99）：
若保存关键字值的Node成员的名字为f?irst，二叉搜索树的基本规则是：
即，对每个节点，
它的左子节点的关键字小于本节点的关键字；
而且，本节点的关键字小于它的右字节点的关键字。
你可以对树中的每个节点验证这个规则是成立的。这允许我们“从根向下”搜索树。非常奇怪的是，在计算机科学文献中，树是从根向下生长的。在本例中，根节点是（Orange，99）。我们沿着树向下比较，直到发现要查找的值或它应该处于的位置。若一棵树的与根等距离的所有子树的节点数大致相等（如本例），那么这棵树被称为平衡的（balanced）。平衡树最小化了一次搜索平均要访问的节点数。
一个Node可能还保存更多的数据，映射可以用之来保持树中节点的平衡。当一棵树中的每个节点的左、右子树点数大致相同时，这棵树就是平衡的。如果一棵有N个节点的树是平衡的，我们找到每个节点最多需要查找log2(N)个节点。这比我们在链表中从开始位置查找一个关键字，平均要查找N/2个节点的情况（这种线性查找的最坏情况是N）要好得多。（参见16.6.4节。）例如，我们看一棵非平衡的树：
这棵树仍然遵守每个节点的关键字大于它的左子节点、小于它的右子节点的规则：
但是，这个版本的树是非平衡的，因此我们现在要经过三“跳”到达Apple和Kiwi，而在平衡树中只需要两“跳”。对于有很多节点的树来说，这个差别可能非常巨大，因此用于实现map的树是平衡的。
使用map时并不需要理解树。这里只是做个合理的假设——专业人员至少了解所用工具的基础知识。我们必须了解的是由标准库提供的map的接口。下面是一个稍微简化过的版本：
你可以在<map>中找到真实的版本。你可以将迭代器想象成一个Node*，但是你不能依赖使用这种特殊类型的自己的实现版本来实现迭代器。
显然，map的接口与vector和list（见15.5节和附录C.4）是很相似的。最大的不同是在遍历时，map的元素类型为pair<Key,Value>。这个类型是另一个有用的STL类型：
我们从标准库复制了pair的完整定义及其有用的辅助函数make_pair()。
注意，当你对一个map进行遍历时，将按关键字定义的序访问元素。例如，如果我们对例子中的水果进行遍历，我们将得到：
我们插入水果的顺序无关紧要。
insert()操作有一个奇怪的返回值，我们经常在简单的程序中忽略它。返回值包含一对迭代器，指向（key, value）元素，还包含一个bool值，如果这次insert()调用成功地插入了（key, value）对，则其值为true。如果关键字已在映射中，则插入失败且返回的bool值为false。
注意，通过提供第三个参数（映射声明中的Cmp），你可以定义映射使用的序的含义。例如：
No_case定义不区分大小写的比较，参见16.8节。默认的序是由less<Key>定义的，表示“小于”。
16.6.3 另一个map实例
为了更好地体会map的用途，我们回到16.5.3节中的道琼斯工业指数的例子。只有当所有的权重与它们对应的名字出现在vector中相同位置时，这段代码才是正确的。这个前提是隐式的，很容易成为隐蔽错误的来源。有很多方法可以解决这个问题，但一个有吸引力的方法是将权重与其公司的股票代码保存在一起，例如（“AA”，2.4808）。“股票代码”是公司名称的缩写，用在需要简洁表示的地方。与此相似，我们可以将公司股票代码与其股票价格保存在一起，例如（“AA”，34.69）。最后，对于那些不经常与美国股票市场打交道的人，我们可以将公司股票代码与公司名称保存在一起，例如（“AA”，“Alcoa Inc.”）。也就是说，我们维护三个相关值的映射。
首先，我们实现（代码，价格）映射：
接下来是（代码，权重）映射：
最后是（代码，名称）映射：
通过这些映射，我们可以方便地提取各种信息。例如：
遍历映射是很容易的。我们只需记住关键字称为f?irst，而值称为second：
我们甚至可以直接使用映射来完成某些计算。特别是，我们可以计算出指数，就像我们在16.5.3节中所做的那样。我们可以从各自的映射中提取出股票价格和权重，并将它们相乘。我们可以很容易地编写一个函数，可对任意两个map<string,double>完成这个操作：
现在，我们将这个函数加入inner_product()的泛化版本，并得到指数值：
为什么有人将这类数据保存在map中，而不是vector中呢？我们使用map的目的是令不同的值之间的联系显式表现出来。这是一个常见的原因。另一个原因是map会按关键字定义的序来保存它的元素。当我们遍历上面的dow时，我们按字母顺序输出股票代码；假如我们使用vector，则需要自己进行排序。使用map的最常见的原因不过是我们希望基于关键字查找值。对于大的序列，使用f?ind()来查找某些东西的速度远比在一个排序的结构（例如map）中查找慢得多。
试一试
编译运行这个小例子。然后，添加几个你自己选择的公司，以及你自己选择的权重。
16.6.4 unordered_map
为了在一个vector中找到一个元素，f?ind()需要检查所有的元素，从首元素到正确值的元素或一直到末尾。其平均代价与vector(N)的长度成比例，我们称这个代价为O(N)。
为了在一个map中找到一个元素，下标操作需要在树中从根节点开始到正确值的元素或一直到叶节点检查路径上所有元素。其平均代价与树的深度成比例。一棵有N个节点的平衡二叉树的最大深度为log2(N)，代价为O(log2(N))。O(log2(N))——即与log2(N)成比例的代价——与O(N)相比实际上是非常好的：
N 15 128 1023 16?383
log2(N) ??4 7 10 ???14
实际的代价将会依赖于我们多快查找到所要的值以及比较和迭代操作的代价有多大。通常，追踪指针（在map中查找所做的）的代价比递增一个指针（f?ind()在vector中所做的）大得多。
对于有些类型，特别是整数和字符串，我们甚至可以做得比map的树搜索更好。我们这里不深入细节，但其思路是给定一个关键字，我们可以计算其在vector中的索引。这个索引被称为一个哈希值（hash value），而使用这种技术的容器通常被称为哈希表（hash table）。应用中可能出现的关键字数量远大于哈希表中的位置数。例如，我们经常用一个哈希函数将数十亿个可能的字符串映射成1000个元素的vector中的索引。这可能有些棘手，但我们可以很好地处理它，这对实现大的映射特别有用。哈希表的主要优点是查找的平均代价接近常数且与表中的元素数量无关，即O(1)。很明显，这对于大的映射来说是一个显著的优点，例如一个有500?000个web地址的映射。如果想获得有关哈希查找的更多知识，你可以查阅有关unordered_map的文档（可在互联网中找到），或者有关数据结构的基础教材（查找“哈希表”和“哈希”）。
在一个（未排序）向量、一棵平衡二叉树和一个哈希表中的查找过程图示如下：
在未排序vector中查找：
在map（平衡二叉树）中查找：
在unordered_map（哈希表）中查找：
STL unordered_map是使用一个哈希表来实现的，正如STL map是使用一个平衡二叉树，STL vector是使用一个矩阵来实现的一样。STL的部分功用就是将这些数据存储和访问方法与算法一起纳入一个通用框架中。相应的经验法则是：
除非你有好的理由，否则使用vector。
如果你需要基于值来进行查找（而且你的关键字类型有合理而高效的小于操作），这时使用map。
如果你需要在一个大的映射中进行大量查找，并且你不需要有序的遍历（而且可以为你的关键字类型找到一个好的哈希函数），这时使用unordered_map。
在这里，我们不会描述unordered_map的细节。我们可以将unordered_map与string或int类型的关键字共同使用，这方面与map完全一样，差别是当你遍历元素时，并不是有序访问元素。例如，我们可以重写16.6.3节中的道琼斯工业指数例子如下：
现在，在dow中查找的速度可能更快。但是，这个变化并不会很显著，这是因为在指数中只有30个公司。假如我们保存了纽约证券交易所中所有公司的股票价格，性能差异就可能显现出来了。但是，我们需要注意一个逻辑上的不同：遍历得到的输出将不会按字母顺序排列。
未排序的映射在C++标准中是新内容，而且还远不是“一等成员”，因为它们是在技术报告而非标准中定义的。但现有编译器已广泛支持它们，即便不支持，通常也能看到它们的前身——名为hash_map之类的东西。
试一试
编写一个使用#include<unordered_map>的小程序。如果它不能正常工作，说明你的C++实现未包含unordered_map。如果你的C++实现未提供unordered_map，你需要下载一个可用的实现（例如参见www.boost.org）。
16.6.5 set
我们可以将set（集合）看作一个对其值不感兴趣的map，或干脆看作一个没有值的map。我们可以图示一个set如下：
我们可以将map的例子（见16.6.2节）中的水果用set表示，如下图所示：
集合有什么用？如果我们看见一个值，碰巧有很多问题需要我们记住。跟踪哪种水果有货（与价格无关）就是一个例子，构造一个字典是另一个例子。一个稍微不同的使用风格是用集合保存“记录”；即，元素是可能包含“大量”信息的对象——我们只需使用一个成员作为关键字。例如：
这里，我们再次看到使用函数对象是如何显著扩大STL组件的应用范围的。
由于set没有值类型，因此它也不支持下标操作（operator[]()）。我们必须使用“链表操作”，例如insert()和erase()。不幸的是，map和set都不支持push_back()——原因很明显：set不是由程序员决定在哪里插入新值，取而代之使用insert()。例如：
set优于map的一点是你可以直接使用从迭代器得到的值。由于不像map（见16.6.3节）那样有（键，值）对，解引用操作直接得到一个元素类型的值：
当然，假设你已经为Fruit定义了<<。或者我们可以写出如下等价代码：