第 11 章 关联容器
关联容器 associative-container
map
set
multimap
multiset
unordered_map
unordered_set
unordered_multimap
unordered_multiset
11.1 使用关联容器
map 通常称为关联数组 associative array。
11.2 关联容器概述
有序容器的关键字类型
需要定义 <，且该运算需要满足严格弱序 strict weak ordering。
11.2.3 pair 类型
pair 定义在 utility 头文件中。
11.3 关联容器操作
set<string>::value_type v1; // string
set<string>::key_type v2; // string
map<string, int>::value_type v3; // pair<const string, int>
map<string, int>::key_type v3; // string
map<string, int>::mapped_type v3; // int
set 没有 mapped_type。
11.3.1 关联容器迭代器
map<string, int> cnt;
auto map_it = cnt.begin();
*map_it; // 指向 pair<const string, int> 的引用
// map_it->first = "new key" // 错误，不能更改 key
++map_it->second; // 可以修改 value 的值
set 的迭代器时 const 的
set 虽然同时有 iterator 和 const_iterator 类型，但是都只能访问 set 中的元素。
关联容器和算法
通常不对关联容器使用泛型算法。
多数时候关联容器本身的算法比泛型算法更好比如 （find）。
关联容器更多地是作为源序列或者目标位置。可以调用 inserter 将一个插入器绑定到关联容器。
11.3.2 添加元素
检查 insert 的返回值
对于 set 和 map，insert 和 emplace 返回一个 pair。first 是插入的关键字的元素的迭代器，second 是 bool 表示是成功插入 （true） 还是已经存在 （false）。
对于 multiset 和 multimap 因为插入一定会成功，因此只返回迭代器。
11.3.3 删除元素
erase(key) 将返回删除元素的个数。
erase(it) 或 erase(b, e) 则返回被删除元素的下一个元素的迭代器。
11.3.4 map 的下标操作
c[k]; // k 不存在时会添加一个 key 为 k 的元素
c.at(k); // k 不存在时会抛出 out_of_range 异常
11.3.5 访问元素
c.find(k); // 指向等于 k 的第一个元素
c.count(k);
c.lower_bound(k);
c.upper_bound(k);
c.equal_range(k); // 返回一个迭代器 pair。k 不存在则返回一对 c.end()
11.4 无序容器
无序关联容器不适用比较算符，使用哈希函数 hash function 和关键字类型的 == 算符。
桶管理
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);
c.load_factor(); // 每个桶的平均元素数量，返回 float 值
c.max_load_factor(); // c 试图维护的平均桶大小
c.rehash(n); // 使 bucket_count >= n
c.reserve(n); // 使 c 可以保存 n 个元素且不必 rehash
无序容器对关键字类型的要求
size_t hasher(const A) { ... }
bool eq_op(const A &a, const A &b) { ... }
unordered_map<A, decltype(hasher)*, decltype(eq_op)*> ma;
Next: 《C++ Primer》 拾遗 第 12 章 动态内存