第11章 关联容器

关联容器和顺序容器的不同：关联容器中的元素时按照关键字来保存和访问的。
关联容器支持通过关键字来高效地查找和读取元素，基本的关联容器类型是 map和 set。

关联容器类型：

map和multimap在头文件map中；set和multiset在头文件set中
无序容器分别定义在unordered_map和unordered_set中
当从map中提取一个元素时，会得到一个pair类型的对象
pair是一个模版类型，保存两个名为first和second的（公有）数据成员
set的底层实现是红黑树

容器类型	解释
按顺序存储
`map`	关键数组：保存`关键字-值`对
`set`	关键字即值，即只保存关键字的容器
`multimap`	支持同一个键多次出现的`map`
`multiset`	支持同一个键多次出现的`set`
无序集合
`unordered_map`	用哈希函数组织的`map`
`unordered_set`	用哈希函数组织的`set`
`unordered_multimap`	哈希组织的`map`，关键字可以重复出现
`unordered_multiset`	哈希组织的`set`，关键字可以重复出现

关联容器概述

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

定义关联容器

需要指定元素类型。
列表初始化：
- map：map<string, int> word_count = {{"a", 1}, {"b", 2}};
  {key, value} 的方式可以用来初始化pair
- set：set<string> exclude = {"the", "a"};
从一个值范围来初始化关联列表：
- set<int> iset(ivec.cbegin(), ivec.cend());

关键字类型的要求

对于有序容器，关键字类型必须定义元素比较的方法。默认是<。
如果想传递一个比较的函数，可以这样定义：multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn); 即需要提供关键字类型和比较操作类型——应该是一种函数指针类型。
- 用compareIsbn来初始化bookstore对象，这表示向bookstore添加元素时，通过调用compareIsbn来为这些元素排序。
- bookstore中的元素以ISBN的顺序进行排列。
- 注意当使用decltype来获得一个函数指针类型时，必须加上一个*来指定我们要使用给定函数类型的指针。
- 参数用compareIbn和&compareIsbn效果相同，当使用函数名字时，在需要时它会自动转化为一个指针。

练习11.10

Q: 定义一个map，将单词与一个行号的list关联，list中保存的是单词所出现的行号。

1	std::map<std::string, std::list<std::size_t>> m;

练习11.11

Q: 可以定义一个vector<int>::iterator 到 int 的map吗？list<int>::iterator 到 int 的map呢？对于两种情况，如果不能，解释为什么。

可以定义 vector<int>::iterator 到 int 的map，但是不能定义 list<int>::iterator 到 int 的map。因为map的键必须实现 < 操作，list 的迭代器不支持比较运算。

pair

在utility头文件中定义。
一个pair保存两个数据成员，两个类型不要求一样。

pair的操作：

操作	解释
`pair<T1, T2> p;`	`p`是一个`pair`，两个类型分别是`T1`和`T2`的成员都进行了值初始化。
`pair<T1, T2> p(v1, v2);`	`first`和`second`分别用`v1`和`v2`进行初始化。
`pair<T1, T2>p = {v1, v2};`	等价于`p(v1, v2)
`make_pair(v1, v2);`	`pair`的类型从`v1`和`v2`的类型推断出来。
`p.first`	返回`p`的名为`first`的数据成员。
`p.second`	返回`p`的名为`second`的数据成员。
`p1 relop p2`	运算关系符按字典序定义。
`p1 == p2`	必须两对元素两两相等
`p1 != p2`	同上

关联容器操作

关联容器额外的类型别名：

类型别名	解释
`key_type`	此容器类型的关键字类型
`mapped_type`	每个关键字关联的类型，只适用于`map`
`value_type`	对于`map`，是`pair<const key_type, mapped_type>`; 对于`set`，和`key_type`相同。

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

关联容器迭代器

解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。
一个map的value_type是一个pair，但我们可以改变pair值，却不能改变关键字成员的值（因为是const的）。
set的迭代器是const的，是只读的。虽然set类型同时定义类iterator和const_iterator类型，但两种类型都只允许只读访问set中的元素。
遍历关联容器：使用begin和end，遍历map、multimap、set、multiset时，迭代器按关键字升序遍历元素。
通过迭代器访问元素时需要解引用，比如map_it->first。再次强调map_it->first和*set_it 都是const的。
通常不对关联容器使用泛型算法，如果我们真要对一个容器使用算法，要么是将其当作一个原序列，要么当做一个目的位置。比如c是一个string的multiset，v 是一个string 的vector，可以使用copy(v.begin(), v.end(), inserter(c, c.end()));。

添加元素

关联容器insert操作：

由于map和set（以及对应的无序类型）包含不重复的关键字，因此插入一个已经存在的元素对容器不会有任何影响。但是会返回一个pair告诉我们插入失效。

10   map<int, int> mp;
11   mp.insert({1, 1});
12   mp.insert({1, 2});
13   printf("%d\n", mp[1]);  // 1

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

向map添加元素：

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));

练习11.22

Q: 给定一个map<string, vector<int>>，对此容器的插入一个元素的insert版本，写出其参数类型和返回类型。

1 2	std::pair<std::string, std::vector<int>> // 参数类型 std::pair<std::map<std::string, std::vector<int>>::iterator, bool> // 返回类型

删除元素

从关联容器中删除元素：

操作	解释
`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`。

使用c.erase(k)删除不存在的k并不会报错：

int main() {
    unordered_map<int, int> hash{{1, 2}};
    cout << hash.erase(1) << endl;
    cout << hash.erase(2) << endl;
    return 0;
}

下标操作

map和unordered_map的下标操作：

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

由于下标运算符可能插入一个新元素，所以只能对非const的map使用下标操作。
通常情况下，解引用一个迭代器所返回的类型和下标运算符返回的类型是一样的，但是对map进行下标操作时会获得一个mapped_type对象，而解引用一个map迭代器时会得到一个value_type对象（pair<const key_type, mapped_type>

查找元素

在一个关联容器中查找元素:

操作	解释
`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`的两个成员均指向关键字可插入的位置。

lower_bound和upper_bound不适用于无序容器。
二者并不报告关键字是否存在，重要的是它们的返回值可以作为一个迭代器范围。个人感觉使用c.equal_range(k)好。
- 如果目标关键字存在，则lower_bound返回的迭代器指向第一个具有给定关键字的元素，而uppper_bound返回的迭代器指向最后一个匹配给定关键字之后的位置。
- 如果不存在，则二者返回相同的位置——指向一个不影响排序的关键字插入位置。
下标和at操作只适用于非const的map和unordered_map。

练习11.30

Q: 对于本节最后一个程序中的输出表达式，解释运算对象pos.first->second的含义。

pos 是一个pair，pos.first 是一个迭代器，指向匹配关键字的元素，该元素是一个 pair，访问该元素的第二个成员。

Q: 编写程序，定义一个作者及其作品的multimap。使用find在multimap中查找一个元素并用erase删除它。确保你的程序在元素不在map 中时也能正常运行。

#include <map>
#include <string>
#include <iostream>

using std::string;

int main()
{
	std::multimap<string, string> authors{
		{ "alan", "DMA" },
		{ "pezy", "LeetCode" },
		{ "alan", "CLRS" },
		{ "wang", "FTP" },
		{ "pezy", "CP5" },
		{ "wang", "CPP-Concurrency" } };

	string author = "pezy";
	string work = "CP5";

	auto found = authors.find(author);
	auto count = authors.count(author);
	while (count)
	{
		if (found->second == work)
		{
			authors.erase(found);
			break;
		}
		++found;  // multimap中key按序排列
		--count;
	}

	for (const auto &author : authors)
		std::cout << author.first << " " << author.second << std::endl;

	return 0;
}

一个单词转换的map

练习11.33

Q: 实现你自己版本的单词转换程序。

#include <map>
#include <string>
#include <fstream> 
#include <iostream>
#include <sstream>

using std::string; using std::ifstream;

std::map<string, string> buildMap(ifstream &map_file) {
  std::map<string, string> trans_map;
  std::string key, value;
  // 读取第一个单词存入key中，行中剩余内容存入value
  while (map_file >> key && getline(map_file, value))
    if (value.size() > 1) 
      trans_map[key] = value.substr(1);  // 跳过前导空格
    else
      throw runtime_error("no rule for " + key)
  return trans_map;
}

const string & transform(const string &s, const std::map<string, string> &m) {
    auto map_it = m.find(s);  // 使用find而非下标运算符以避免产生新元素
    return map_it == m.cend() ? s : map_it->second;
}

void word_transform(ifstream &map, ifstream &input) {
  auto trans_map = buildMap(map);
  std::string text
  while (getline(input, text)) {
    std::istringstream iss(text);  // 读取每个单词
    std::string word
    while (iss >> word)
        std::cout << transform(word, trans_map) << " ";
    std::cout << std::endl;
  }
}

int main() {
  ifstream ifs_map("../data/word_transformation_bad.txt");
  ifstrean ifs_content("../data/given_to_transform.txt");
  if (ifs_map && ifs_content) word_transform(ifs_map, ifs_content);
  else std::cerr << "can't find the documents." << std::endl;
}

注意 getline 不会跳过前导空格，也不会跳过行首换行符（会导致第二参数为空字符串），它会一直读到下一个换行符，会“吃了”这个换行符，但返回第二个参数中并不会包含此换行符。

练习11.35

Q:在buildMap中，如果进行如下改写，会有什么效果？

1
2
3

trans_map[key] = value.substr(1);
//改为
trans_map.insert({key, value.substr(1)});

A: 当一个转换规则的关键字多次出现的时候，使用下标运算符会保留最后一次添加的规则，而用insert则保留第一次添加的规则。

无序容器

有序容器使用比较运算符来组织元素；无序容器使用哈希函数和关键字类型的==运算符。
理论上哈希技术可以获得更好的性能。
无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。
无论在有序容器中还是在无序容器中，具有相同关键字的元素都是相邻存储的。

无序容器管理操作：

操作	解释
桶接口
`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.reverse(n)`	重组存储，使得`c`可以保存`n`个元素且不必`rehash`。

标准库为内置类型（包括指针）提供了hash模版，还为一些标准库类型，包括string和智能指针类型定义了hash。
不能直接定义关键字类型为自定义类型的无序容器。与容器不同，不能直接使用hash模版，而必须提供自己的hash模版版本（P626）
不使用默认hash，但可以使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作。