C++ Primer 第十一章 关联容器

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器支持高效的关键字查找和访问。两个主要的关联容器（associative-container）类型是 map 和 set。

map中的元素是一些关键字-值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。

set中每个元素只包含一个关键字，set支持高效的关键字查询操作。

类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器则定义在头文件unordered_map和unordered_set中。无序容器使用哈希函数来组织元素。

关联容器类型：

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

11.1 关联容器概述

关联容器（有序和无序的）都支持如下的普通容器操作：

关联容器不支持顺序容器位置相关的操作，例如push_front或push_back，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。

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

11.1.1 定义关联容器

每个关联容器都定义一个默认构造函数，它创建一个指定类型的空容器。我们可以将关联容器初始化为另一个同类型容器的拷贝，或者从一个值范围来初始化关联容器，只要这些值可以转换为容器所需类型就行。在新标准下，我们也可以对关联容器进行值初始化，与往常一样，初始化器必须能够转换为容器中元素的类型：

map<string, size_t> word_count; //空容器
//列表初始化
set<string> exclude = {"the", "but", "and"};
//两个元素，列表初始化
map<string, string> authors = { {"Joyce", "James"}, {"Austen", "Jane"}  };

11.1.2 关键字类型的要求

11.1.2.1 有序容器

关键字类型必须定义元素比较的方法，默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。

11.1.2.2 无序容器

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

因此，我们可以直接定义关键字是内置类型（包括指针类型）、string还有智能指针类型的无序容器。

但是，我们不能直接定义关键字类型为自定义类类型的无序容器。我们必须提供自己的hash模板版本。

11.1.2.3 使用关键字类型的比较函数

multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

• 用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出
• 比较操作的类型应该是一种函数指针类型
• 在尖括号中的类型仅仅是一个类型而已，当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与尖括号中指定的类型吻合）
• 当使用decltype来获得一个函数指针类型时，必须加上一个“*”来指出我们需要一个函数指针类型
• 用于初始化 bookstore 对象的参数也可以写作&compareIsbn，因为函数名会自动转换为函数指针

11.1.3 pair 类型

pair标准库类型定义在头文件utility中。一个pair保存两个数据成员。pair是一个用来生成特定类型的模板。pair的默认构造函数对数据成员进行值初始化。

pair的成员是public的，两个成员为first和second。

标准库定义的pair操作：

创建返回 pair 对象的函数

pair<string, int> process(vector<string> &v)
{
    //处理 v
    if (!v.empty())
        //列表初始化
        return {v.back(), v.back().size()};
    else
        //隐式构造返回值
        return pair<string, int>();
}

11.2 关联容器操作

关联容器额外定义了一些类型别名：

由于我们不能改变一个元素的关键字，因此这些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

11.2.1 关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的 value_type 的值的引用。

• 对map而言，得到pair类型，其 first 成员保存const关键字，second 成员保存值
• 对set而言，迭代器也是const的

当使用一个迭代器遍历一个map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

我们通常不对关联容器使用泛型算法。在实际编程中，如果我们真的要对一个关联容器使用算法，要么将它作为一个源序列，要么将它作为一个目的位置。

11.2.2 添加元素

返回值：

• 不包含重复关键字的容器：返回一个pair，first 成员是一个迭代器，指向具有给定关键字的元素，second 成员是一个bool值，关键字不存在，为true，否则为false
• 包含重复关键字的容器：返回一个指向新元素的迭代器

11.2.3 删除元素

11.2.4 map 下标操作

由于下标运算可能插入一个新元素，我们只可以对非const的map使用下标操作。

map下标操作与其他下标操作不同的地方：对map进行下标操作时，会得到一个 mapped_type 对象；但当解引用一个map迭代器时，得到一个 value_type 对象。

map下标操作与其他下标操作相同的地方：返回一个左值，可读也可写。

11.2.5 访问元素

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

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

对map使用 find 代替下标操作，以防添加不存在元素。

11.3 无序容器

新标准定义了4个无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的 == 运算符。

除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作。

11.3.1 管理桶

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。

无序容器使用一个哈希函数将元素映射到桶。

为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。

容器将具有一个特定哈希值的所有元素都保存在相同的桶中。

如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。

无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

对于相同的参数，哈希函数必须总是产生相同的结果。

理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是将不同关键字的元素映射到相同的桶也是允许的。

当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在桶中搜索通常都是很快的操作。但是如果一个桶保存了很多元素，那么查找一个特定元素就需要大量比较操作。

无序容器提供了一组管理桶的函数：

11.3.2 无序容器对关键字类型的要求