【笔记】《C++Primer》—— 第11章：关联容器

这一章介绍了标准库中的关联容器们，主要是11.3的对有序关联容器操作的介绍。这章比较短，也只是比较工具性的东西，快速浏览即可。下一章就是C++的重要运用：动态内存管理。

11.1 使用关联容器

• 关联容器和顺序容器有根本的不同，关联容器中的元素是按照关键保存和访问的，而不是顺序容器中的按照容器位置来保存和访问
• 标准库中最主要的两个关联容器就是map和set。map是键值对，set是关键字集。标准库中的关联容器分为无序集合和有序集合，集合中分为map和set，然后map和set都有允许重复关键字的版本，具体如下：

• 和顺序容器一样，关联容器也是模板类型，因此为了定义关联容器我们也需要指定关键字和值的类型，按照：map<关键字, 值>，set<关键字>的格式
• 关联容器同样可以得到对应元素的迭代器，但是使用上稍有差别
• map系列定义在头文件map中
• set系列定义在头文件set中
• 无序容器定义在unordered_map和unordered_set中

11.2 关联容器概述

• 关联容器都支持之前提到的顺序容器的那些普通操作，但是不支持与位置相关的操作如push_back，push_front，也不支持构造函数和插入函数
• 关联容器的迭代器都是双向的
• 关联容器进行初始化时可以用空构造，用迭代器范围进行拷贝构造或C11以后支持的列表初始化。进行列表初始化的时候要注意map需要采用内部花括号进行pair的构造

// map的列表构造 map<int, string > test= { {1, "A"}, { 2,"B" }};

• 使用有序容器时，必须定义关键字元素的比较方法，默认采用<符
• 容器的操作都需要满足严格弱序，类似于小于等于关系，需要满足关系的传递律，即链条上的元素都需要小于等于传递。当两个元素都不小于等于对方时，称这两个元素等价
• 严格弱序条件在实际中我们一般保证任意元素都定义了正常的小于号即可
• 类似谓词我们也可以在初始化容器时在模板列表中传入比较函数，但是这里要注意传入函数时需要动decltype来获得函数指针

bool isSmaller(const int& a, const string& b) {
  return a < b.size();
}

int main() {
  // 提供函数指针进行比较
  map<int, string, decltype(isSmaller)*> test = { {1, "A"}, { 2,"B" } };
  return 0;
}

• map中所存放的元素实际是pair类型的元素对，pair类型是存于头文件utility的标准库类型
• 一个pair保存两个数据成员，也是一种模板容器类，初始化时需要提供两个类型名。
• pair会对其中的数据成员进行值初始化，且其两个数据成员(first，second)都是public的，可以自由操作
• 我们可以用两个值构造pair，可以列表初始化pair，也可以用makepair函数返回一个pair对象。当使用makepair时，pair的类型是编译器推断的

11.3 关联容器操作

• 关联容器有一组表示出容器类型的成员如下，我们用域运算符来得到容器相应的类型成员。由于我们不能改变元素的关键字因此pair的关键字部分是const的

• 当解引用关联容器的迭代器时，效果会与顺序容器稍有不同，我们得到的是容器的value_type的类型值。这对于set来说效果没什么差别，因为set的value_type和key_type相同，value即为key，但是对于map来说，map会返回一个pair，pair里才是我们想要的结果
• 由于说到关键字是const的，因此set的迭代器是const的
• 但是与顺序容器一样我们可以用begin和end得到关联容器想要的迭代器
• 我们通常不对关联容器使用泛型算法，因为容器的迭代器常常包含了const成分难以被需要修改元素的算法处理，容器由于是按照关键字排序的，所以对其采用泛型的只读算法如find效率也会很低
• 实际应用中我们使用容器自带的一些算法进行处理，例如关联容器自带的find
• 我们可以用成员函数insert或emplace来向关联容器插入元素，使用方法和顺序容器类似。但是对于map来说insert函数的返回值是一个pair类型，其第一个元素是一个迭代器，指向具有给定关键字的元素，第二个元素是bool值，false代表元素已经在容器中了，什么都不做，true代表已经进行了插入
• 对于无序容器来说即使容器查找到重复元素也会进行插入，因此无序容器的insert的返回值仅仅是一个迭代器，指向这个新插入的元素
• 关联容器同样用erase进行删除元素，但是关联容器提供了三个版本的erase函数，前两个版本和顺序容器的一致，是传入一个迭代器或者一对迭代器表示范围，第三个版本接受一个key_type参数，将会删除所有匹配了这个关键字的元素，然后返回删除掉的元素的数量，返回0时自然表示目标关键字不在容器中
• 我们可以用下标或at函数来访问容器的元素，参数是关键字，但是和顺序容器不同的是当关键字不在map中时，map会创建一个元素并插入进去，然后进行值初始化。相比之下如果用at来访问数据，则有参数检查，当关键字不在map中时会抛出out_of_range异常
• 由于下标操作会创建新的值，所以我们只能对非const的map进行下标操作
• 如果想要访问元素，对于不可重复关键字的容器直接用find即可，但是如果是可重复元素的容器，则关联容器有三种方法处理。
  • find和count。由于相同关键字的元素在容器中都是相邻储存的，所以可以先用find找到开始处的迭代器，然后用count查找出现了多少个相同关键字的元素，然后用一个简单的for循环计数遍历
  • lower_bound和upper_bound。这两个函数分别返回一个迭代器，lower_bound返回目标关键字的第一个匹配迭代器，upper_bound返回最后一个目标关键字的下一个元素迭代器。这正好构成了一对范围迭代器可以方便函数调用
  • equal_range。这是最直接方便的方法，它接收关键字后返回一个pair类型，pair中就是b点中得到的两个范围迭代器

11.4 无序容器

• 无序关联容器是C11才加入的新标准容器，本质是一个哈希桶，也就是用哈希函数和==运算符来组织元素，用来方便我们对一组没有明显顺序关系的元素提供一个可以在平均时间内进行检索的容器，很多时候用无序容器性能更好
• 无序容器的很多操作和有序容器相同，也就是很多时候可以相互取代，但是由于无序容器中元素储存的无序性，容器内容输出的时候元素间顺序自然与顺序容器不同
• 无序容器将哈希值相同的元素储存在同一个桶中，在桶中再采用顺序查找，然后在元素增多时看情况重整桶的元素以此来保持平均性能，因此自然也就有一批围绕着桶展开的成员函数可供操控。其中rehash能提高容器的性能但重组的时间代价很大

• 无序容器使用哈希函数来生成每个元素的哈希值，标准库为每个内置类型(包括指针)提供了hash模板，因此我们可以直接指定内置类型的无序容器。但是我们不能直接定义自定义类型的无序容器，需要提供我们自己的hash模板，这部分会在16章提到
• 简易地用的话，我们可以简单定义hash函数，对标准库的hash模板进行包装，并包装自己的==比较运算符来构造自己的无序容器，大概做法和有序容器自定义比较函数相似，示例如下

size_t hasher(string in) {
  return hash<int>()(in.size());
}

bool isEqual(const string& a, const string& b) {
  return a.size()==b.size();
}

int main() {
  // 自定义了string的无序容器
  // 用上面的两个函数使用string的长度重载int版本的hash生成新的hash值，并用长度进行比较
  unordered_set<string, decltype(hasher)*, decltype(isEqual)*> test;
  return 0;
}