11.1 使用关联容器

set 支持高效的关键字查询操作——检查一个给定关键字是否在 set 中。

标准库提供 8 个关联容器，如下表所示：

关联容器类型
按关键字有序保存元素
map	关联数组；保存关键字-值对
set	关键字即值，即只保存关键字的容器
multimap	关键字可重复出现的 map
multiset	关键字可重复出现的 set
无序集合
unordered_map	用哈希函数组织的 map
unordered_set	用哈希函数组织的 set
unordered_multimap	哈希组织的 map；关键字可以重复出现
unordered_multiset	哈希组织的 set；关键字可以重复出现

这 8 个容器间的不同体现在三个维度上：每个容器（1）或者是一个 set，或者是一个 map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。

类型 map 和 multimap 定义在头文件 map 中；set 和 multiset 定义在头文件 set 中；无序容器则定义在头文件 unordered_map 和 unordered_set 中。
使用下标查找 map 中的元素时，若元素不存在，则会新建。
当从 map 中提取一个元素时，会得到一个 pair 类型的对象，简单来说，pair 是一个模板类型，保存两个名为 first 和 second 的（公有）数据成员。map 所使用的 pair 用 first 成员保存关键字，用 second 成员保存对应的值。
与顺序容器类似，可以对一个关联容器的元素进行列表初始化。

11.2 关联容器概述

关联容器不支持顺序容器的位置相关的操作，例如 push_front 或 push_back。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
关联容器的迭代器都是双向的。

11.2.1 定义关联容器

每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，我们也可以对关联容器进行值初始化。
一个 map 或 set 中的关键字必须是唯一的，即，对于一个给定的关键字，只能有一个元素的关键字等于它。容器 multimap 和 multiset 没有此限制，它们都允许多个元素具有相同的关键字。

观察下述代码：

// 定义一个有 20 个元素的 vector，保存 0 到 9 每个整数的两个拷贝
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i)
{
    ivec.push_back(i);
    ivec.push_back(i); // 每个数重复保存一次
}
// iset 包含来自 ivec的 不重复的元素；miset 包含所有 20 个元素
set<int> iset(ivec.cbegin(), ivec.cend());
multiset<int> miset(ivec.cbegin(), ivec.cend());
cout << ivec.size() << endl;  // 打印出 20
cout << iset.size() << endl;  // 打印出 10
cout << miset.size() << endl; // 打印出 20

11.2.2 关键字类型的要求

对于有序容器——map、multimap、set 以及 multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。
可以向一个算法提供我们自己定义的比较操作，与之类似，也可以提供自己定义的操作来代替关键字上的 < 运算符。所提供的操作必须在关键字类型上定义一个严格弱序（strict weak ordering）。可以将严格弱序看作“小于等于”。
如果两个关键字是等价的（即，任何一个都不“小于等于”另一个），那么容器将它们视作相等来处理。当用作 map 的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。
Note： 在实际编程中，重要的是，如果一个类型定义了“行为正常”的 < 运算符，则它可以用作关键字类型。
为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。
假如我们有个 compareIsbn 函数：
1
2
3
4
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
return lhs.isbn() < rhs.isbn();
}
此函数在 Sales_data 对象的 ISBN 成员上定义了一个严格弱序，假设我们想定义一个 Sales_data 的 multiset，为了使用自己定义的操作，在定义 multiset 时我们必须提供两个类型：关键字类型 Sales_data，以及比较操作类型——应该是一种函数指针类型，可以指向 compareIsbn。当定义此容器类型的对象时，需要提供想要使用的操作的指针：
1
2
3
// bookstore 中多条记录可以有相同的 ISBN
// bookstore 中的元素以 ISBN 的顺序进行排列
multiset<Sales_data, decltype(compareIsbn) *> bookstore(compareIsbn);
此处，我们使用 decltype 来指出自定义操作的类型。记住，当用 decltype 来获得一个函数指针类型时，必须加上一个 * 来指出我们要使用一个给定函数类型的指针。用 compareIsbn 来初始化 bookstore 对象，这表示当我们向 bookstore 添加元素时，通过调用 compareIsbn 来为这些元素排序。即，bookstore 中的元素将按它们的 ISBN 成员的值排序。可以用 compareIsbn 代替 &compareIsbn 作为构造函数的参数，因为当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针。

11.2.3 pair 类型

pair 标准库类型定义在头文件 utility。
pair 的默认构造函数对数据成员进行值初始化，也可以为每个成员提供初始化器：
1
pair<string, string> author{"James", "Joyce"};
与其他标准库类型不同，pair 的数据成员是 public 的，两个成员分别命名为 first 和 second。我们用普通的成员访问符号来访问他们。

标准库只定义了有限的几个 pair 操作：

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};	等价于 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.first < p2.first 或 !(p2.first < p1.first) && p1.second < p2.second 成立时，p1 < p2 为 true。关系运算利用元素的 < 运算符来实现
p1 == p2	当 first 和 second 成员分别相等时，两个 pair 相等。相等性判断利用元素的 == 运算符实现
p1 != p2	当 first 和 second 成员分别相等时，两个 pair 相等。相等性判断利用元素的 == 运算符实现

11.3 关联容器操作

关联容器定义了几个额外的类型别名：

关联容器额外的类型别名
key_type	此容器类型的关键字类型
mapped_type	每个关键字关联的类型；只适用于 map
value_type	对于 set，与 key_type 相同；对于 map，为 pair<const key_type, mapped_type>

对于 set 类型，key_type 和 value_type 是一样的；set 中保存的值就是关键字。在一个 map 中，元素是关键字-值对。即，每个元素是一个 pair 对象，包含一个关键字和一个关联的值。由于我们不能改变一个元素的关键字，因此这些 pair 的关键字部分是 const 的：

set<string>::value_type v1;       // v1 是一个 string
set<string>::key_type v2;         // v2 是一个 string
map<string, int>::value_type v3;  // v3 是一个 pair<const string, int>
map<string, int>::key_type v4;    // v4 是一个 string
map<string, int>::mapped_type v5; // v5 是一个 int

我们使用作用域运算符来提取一个类型的成员——例如，map<string, int>::key_type。

11.3.1 关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的 value_type 的值的引用。对 map 而言，value_type 是一个 pair 类型，其 first 成员保存 const 的关键字，second 成员保存值。

Note： 必须记住，一个 map 的 value_type 是一个 pair，我们可以改变 pair 的值，但不能改变关键字成员的值。
虽然 set 类型同时定义了 iterator 和 const iterator 类型，但两种类型都只允许只读访问 set 中的元素。与不能改变一个 map 元素的关键字一样，一个 set 中的关键字也是 const 的。可以用一个 set 迭代器来读取元素的值，但不能修改。
Note： 当使用一个迭代器遍历一个 map、multimap、set 或 multiset 时，迭代器按关键字升序遍历元素。
我们通常不对关联容器使用泛型算法。 关键字是 const 这一特性意味着不能将关联容器传递给修改或重排容器元素的算法，因为这类算法需要向元素写入值，而 set 类型中的元素是 const 的，map 中的元素是 pair，其第一个成员是 const 的。关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。关联容器定义了一个名为 find 的成员，它通过一个给定的关键字直接获取元素。我们可以用泛型 find 算法来查找一个元素，但此算法会进行顺序搜索。使用关联容器定义的专用的 find 成员会比调用泛型 find 快得多。

练习 11.17： 假定 c 是一个 string 的 multiset，v 是一个 string 的 vector，解释下面的调用。指出每个调用是否合法：

copy(v.begin(), v.end(), inserter(c, c.end())); // 合法
copy(v.begin(), v.end(), back_inserter(c));     // 不合法
copy(c.begin(), c.end(), inserter(v, v.end())); // 合法
copy(c.begin(), c.end(), back_inserter(v));     // 合法

back_inserter 会调用容器的 push_back 方法，但关联容器不包含该方法。

11.3.2 添加元素

关联容器的 insert 成员向容器中添加一个元素或一个元素范围。由于 map 和 set（以及对应的无序类型）包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响：

vector<int> ivec = {2, 4, 6, 8, 2, 4, 6, 8}; // ivec 有 8 个元素
set<int> set2;                               // 空集合
set2.insert(ivec.cbegin(), ivec.cend());     // set2 有 4 个元素
set2.insert({1, 3, 5, 7, 1, 3, 5, 7});       // set2 现在有 8 个元素

insert 有两个版本，分别接受一对迭代器，或是一个初始化器列表，这两个版本的行为类似对应的构造函数——对于一个给定的关键字，只有第一个带此关键字的元素才被插入到容器中。

对一个 map 进行 insert 操作时，必须记住元素类型是 pair。通常，对于想要插入的数据，并没有一个现成的 pair 对象。可以在 insert 的参数列表中创建一个 pair：

// 向 word_count 插入 word 的 4 种方法
word_count.insert({word, 1});
word_count.insert(make_pair(word, 1));
word_count.insert(pair<string, size_t>(word, 1));
word_count.insert(map<string, size_t>::value_type(word, 1));

在 C++11 新标准下，创建一个 pair 最简单的方法是在参数列表中使用花括号初始化。也可以调用 make_pair 或显式构造 pair。

关联容器的 insert 操作：

关联容器 insert 操作
c.insert(v)	v 是 value_type 类型的对象；args 用来构造一个元素对于 map 和 set，只有当元素的关键字不在 c 中时才插入（或构造）元素。函数返回一个 pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否成功的 bool 值对于 multimap 和 multiset，总会插入（或构造）给定元素，并返回一个指向新元素的迭代器
c.emplace(args)
c.insert(b, e)	b 和 e 是迭代器，表示一个 c::value_type 类型值的范围；il 是这种值的花括号列表。函数返回 void 对于 map 和 set，只插入关键字不在 c 中的元素。对于 multimap 和 multiset，则会插入范围中的每个元素
c.insert(il)
c.insert(p, v)	类似 insert(v)（或 emplace(args)），但将迭代器 p 作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素
c.emplace(p, args)

insert（或 emplace）返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的 insert 和 emplace 版本返回一个 pair，告诉我们插入操作是否成功。pair 的 first 成员是一个迭代器，指向具有给定关键字的元素；second 成员是一个 bool 值，指出元素是插入成功还是已经存在于容器中。如果关键字已在容器中，则 insert 什么事情也不做，且返回值中的 bool 部分为 false。如果关键字不存在，元素被插入容器中，且 bool 值为 true。
练习 11.21： 假定 word_count 是一个 string 到 size_t 的 map，word 是一个 string，解释下面循环的作用：
1
2
while (cin >> word)
++word_count.insert({word, 0}).first->second;
答：读取标准输入到 word 中，使用 word 和 0 组成花括号列表，并 insert 到 word_count 中，insert 返回一个 pair，pair 的首元素是指向新插入元素（也是个 pair）的迭代器，新插入元素的 second 是计数器，对其实施前置递增。
练习 11.22： 给定一个 map<string, vector<int>>，对此容器的插入一个元素的 insert 版本，写出其参数类型和返回类型。

答：参数类型 pair<string, vector<int>>；返回类型 pair<map<string, vector<int>>::iterator, bool>。

11.3.3 删除元素

关联容器定义了三个版本的 erase，与顺序容器一样，我们可以通过传递给 erase 一个迭代器或一个迭代器对来删除一个元素或者一个元素范围。

关联容器提供一个额外的 erase 操作，它接受一个 key_type 参数。此版本删除所有匹配给定关键字的元素（如果存在的话），返回实际删除的元素的数量。使用这个 erase 操作时：对于保存不重复关键字的容器，erase 的返回值总是 0 或 1，若返回值为 0，则表明想要删除的元素并不在容器中；对允许重复关键字的容器，删除元素的数量可能大于 1。

从关联容器删除元素
c.erase(k)	从 c 中删除每个关键字为 k 的元素。返回一个 size_type 值，指出删除的元素的数量
c.erase(p)	从 c 中删除迭代器 p 指定的元素。p 必须指向 c 中一个真实元素，不能等于 c.end()。返回一个指向 p 之后元素的迭代器，若 p 指向 c 中的尾元素，则返回 c.end()
c.erase(b, e)	删除迭代器对 b 和 e 所表示的范围中的元素。返回 e

11.3.4 map 的下标操作

map 和 unordered_map 容器提供了下标运算符和一个对应的 at 函数：

map 和 unordered_map 的下标操作
c[k]	返回关键字为 k 的元素；如果 k 不在 c 中，添加一个关键字为 k 的元素，对其进行值初始化
c.at(k)	访问关键字为 k 的元素，带参数检查；若 k 不在 c 中，抛出一个 out_of_range 异常

set 类型不支持下标，因为 set 中没有与关键字相关联的“值”。我们不能对一个 multimap 或一个 unordered_multimap 进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

类似我们用过的其他下标运算符，map 下标运算符接受一个索引（即，一个关键字），获取与此关键字相关联的值。但是，与其他下标运算符不同的是，如果关键字并不在 map 中，会为它创建一个元素并插入到 map 中，关联值将进行值初始化。由于下标运算符可能插入一个新元素，我们只可以对非 const 的 map 使用下标操作。
Note： 对一个 map 使用下标操作，其行为与数组或 vector 上的下标操作很不相同：使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到 map 中。
map 的下标运算符与我们用过的其他下标运算符的另一个不同之处是其返回类型。通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但对 map 则不然：当对一个 map 进行下标操作时，会获得一个 mapped_type 对象；但当解引用一个 map 迭代器时，会得到一个 value_type 对象。与其他下标运算符相同的是，map 的下标运算符返回一个左值。由于返回的是一个左值，所以我们既可以读也可以写元素。

与 vector 与 string 不同，map 的下标运算符返回的类型与解引用 map 选代器得到的类型不同。
如果关键字还未在 map 中，下标运算符会添加一个新元素，有时只是想知道一个元素是否已在 map 中，但在不存在时并不想添加元素。在这种情况下，就不能使用下标运算符。

11.3.5 访问元素

关联容器提供多种查找一个指定元素的方法，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()

如果我们所关心的只不过是一个特定元素是否已在容器中，可能 find 是最佳选择。对于不允许重复关键字的容器，可能使用 find 还是 count 没什么区别。但对于允许重复关键字的容器，count 还会做更多的工作：如果元素在容器中，它还会统计有多少个元素有相同的关键字。如果不需要计数，最好使用 find。
使用下标操作有一个严重的副作用：如果关键字还未在 map 中，下标操作会插入一个具有给定关键字的元素。
如果一个 multimap 或 multiset 中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。
如果关键字在容器中，lower_bound 返回的迭代器将指向第一个具有给定关键字的元素，而 upper_bound 返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。如果元素不在 multimap 中，则 lower_bound 和 upper_bound 会返回相等的迭代器——指向一个不影响排序的关键字插入位置。因此，用相同的关键字调用 lower_bound 和 upper_bound 会得到一个迭代器范围，表示所有具有该关键字的元素的范围。
如果我们查找的元素具有容器中最大的关键字，则此关键字的 upper_bound 返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则 lower_bound 返回的也是尾后送代器。
Note：lower_bound 返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。如果关键字不在容器中，则 lower_bound 会返回关键字的第一个安全插入点——不影响容器中元素顺序的插入位置。
如果没有元素与给定关键字匹配，则 lower_bound 和 upper_bound 会返回相等的迭代器——都指向给定关键字的插入点，能保持容器中元素顺序的插入位置。
Note： 如果 lower_bound 和 upper_bound 返回相同的迭代器，则给定关键字不在容器中。
equal_range 函数接受一个关键字，返回一个迭代器 pair。若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。

11.3.6 一个单词转换的 map

11.4 无序容器

无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数（hash function）和关键字类型的 == 运算符。在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。
虽然理论上哈希技术能获得更好的平均性能，但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作。因此，使用无序容器通常更为简单（通常也会有更好的性能）。
Tip： 如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。
通常可以用一个无序容器替换对应的有序容器，反之亦然。
无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。
对于相同的参数，哈希函数必须总是产生相同的结果。理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量比较操作。

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

无序容器管理操作
桶接口
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
c.rehash(n)	重组存储，使得 bucket count >= n 且 bucket_count > size/max_load_factor
c.reserve(n)	重组存储，使得 c 可以保存 n 个元素且不必 rehash

默认情况下，无序容器使用关键字类型的 == 运算符来比较元素，它们还使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值。标准库为内置类型（包括指针）提供了 hash 模板。还为一些标准库类型，包括 string 和智能指针类型定义了 hash。因此，我们可以直接定义关键字是内置类型（包括指针类型）、string 还有智能指针类型的无序容器。

不能直接定义关键字类型为自定义类类型的无序容器。 与容器不同，不能直接使用哈希模板，而必须提供我们自己的 hash 模板版本。我们不使用默认的 hash，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作。为了能将 Sales_data 用作关键字，我们需要提供函数来替代 == 运算符和哈希值计算函数。我们从定义这些重载函数开始：

size_t hasher(const Sales_data &sd)
{
    return hash<string>()(sd.isbn());
}
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() == rhs.isbn();
}

我们使用这些函数来定义一个 unordered_multiset：

using SD_multiset = unordered_multiset<Sales_data,
                                       decltype(hasher) *,
                                       decltype(eqOp) *>;
// 参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42, hasher, eqOp);

练习 11.37： 一个无序容器与其有序版本相比有何优势？有序版本有何优势？

答：无序关联容器效率更高，有序关联容器默认将元素根据键进行排序。

小结

关联容器支持通过关键字高效查找和提取元素。对关键字的使用将关联容器和顺序容器区分开来，顺序容器中是通过位置访问元素的。
有序容器使用比较函数来比较关键字，从而将元素按顺序存储。默认情况下，比较操作是采用关键字类型的 < 运算符。无序容器使用关键字类型的 == 运算符和一个 hash<key_type> 类型的对象来组织元素。
有序容器的迭代器通过关键字有序访问容器中的元素。无论在有序容器中还是在无序容器中，具有相同关键字的元素都是相邻存储的。

输出倒逼思考

C++ Primer - 第 11 章关联容器