第 11 章 关联容器

C++Primer 学习记录 关联容器

11.1 使用关联容器

1. 标准库中定义了 8个关联容器，这些容器的不同体现在三个维度上。
   
   • 或者是一个 set，或者是一个 map。
   • 或者要求不重复的关键字，或者允许重复关键字，允许重复的容器的名字中都包含单词 multi。
   • 或者按顺序保存元素或无序保存。不保持关键字按顺序存储的容器的名字都以 unordered开头。

11.2 关联容器概述

1. 当初始化一个 map时，必须提供关键字类型和值类型。将每个关键字——值对包围在花括号中：{key, value}

   map<string, string> authors = { {"Joyce", "James"},
                                   {"Austen", "Jane"} };

2. map或 set中的关键字必须是唯一的，用含有重复元素的容器的迭代器来初始化 map或set，得到的结果中对于重复元素也只会有一份拷贝。

3. 对于有序容器，关键字类型必须定义元素比较的方法。默认情况下，标准库使用<运算符来比较两个关键字。当然，也可以使用自定义的操作来比较两个关键字。此时必须在定义关联容器类型时就提供此操作的类型。

   bool compare(const A &lhs, const A &rhs);
   // 关于下式，第一个 compare出现的地方需要的是函数指针类型，而
   // decltype返回的是一个函数类型，所以 *必不可少。而第二个 compare
   // 出现的地方需要的是函数指针类型的实参，此时函数名可以自动转化为一个指针
   set<A, decltype(compare)*> aSet(compare);

4. 当一个函数需要返回一个 pair时，下面四种写法都是正确的。

   // 隐式构造
   return pair<string, int>();
   // 显示构造
   return pair<string, int>("test", 3);
   // 利用 make_pair生成 pair对象
   return make_pair("test", 3);
   // 列表初始化
   return {"test", 3};

11.3 关联容器操作

1. 关联容器定义了一些额外的类型别名。由于我们不能改变一个元素的关键字，因此这些 pair的关键字部分是 const的。

   • key_type，关键字类型
   • mapped_type，只适用于 map，每个关键字关联的类型
   • value_type，对于 set，等于 key_type；对于 map，为 pair< const key_type, mapped_type >。
   • 在使用作用域运算符来提取一个类型成员时，记得加上模板参数：
     

     map<string, int>::value_type v3;

2. 解引用一个关联容器迭代器时，会得到一个类型为容器的 value_type的值的引用。因此，对于 map，得到的是 pair类型的引用。可以改变 pair的 second成员，即元素的值，但是不能改变 pair的 first成员，即元素的关键字；对于 set，其关键字也是 const的，set迭代器只能用来读取元素的值。

   map<string, int> word_count;
   auto map_it = word_count.begin();
   map_it->first = "new key";    // 错误，关键字是 const的
   ++map_it->second;             // 正确，元素的值可以改变

3. 通常不对关联容器使用泛型算法。

   • 关键字是 const的，这一特性使得不能将需要修改或重排容器元素的算法传递给关联容器。

   • 关联容器可用于只读元素的算法，但是这类算法通常都要搜索序列，而对于关联容器，使用自定义的查找算法（基于二分查找）会比泛型算法（逐一比较）快得多。

   • 真要对一个容器使用关联算法，要么将它当作一个源序列，要么当作是一个目的位置（inserter）。

4. c.insert(i1)，返回一个 pair类型。其 first成员是一个迭代器，指向具有给定关键字的元素；second成员具有一个 bool值，指出元素插入是否成功。

   • 关键字已存在，insert什么也不做，返回值中的bool部分为 false。
   • 关键字不存在，元素被插入到容器中，且 bool值为 true。

5. c.erase(k)，从 c中删除每个关键字为 k的元素，返回删除的元素的数量。

6. map和 unordered_map提供了下标运算符和一个对应的 at函数，下标操作需要一个值与一个关键字对应，因此 set或 multimap不支持下标操作。

   • 下标运算，当关键字不在 map中时，会为它创建一个元素并插入到 map中，关联值进行值初始化。并且，下标运算返回的是一个左值引用，因此既可以读也可以写元素。

     map<string, size_t> word_count;  // 空 map
     word_count["Anna"] = 1;

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

   • 通常情况下，解引用一个迭代器与下标运算符的返回类型是一样的。但对于 map则不然。解引用——>value_type，下标——>mapped_type。

   • c.at(k)。带参数检查，如果 k不在 c中，抛出一个 out_of_range异常。

7. c.find(k)，返回一个迭代器，指向第一个关键字为 k的元素。若 k不在容器中，则返回尾后迭代器。

8. c.count(k)，返回关键字等于 k的元素的数量。

11.4 无序容器

1. 无序容器使用一个哈希函数和关键字类型的==运算符来组织元素。如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器，性能会更好。

2. 标准库为内置类型（包括指针类型）、string和智能指针类型定义了 hash模板，可以直接定义关键字是以上类型的无序容器。但是，我们不能定义关键字类型为自定义类型的无序容器。一种方法是提供自定义类型的 hash模板版本，一种方法是重载 hash函数和==运算符。

   size_t hasher(cosnt A &a);
   bool eqOp(const A &lhs, const A &rhs);
   using A_set = unordered_multiset<A, decltype(hasher)*, decltype(eqOp)*>;
   // 构造参数是桶大小、哈希函数和相等性判断运算符指针
   A_set aSet(42, hasher, qeOp);