第十一章 关联容器

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

关联容器类型：

关联容器概述

定义关联容器

• 需要指定元素类型。
• 列表初始化：
  • map：map<string, int> word_count = {{"a", 1}, {"b", 2}};
  • set：set<string> exclude = {"the", "a"};

关键字类型的要求

• 对于有序容器，关键字类型必须定义元素比较的方法。默认是<。
• 如果想传递一个比较的函数，可以这样定义：multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

pair

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

pair 的操作：

关联容器操作

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

关联容器迭代器

• 解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。
• set的迭代器是const的。
• 遍历关联容器：使用begin和end，遍历map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

添加元素

关联容器insert操作：

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

删除元素

从关联容器中删除元素：

下标操作

map和unordered_map的下标操作：

查找元素

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

• lower_bound和upper_bound不适用于无序容器。
• 下标和at操作只适用于非const的map和unordered_map。

无序容器

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

无序容器管理操作：