第11章 关联容器

1. 关联容器与顺序容器的根本不同：关联容器按关键字来保存和访问元素；顺序容器按位置保存和访问元素。
2. map是关键字-值对集合，关键字用于索引，值是与索引相关联的数据。
3. set是关键字集合，支持高效的关键字查询操作。
4. map和multimap定义在头文件map；set和multiset定义在头文件set；unordered_map、unordered_multimap定义在头文件unordered_map；unordered_set、unordered_multiset定义在头文件unordered_set。
5. multi前缀代表元素的关键字可以重复，unordered前缀代表无序关联容器。

11.1 使用关联容器

1. map中的元素是pair，first保存关键字，second保存对应的值。
2. 定义map需指定关键字和值的类型，定义set需指定关键字类型。

11.2 关联容器概述

1. 关联容器按关键字存储元素，故不支持顺序容器的位置相关的操作，如push_front、push_back等。
2. 关联容器不支持接受一个元素值和一个数量值的构造函数或插入操作。
3. 无序关联容器不支持>、>=、<、<=。
4. assign仅支持顺序容器，不支持关联容器。
5. 关联容器的迭代器都是双向迭代器。

11.2.1 定义关联容器

1. 定义map需指定关键字和值的类型，定义set只需指定关键字类型。
2. 关联容器可用同类型容器来初始化，或一个可转换的值范围初始化。

11.2.2 关键字类型的要求

1. 对于有序关联容器（map、multimap、set、multiset），关键字类型必须定义元素比较的方法，默认使用<运算符。
2. 有序关联容器的比较函数必须是严格弱序。<是严格弱序，<=不是严格弱序。
3. 两个关键字等价，即任何一个都不“小于”对方。
4. 严格弱序的比较函数F具备的基本性质：
   -- 若F(k1,k2)=true，则F(k2,k1)=false；
   -- 若F(k1,k2)=true, F(k2,k3)=true，则F(k1,k3)=ture；
   -- 若F(k1,k2)=false, F(k2,k1)=false，则k1=k2。若k1=k2,k2=k3，则k1=k3。
5. 可以使用严格弱序的自定义比较函数替代<运算符。

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}
multiset<Sales_data, decltype(compareIsbn) *> bookstore(compareIsbn);
multiset<Sales_data, bool (*)(const Sales_data &lhs, const Sales_data &rhs)> bookstore(compareIsbn);

11.2.3 pair类型

1. pair定义在头文件utility。
2. pair类似于容器，是一个用来生成特定类型的模板。一个pair保存两个public数据成员，分别是first和second。
3. map的元素是pair。
4. 比较pair：若 p1.first<p2.first，或者 !(p2.first<p1.first) && p1.second<p2.second，则p1<p2。若p1.first=p2.first && p1.second=p2.second，则p1=p2。
5. 在早期C++版本的函数中，不允许用花括号包围的初始化器来返回pair，必须显示构造返回值。

11.3 关联容器操作

11.3.1 关联容器迭代器

1. 关联容器迭代器指向类型为value_type的元素。
2. 对于map，value_type是pair<const key_type, mapped_type>，其first成员保存const的关键字，second成员保存值。
3. 对于set，value_type是const key_type。iteraroe与const_iterator都只能读取而不可修改set中的元素。
4. 使用迭代器遍历map、multimap、set、multiset时，是按关键字升序遍历。
5. 关联容器可用于只读算法；不宜对关联容器使用泛型搜索算法（如find等），因为关联容器中的元素可以直接通过关键字快速查找；不能将关联容器传递给修改或重排容器元素的算法，因为set的value_type是const key_type，map的value_type是pair<const key_type, mapped_type>，const不可修改。
6. 通常不对关联容器使用泛型算法。在实际编程中，若真要对关联容器使用泛型算法，则关联容器要么是一个源序列，要么是一个目的位置。

11.3.2 添加元素

1. 对于非multi的关联容器，插入一个元素前需先看其关键字是否存在。若关键字已存在，则什么也不做；若关键字不存在，则插入该元素。
2. map的元素类型是pair，添加元素时须构建pair对象。

11.3.3 删除元素

11.3.4 map的下标操作

1. 只有map和unordered_map支持下标运算符和at函数，因为set只有关键字，无对应的值；multimap和unodered_multimap一个关键字可能对应多个值。
2. 只能对非const的map和unordered_map使用下标操作，因为下标运算符可能会插入一个新元素。
3. 通常情况，迭代器解引用返回的类型与下标运算符返回的类型一样，但map不同：解引用一个map迭代器得到一个value_type对象，对map进行下标操作得到一个mapped_type对象。
4. 下标运算符返回的结果是左值。

11.3.5 访问元素

1. lower_bound和upper_bound不适用于unordered的关联容器。
2. 若k在c中，lower_bound返回的迭代器指向第一个具有给定关键字的元素，upper_bound返回的迭代器指向最后一个匹配关键字的元素之后的位置；若k不在c中，lower_bound和upper_bound返回相等的迭代器——指向一个不影响排序的关键字插入位置
3. equal_range返回一个pair对象，[first, second)表示关键字等于k的元素的范围，若k在c中，first指向第一个匹配关键字的元素，second指向最后一个匹配关键字的元素之后的位置；若k不在c中，first=second，都指向关键字可以插入的位置。

11.3.6 一个单词转换的map

1. c[key] = value 与 c.insert({key,value}) 的区别：对于multi的关联容器插入多个关键字相同的元素，前者取最后一次插入的元素，后者取第一次插入的元素。

11.4 无序容器

1. 有序关联容器通过比较运算符组织元素；无序关联容器使用哈希函数和==运算符组织元素。
2. 若元素没有明显的序关系，或维护元素的序的代价高昂，则建议使用无序容器。
3. 通常可用一个无序容器替换对应的有序容器，反之亦然。由于存储顺序的不同，两者的输出通常不同。
4. 无序容器是桶集合，每个桶可保存零个或多个元素。访问元素时，容器先计算元素的哈希值，再搜索哈希值对应的桶。
5. 若关键字是内置类型（包括指针类型）、string和智能指针类型，则可以直接定义对应类型的无序容器。
6. 不能直接定义关键字类型是自定义类型的无序容器。对于自定义类型，hash模板不能直接使用，必须提供自定义的hash模板版本。
7. 在无序或有序容器中，具有相同关键字的元素都是相邻存储的。

// 使用一个标准库hash类型对象来计算isbn成员的哈希值，该hash类型建立在string类型之上
size_t hasher(const Sales_data &sd)
{
    return hash<string>()(sd.isbn());
}
// 通过比较isbn来比较两个Sales_data
bool eqOp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() == rhs.isbn();
}
// 别名声明
using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>
// 定义自定义类型的无序容器
// 参数：桶大小，哈希函数指针，相等性判断运算符指针
SD_multiset bookstores(42, hasher, eqOp)

// 若自定义类型已定义==运算符，则可以只重载哈希函数
unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);