引入

继上文 STL序列式容器使用注意、概念总结继续总结关联式容器的概念以及一些使用事项。

关联式容器与容器适配器

STL 中的关联式底层容器：RB tree, hash table，可以作为其他容器的底层结构。

1.RB tree

RB tree 红黑树这玩意儿可是重量级的，书中从基本的树概念讲起，到二叉树、BST、AVL，然后才到 RB tree。简单来说，AVL 是高度极其平衡的 BST，任意节点的左右子树高度差不超过 1 。那为什么还要 RB tree 呢？因为实践证明 AVL 为了保持其平衡性需要经常进行旋转操作，影响性能。而 RB tree 减轻了对平衡的要求，根据它的定义（我实在没能背下来，也不知道发明它的人是怎么想的，牛B），任意节点的左右子树高度差有可能超过 1，由此带来的好处是不那么频繁的旋转操作。在实际应用中，RB tree 的表现比 AVL 更好。
总结起来 RB tree 就是一个虽然不是严格平衡但也非常平衡的二叉搜索树，插入、删除、查找等操作都能保持在 \(O(log \space n)\) 的时间复杂度。
它的迭代器类型为 Bidirectional Iterator 双向迭代器。

2.hash table

真正的哈希表，目的是使得各项操作如插入、删除、查找的均摊时间开销是 \(O(1)\)。
哈希函数：将一个元素映射到一个“大小可接受的索引”。随着 C++ 标准的发展，现在几乎所有内置类型都自带了哈希函数，我遇到过 pair 和自定义类型需要自定义哈希函数（自定义方法见下文 unordered_map ）。
哈希碰撞：哈希函数可能将不同的元素映射到相同的位置。
哈希碰撞的解决方法：
负载系数：元素个数除以表格大小（表格是存放 value 的地方）。除了拉链法，其他方法的负载系数都在 0-1 之间。
STL 采用拉链法实现，自带的 vector 和自维护的 list（没有使用已经实现的双向循环链表 list）。相信大家都用过这种方法，它的一大局限是映射到同一个位置的元素过多，链表会变得很长，此时查找等操作的时间开销就很大了。STL 实现的哈希表有一个表格重整的机制，专门解决这种情况。
采用拉链法实现哈希表，表格的大小一般设置为质数以减少碰撞，STL 内置了 28 个质数。
它的迭代器 Forward Iterator 前向迭代器，只支持自增操作（++）。

以某种容器作为底层结构，改变其接口，使之符合某种特性。关联式容器适配器有：

以 RB tree 为底层结构的 map 和 set。
以 hash table 为底层结构的 unordered_map 和 unordered_set 。

这 4 种容器适配器都不允许 key 重复，它们都有对应的允许 key 重复的版本：multimap, multiset, unordered_multimap 和 unordered_multiset。

这里不讲实现细节，讲讲一些注意事项和使用方法。

通过下标访问 map 时，一定要确保 key 已存在，否则将插入一个新建的 key-value 对，key 是指定的，value 是类型的默认值，如下代码所示：
```
map<int, int> m;
cout << boolalpha << (m.find(2) == m.end()) << endl;    // true
if (m[2] > 0) { // do something }    // if 里潜在地插入了 m[2] = 0
cout << boolalpha << (m.find(2) == m.end()) << endl;    // false
```
除非你本身需要这种特点，否则要特别注意喔。
set 集合，key 就是 value，由于 key 不可变，所以我们不能通过 set 的迭代器更改其元素值，其迭代器是一种常量迭代器。
map 和 set 会对插入的元素进行排序，因为底层的 RB tree 也是 BST，对 BST 进行中序遍历即可得到有序序列。
正如它们的名字所说的那样，unordered_map 和 unordered_set 不会对插入的元素排序。

如何为 unordered_map 自定义哈希函数和 key 比较函数呢？下面给出两个示例，一个针对自定义类类型，另一个针对 pair。核心思想是重载函数调用符。

一、为 pair 自定义哈希函数和 key 比较函数

其实 pair 本身重载了比较函数，不自己定义也可以。

#include <unordered_map>
using namespace std;

// 哈希函数
struct MyKeyHash
{
    size_t operator()(const pair<int, int>& p) const {
        // 第一种写法里第一个()是实例化一个hash<int>类对象
        // 第二个()是像函数一样使用该对象
        // 因为它重载了函数调用符
        // return hash<int>()(p.first) ^ hash<int>()(p.second);    // 这第二种写法C++11开始支持
    // {}表示列表初始化
    // 类似vector&lt;int&gt;{1, 2, 3}
    return hash&lt;int&gt;{}(p.first) ^ hash&lt;int&gt;{}(p.second);    // 异或一下
}};

// key比较函数
struct MyKeyEqual
{
    bool operator() (const pair<int, int>& key1, const pair<int, int>& key2) const {
        return key1.first == key2.first && key1.second == key2.second;
    }
};

int main()
{
    unordered_map<pair<int, int>, int, MyKeyHash, MyKeyEqual> um;
    // unordered_map<pair<int, int>, int, MyKeyHash> um;    // 其实pair本身重载了比较函数，不自己定义也可以。
    um.insert(pair<pair<int, int>, int>(pair<int, int>(1, 1), 2));    // 这句长到头皮发麻
    return 0;
}

哈希函数通过异或实现，网上说这种方法在数据量较大时发生碰撞的概率很大，导致性能很差。有位大佬的博客说他在《C++ 标准库》第二版这本书里找到了正解，用过都说好的哈希函数，链接在这：C++ pair 作为 unordered_map unordered_set 的键值。

二、为自定义类类型自定义哈希函数和 key 比较函数

#include <unordered_map>
#include <string>
using namespace std;

// 自定义一个Person类型
class Person {
private:
    int m_id;         // 身份证
    int m_age;        // 年龄
    string m_name;    // 姓名
    // 其他成员
public:
    int getId() const { return m_id; }
    int getAge() const { return m_age; }
    string getName() const { return m_name; }Person() = default;
Person(int id, int age, string name): m_id(id), m_age(age), m_name(name) {}};

struct MyKeyHash
{
    size_t operator()(const Person& p) const {
        // 这里只使用一个人的年龄和姓名进行哈希映射
        // return hash<int>{}(p.getAge()) ^ hash<string>{}(p.getName());
        return hash<int>()(p.getAge()) ^ hash<string>()(p.getName());
    }
};

struct MyKeyEqual
{
    bool operator() (const Person& p1, const Person& p2) const {
        // 当且仅当两个人的身证份一致时才认为是同一个人
        return p1.getId() == p2.getId();
    }
};

int main()
{
    unordered_map<Person, int, MyKeyHash, MyKeyEqual> um;
    um.insert(pair<Person, int>(Person(), 1));
    return 0;
}