[C++]C++Primer Chapter 11
关联容器
关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。
标准库提供8个关联容器，如表11.1所示。这8个容器间的不同体现在三个维度上：每个容器（1）或者是一个set，或者是一个map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以单词unordered开头。
11.1 使用关联容器
map是关键字-值对的集合。
map类型通常被称为关联数组（associative array）。关联数组与“正常”数组类似，不同之处在于其下标不必是整数。
set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。
使用map
为了定义一个map，我们必须指定关键字和值的类型。
当从map中提取一个元素时，会得到一个pair类型的对象，我们将在11.2.3节（第379页）介绍它。简单来说，pair是一个模板类型，保存两个名为first和second的（公有）数据成员。map所使用的pair用first成员保存关键字，用second成员保存对应的值。
使用set
find调用返回一个迭代器。如果给定关键字在set中，迭代器指向该关键字。否则，find返回尾后迭代器。
11.2 关联容器概述
关联容器不支持顺序容器的位置相关的操作，例如push_front或push_back。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
关联容器的迭代器都是双向的。
11.2.1 定义关联容器
初始化multimap或multiset
11.2.2 关键字类型的要求
对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。
有序容器的关键字类型
可以提供自己定义的操作来代替关键字上的<运算符。所提供的操作必须在关键字类型上定义一个严格弱序（strict weak ordering）。可以将严格弱序看作“小于等于”，虽然实际定义的操作可能是一个复杂的函数。无论我们怎样定义比较函数，它必须具备如下基本性质：
- 两个关键字不能同时“小于等于”对方；如果k1“小于等于”k2，那么k2绝不能“小于等于”k1。
- 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
- 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。
如果两个关键字是等价的（即，任何一个都不“小于等于”另一个），那么容器将它们视作相等来处理。当用作map的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。
在实际编程中，重要的是，如果一个类型定义了“行为正常”的<运算符，则它可以用作关键字类型。
使用关键字类型的比较函数
用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。
在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。
为了使用自己定义的操作，在定义multiset时我们必须提供两个类型：关键字类型Sales_data，以及比较操作类型——应该是一种函数指针类型（参见6.7节，第221页），可以指向compareIsbn。当定义此容器类型的对象时，需要提供想要使用的操作的指针。
11.2.3 pair类型
定义在头文件utility中。
一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。当创建一个pair时，我们必须提供两个类型名，pair的数据成员将具有对应的类型。两个类型不要求一样
pair的默认构造函数对数据成员进行值初始化（参见3.3.1节，第88页）。
与其他标准库类型不同，pair的数据成员是public的（参见7.2节，第240页）。两个成员分别命名为first和second。
11.3 关联容器操作
除了表9.2（第295页）中列出的类型，关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。
11.3.1 关联容器迭代器
当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。对map而言，value_type是一个pair类型，其first成员保存const的关键字，second成员保存值
set的迭代器是const的
虽然set类型同时定义了iterator和const_iterator类型，但两种类型都只允许只读访问set中的元素。与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改
遍历关联容器
当使用一个迭代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素。
关联容器和算法
我们通常不对关联容器使用泛型算法（参见第10章）。关键字是const这一特性意味着不能将关联容器传递给修改或重排容器元素的算法，因为这类算法需要向元素写入值，而set类型中的元素是const的，map中的元素是pair，其第一个成员是const的。
关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。
关联容器定义了一个名为find的成员，它通过一个给定的关键字直接获取元素。我们可以用泛型find算法来查找一个元素，但此算法会进行顺序搜索。使用关联容器定义的专用的find成员会比调用泛型find快得多。
11.3.2 添加元素
关联容器的insert成员（见表11.4，第384页）向容器中添加一个元素或一个元素范围。由于map和set（以及对应的无序类型）包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响
insert有两个版本，分别接受一对迭代器，或是一个初始化器列表，这两个版本的行为类似对应的构造函数（参见11.2.1节，第376页）——对于一个给定的关键字，只有第一个带此关键字的元素才被插入到容器中。
向map添加元素
对一个map进行insert操作时，必须记住元素类型是pair。通常，对于想要插入的数据，并没有一个现成的pair对象。可以在insert的参数列表中创建一个pair
检测insert的返回值
向multiset或multimap添加元素
11.3.3 删除元素
关联容器定义了三个版本的erase，如表11.5所示。与顺序容器一样，我们可以通过传递给erase一个迭代器或一个迭代器对来删除一个元素或者一个元素范围。这两个版本的erase与对应的顺序容器的操作非常相似：指定的元素被删除，函数返回void。
关联容器提供一个额外的erase操作，它接受一个key_type参数。此版本删除所有匹配给定关键字的元素（如果存在的话），返回实际删除的元素的数量。
11.3.4 map的下标操作
map和unordered_map容器提供了下标运算符和一个对应的at函数（参见9.3.2节，第311页），如表11.6所示。set类型不支持下标，因为set中没有与关键字相关联的“值”。
我们不能对一个multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。
如果关键字并不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化（参见3.3.1节，第88页）。
将会执行如下操作：
- 在word_count中搜索关键字为Anna的元素，未找到。
- 将一个新的关键字-值对插入到word_count中。关键字是一个const string，保存Anna。值进行值初始化，在本例中意味着值为0。
- 提取出新插入的元素，并将值1赋予它。
由于下标运算符可能插入一个新元素，我们只可以对非const的map使用下标操作。
11.3.5 访问元素
对map使用find代替下标操作
我们只是想知道一个给定关键字是否在map中，而不想改变map。这样就不能使用下标运算符来检查一个元素是否存在，因为如果关键字不存在的话，下标运算符会插入一个新元素。在这种情况下，应该使用find
在multimap或multiset中查找元素
如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。
例如，给定一个从作者到著作题目的映射，我们可能想打印一个特定作者的所有著作。
可以用三种不同方法来解决这个问题。最直观的方法是使用find和count：
一种不同的，面向迭代器的解决方法
我们还可以用lower_bound和upper_bound来解决此问题。这两个操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound返回的迭代器将指向第一个具有给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。如果元素不在multimap中，则lower_bound和upper_bound会返回相等的迭代器——指向一个不影响排序的关键字插入位置。因此，用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围（参见9.2.1节，第296页），表示所有具有该关键字的元素的范围。
这两个操作返回的迭代器可能是容器的尾后迭代器。如果我们查找的元素具有容器中最大的关键字，则此关键字的upper_bound返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则lower_bound返回的也是尾后迭代器。
lower_bound返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。如果关键字不在容器中，则lower_bound会返回关键字的第一个安全插入点——不影响容器中元素顺序的插入位置。
equal_range函数
解决此问题的最后一种方法是三种方法中最直接的：不必再调用upper_bound和lower_bound，直接调用equal_range即可。此函数接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。
11.3.6 一个单词转换的map
给定一个string，将它转换为另一个string。程序的输入是两个文件。第一个文件保存的是一些规则，用来转换第二个文件中的文本。每条规则由两部分组成：一个可能出现在输入文件中的单词和一个用来替换它的短语。表达的含义是，每当第一个单词出现在输入中时，我们就将它替换为对应的短语。第二个输入文件包含要转换的文本。
11.4 无序容器
新标准定义了4个无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数（hash function）和关键字类型的==运算符。在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。
使用无序容器
通常可以用一个无序容器替换对应的有序容器，反之亦然。
管理桶
无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
对于相同的参数，哈希函数必须总是产生相同的结果。
当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。
无序容器提供了一组管理桶的函数，如表11.8所示。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。
无序容器对关键字类型的要求
无序容器使用关键字类型的==运算符来比较元素，它们还使用一个hash
不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的hash模板版本。我们将在16.5节（第626页）中介绍如何做到这一点。
我们不使用默认的hash，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作（参见11.2.2节，第378页）。为了能将Sale_data用作关键字，我们需要提供函数来替代==运算符和哈希值计算函数。我们从定义这些重载函数开始
