前言

经历了相当漫长的历程，终于将 STL 的序列式容器基本分析完毕，接下来将进入关联式容器的分析。相比于序列式容器，关联式容器中真正需要实现的底层容器更少，仅有两个。但是，但是，这两位可都是重量级：红黑树与哈希表。它们的复杂程度要远超之前的 vector、list 以及 deque，并且红黑树不仅复杂还让人及其费解，用一个词来形容就是又臭又长，理解与实现起来都十分困难。但这已经是我们实现 STL 之路上的倒数第二个阻碍了，翻过这座山，我们就是冠军。

标准的 STL 关联式容器分为 set（集合）和map（映射表）两大类，以及这两大类的衍生体 multiset（多键集合）和 multimap（多键映射表）。这些容器的底层机制均以 RB-tree （红黑树）完成。RB-tree 也是一个独立容器，但并不开放给外界使用。
此外，SGI STL 还提供了一个不在标准规格之列的关联式容器: hash table（散列表），以及以此 hashtable 为底层机制而完成的 hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_multimap（散列多键映射表）。
所谓关联式容器，观念上类似关联式数据库（实际上则简单许多）：每笔数据（每个元素）都有一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时、容器内部结构（可能是RB-tree，也可能是 hash-table）便依照其键值大小，以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾（只有最大元素和最小元素），所以不会有所谓 push_back() 、 push_front() 、pop_back()、 pop_front()、 begin()、end() 这样的操作行为。
———— 《STL源码剖析》侯捷

本节将会介绍实现红黑树之前的预备知识。

预备知识

二叉树 & 二叉搜索树 & AVL 树 & 红黑树

想要彻底理解红黑树，就要明白这个复杂的概念是如何提出的，让我们从头开始。

二叉树（binary tree），是指树中的每个节点最多只有两个子节点的树。当然，二叉树本身似乎没什么用，我们平时说的二叉树基本上都是指二叉查找树，或者叫有序二叉树、二叉搜索树、二叉排序树。

二叉搜索树（BST，binary search tree），就是在二叉树的基础上增加有序性，有了有序性，我们就可以使用二叉树来快速的查找、删除、插入元素了。例如：递归定义这样一种树，它的左子树的所有值均小于根节点的值，右子树的所有值均大于根节点的值，就形成了我们常说的二叉搜索树。这样的树查找元素的平均时间复杂度为 O(logn)，查找起来类似于二分。

但是，二叉搜索树有一个非常严重的问题，那就是当持续插入有序元素时，其结构会退化成链表。此时，查找元素的复杂度便退化成了 O(n) 而不是 O(logn)，所以，在极限情况下，二叉查找树的时间复杂度是非常差的。

为此，需要一能够自己调整结构的二叉树，这种手段就叫做平衡，这种可以自平衡的树就叫做平衡树。平衡树一直只是一个概念，直到1962年才由两个苏联人发明了第一种平衡树 —— AVL树。

AVL树（由发明者Adelson-Velsky 和 Landis 的首字母缩写命名）。AVL 树可以通过左旋和右旋的方式来维持自身的平衡性，使得任意节点的两个子树的高度差不超过 1，也就是说可以一直维持良好的查找性质。

虽然 AVL 树很神奇也可以维持良好的查找性质，但有两个问题：

  1. 当节点数多的时候，判断是否平衡非常麻烦，因为要逐节点判断左右子树的深度关系。
  2. 频繁地插入与删除节点时，效率很低，因为两个子树的高度差不超过 1 这一条件很容易被打破，因此会频繁地调整树的结构。

综上，AVL 由于严苛的平衡条件，使得其在节点数量过多与频繁地插入删除节点时的性能不尽人意。因此，后续又衍生出了诸如 2-3 树、2-3-4 树、B 树等一系列的改进版本，关于这些树这里就不再细说，值得一提的是 2-3-4 树与红黑树的结构十分接近，甚至可以说 2-3-4 树就是红黑树，关于这部分可以参考视频：红黑树。

红黑树由以下的五条性质定义：

  1. 节点是红色或黑色。
  2. 根是黑色。（根据OI_WIKI，这一条不一定需要满足）
  3. 所有叶子都是黑色（叶子是 NIL 节点）。
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这样较为宽松的定义使得红黑树的平衡条件不会像 AVL 树那样严苛，是一种弱平衡的搜索树，即一颗子树的高度不会超过另一棵的二倍（左子树全为黑色节点，右子树全为黑红相间），这样的性质使得红黑树既不会像二叉搜索树那样退化为单链表也不会像 AVL 树那样有过于严苛的平衡要求。参考视频

但经验表明，红黑树的平均搜索效率却能几乎与 AVL 树相当。 ———— 《STL源码剖析》侯捷

作为代价，由于多了一个颜色的性质，红黑树的调整、插入与删除都变得异常复杂，这部分可以参考我的博客 红黑树寄录，理解了这些操作，才能够理解与实现 STL 中的 rb-tree。

pair

关联式容器实现诸如 map、multimap 是依靠底层的 pair 容器的，这个容器十分简单，只是将两个元素打包，使用 pair.first 与 pair.second 即可获得内部的元素，对于 map 而言即为 pair<key, value>，下面就来看看 pair 的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// ========================== pair ========================== //
// pair: 一个模板结构体，用于存储一对值

template <class T1, class T2>
struct pair {
    
    typedef T1  first_type;
    typedef T2  second_type;

    // 成员变量
    first_type  first;
    second_type second;

    // 默认构造
    template <class U1 = T1, class U2 = T2, 
        typename std::enable_if<std::is_default_constructible<U1>::value &&
        std::is_default_constructible<U2>::value, void>::type>
        constexpr pair() : first(), second() {}

    // 其他构造 ...

    // 使用默认的实现
    pair(const pair& rhs) = default;
    pair(pair&& rhs) = default;

    // copy assign
    pair& operator=(const pair& rhs) {
        if (this != &rhs) {
            first = rhs.first;
            second = rhs.second;
        }
        return *this;
    }

    // move assign
    pair& operator=(pair&& rhs) {
        if (this != &rhs) {
            first = tinystl::move(rhs.first);
            second = tinystl::move(rhs.second);
        }
        return *this;
    }

    // copy assign for pair with different types
    template <class U1, class U2>
    pair& operator=(const pair<U1, U2>& rhs) {
        first = rhs.first;
        second = rhs.second;
        return *this;
    }

    // move assign for pair with different types
    template <class U1, class U2>
    pair& operator=(pair<U1, U2>&& rhs) {
        first = tinystl::forward<U1>(rhs.first);
        second = tinystl::forward<U2>(rhs.second);
        return *this;
    }

    ~pair() = default;

    // swap

    void swap(pair& rhs) {
        if (this != &rhs) {
            tinystl::swap(first, rhs.first);
            tinystl::swap(second, rhs.second);
        }
    }

};


// ========================== 重载比较运算符 ========================== //

template <class T1, class T2>
bool operator==(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return lhs.first == rhs.first && lhs.second == rhs.second;
}

template <class T1, class T2>
bool operator<(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return (lhs.first < rhs.first) || ((lhs.first == rhs.first) && (lhs.second < rhs.second));
}

template <class T1, class T2>
bool operator!=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(lhs == rhs);
}

template <class T1, class T2>
bool operator>(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return rhs < lhs;
}

template <class T1, class T2>
bool operator<=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(rhs < lhs);
}

template <class T1, class T2>
bool operator>=(const pair<T1, T2>& lhs, const pair<T1, T2>& rhs) {
    return !(lhs < rhs);
}

// 重载 tinystl 的 swap

template <class T1, class T2>
void swap(pair<T1, T2>& lhs, pair<T1, T2>& rhs) {
    lhs.swap(rhs);
}

// ========================== make_pair ========================== //
// make_pair: 用于生成一个 pair 对象

template <class T1, class T2>
pair<T1, T2> make_pair(T1&& first, T2&& second) {
    return pair<T1, T2>(tinystl::forward<T1>(first), tinystl::forward<T2>(second));
}

pair 的结构十分简单，只是封装了两个元素并提供了一些运算符的重载，其中全局函数 make_pair(T1&& first, T2&& second) 可以生成一个 pair 对象，方便使用。