关联式容器

关联式容器的每个数据都有一个 key 和一个 value，当元素被插入到关联式容器时，容器的内部结构（可能时 RB-tree，也可可能时 hash-table）会根据键值的大小，以某种特定规则将这个数据放置在适当的位置。关联容器没有所谓的头，尾，因此不会有类似于 push_back, push_front, pop_back(), pop_front(), begin, end 之类的函数。一般来说，关联式容器的内部是有个平衡二叉树（包括AVL-tree, RB-tree, AA-tree），其中在STL中使用最多的就是 RB-tree。

1. 数据结构——树

1. 二叉搜索树（BST)

二叉搜索树中任何节点的键值一定大于其左子树的每一个节点的键值，并小于右子树的每一个节点的键值。因此从跟节点一种往左走可以得到最小的键值，一直往右走可以得到最大的键值。
二叉搜索树的插入操作：从跟节点开始，遇键值较大者就向左，遇键值小者就向右，一直到尾端，即为插入点。
二叉搜索树的删除操作：想要删除节点A可以分为两种情况，如果A只有一个子节点，可以直接将A的子节点连接到A的父节点，并将A删除即可；如果A有两个子节点，就用右子树的最小节点（从右子节点开始一直往左走即可获得）取代A即可。

2. 平衡二叉搜索树（balanced binary search tree）

二叉搜索树有一个缺点就是当输入数据不够随机（比如说已经有序），二叉搜索树就可能失去平衡（比如退化成单链表），造成搜索效率低下。这里的平衡的意思就是没有任何一个节点深度过大。不同的平衡条件有不同的搜索效率，AVL-tree、RB-tree、AA-tree都可以实现平衡二叉树，它们一般都比普通的二叉搜索树复杂，因此插入节点喝删除节点的平均时间也比较长，但是可以避免高度不平衡的情况，访问元素的时间平均也比较少。

3. AVL-tree（Adelson-Velskii-Landis tree）

AVL-tree 是一种加上了额外的平衡条件的二叉搜索树，也叫二叉平衡搜索树，平衡条件的建立是为了确保整棵树的深度为 O(logN)。一般来说，最严格的平衡条件就是左右子树有着相同的高度（这也太难以实现了），因此 AVL-tree 退而求其次，要求任何节点的左右子树高度相差最多1。当一个节点插入到 AVL-tree ，使得平衡的状态被打破，就意味着某个节点X的左右子树高度差等于2，因此插入点和X的位置可以分为如下四种关系：

插入点位于X的左子节点的左子树——左左
插入点位于X的左子节点的右子树——左右
插入点位于X的右子节点的左子树——右左
插入点位于X的右子节点的右子树——右右
其中，情况1、4互为对称，称为外侧插入，可以使用单旋转操作；情况2、3互为对称，称为内侧插入，可以使用双旋转操作。
单旋转
在外侧插入的状态下，也就是出现“左左”或者“右右”的情况下，可以使用单旋转来修正不平衡的状态：

双旋转
在内侧插入的状态下，也就是出现“左右”或者“右左”的情况下，可以使用双旋转来修正不平衡的状态，所谓双旋转其实就是由两次单旋转合并而成，只要代码实现好左旋右旋的单旋转即可。

4. RB-tree（红黑树）

RB-tree 是另一种平衡二叉搜索树，平衡条件和 AVL-tree 有所不同，牺牲了部分平衡性（ RB-tree 某些节点的左右子树高度差值可能大于1），但是同样使用单旋转、双旋转操作来修正树使其满足平衡条件，整体性能优于 AVL-tree。RB-tree 是 STL 中广泛使用的数据结构，除了要满足二叉搜索树的定义之外，还需要满足以下几个规则：

每个节点不是红色就是褐色；
跟节点是黑色；
如果节点是红色，那么其子节点必然是黑色；
任一节点到叶节点的任何路径，所含的黑节点数必须相同；
每个叶子节点都是黑色的空节点。

根据规则4：新节点必须为红
根据规则3：新节点的父节点必须是黑

有了这些规则的限制，保证了 RB-tree 的自平衡，红黑色从根节点到叶子的最长路径不会超过最短路径的两倍，这是因为最短的路径一定是全黑节点，而最长路径一定是红黑相间的节点，而要保持规则4，那么最长路径就刚好是最短路径的两倍。

RB-tree 的实现代码在 stl_tree.h 中：

RB-tree 节点设计

enum _Rb_tree_color { _S_red = false, _S_black = true }; // false是红色，true 是黑色

struct _Rb_tree_node_base {
  typedef _Rb_tree_node_base* _Base_ptr;
  typedef const _Rb_tree_node_base* _Const_Base_ptr;

  _Rb_tree_color	_M_color; // 颜色
  _Base_ptr		_M_parent; // 指向父节点, RB-tree 的很多操作要知道父节点
  _Base_ptr		_M_left; // 左子节点
  _Base_ptr		_M_right; // 右子节点

  // 二叉搜索树得特性,一直向左走可以获得最小值
  static _Base_ptr _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  static _Const_Base_ptr _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  // 一直向右走可以获得最大值
  static _Base_ptr _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }

  static _Const_Base_ptr _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};

template<typename _Val>
struct _Rb_tree_node : public _Rb_tree_node_base {
  typedef _Rb_tree_node<_Val>* _Link_type;
  __gnu_cxx::__aligned_membuf<_Val> _M_storage; // 节点存储数据

  _Val* _M_valptr() { return _M_storage._M_ptr(); }
  const _Val* _M_valptr() const { return _M_storage._M_ptr(); }
};

RB-tree 迭代器
迭代器的实现关键在运算符 operator++、operator– 的实现，按照一般意义，在 RB-tree 中，这两个运算符分别用来获取当前节点的后一个节点和前一个节点，也就是当前节点后最小节点以及当前节点前最大节点。
为了实现这两个运算符的重载，STL写了两个查找的函数 increment() 和 decrement()。

void increment() {
    if ( node->_M_right != 0 ) { //        情况1：当前节点有右子节点
        node = node->_M_right;  //        就向右走，然后一直向左走
        while ( node->_M_left != 0 )
            node = node->_M_left;
    }
    else {                             //  情况2：当前节点没有右子节点
        _Base_ptr y = node->_M_parent; //  找到父节点
        while ( node == y->_M_right ) { // 如果当前节点本来就是右子节点
            node = y;                   // 那么就一直向上找，直到node不为右节点
            y = y->_M_parent;          
        }
        if ( node->_M_right != y ) //  一般来说此时的y就是结果，但是如果求得是
            node = y;              // 跟节点得下一个节点，恰巧跟节点没有右子节
                                   // 点，那么node才是结果
    }
}

void decrement() {
    if ( node->_Rb_tree_color == _S_red && node->_M_parent->_M_parent == node )
        node = node->_M_right; // 如果是红节点兵器父节点得父节点是自己，也就是node是header的时候
    else if ( node->_M_left != 0 ) {
        _Base_ptr y = node->_M_left; // 如果当前节点有左子树，那么就找左子节点的最大
        while ( y->_M_right != 0 ) {
            y = y->_M_right;
        }
        node = y;
    }
    else {
        _Base_ptr y = node->_M_parent; // 不是跟节点，也没有左子树，找到父节点
        while ( node == y->_M_left ) { // 一直往上走，直到当前节点不是左节点
            node = y;
            y = y->_M_parent;
        }
        node = y; // 此时父节点就是结果
    }
}

template<typename _Tp>
    struct _Rb_tree_iterator
    {
      typedef _Tp  value_type;
      typedef _Tp& reference;
      typedef _Tp* pointer;

      typedef bidirectional_iterator_tag iterator_category;
      typedef ptrdiff_t		  difference_type;

      typedef _Rb_tree_iterator<_Tp>	_Self;
      typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
      typedef _Rb_tree_node<_Tp>*	   _Link_type;

      _Rb_tree_iterator() _GLIBCXX_NOEXCEPT : _M_node() { }

      explicit _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
      : _M_node(__x) { }

      reference operator*() const _GLIBCXX_NOEXCEPT
      { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }

      pointer operator->() const _GLIBCXX_NOEXCEPT
      { return static_cast<_Link_type> (_M_node)->_M_valptr(); }

      _Self& operator++() _GLIBCXX_NOEXCEPT {
        _M_node = _Rb_tree_increment(_M_node);
        return *this;
      }

      _Self operator++(int) _GLIBCXX_NOEXCEPT {
        _Self __tmp = *this;
        _M_node = _Rb_tree_increment(_M_node);
        return __tmp;
      }

      _Self& operator--() _GLIBCXX_NOEXCEPT {
        _M_node = _Rb_tree_decrement(_M_node);
        return *this;
      }

      _Self operator--(int) _GLIBCXX_NOEXCEPT {
        _Self __tmp = *this;
        _M_node = _Rb_tree_decrement(_M_node);
        return __tmp;
      }

      bool operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
      { return _M_node == __x._M_node; }

      bool operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
      { return _M_node != __x._M_node; }

      _Base_ptr _M_node; // 指向  RB-tree 节点
  };

RB-tree 数据结构
为了便于处理 RB-tree 代码中的边界条件，使用两个标记节点 header 和 nil 来充当哨兵，拥有和普通节点一样的属性，header 颜色是红色，父指针指向跟节点，左指针指向最小节点，右指针指向最大节点。之后每次插入新节点不仅要按照 RB-tree 的规则作调整，而且维护 header 节点的正确性。同时所有的叶节点的左右子节点都指向节点 nil，用于在遍历时的结束标记。
header 和 root 互为对方的父节点：

RB-tree 的构造和内存管理
RB-tree 元素操作

元素插入操作

insert_equal()：插入新值，允许键值重复, 返回一个迭代器，指向新节点

 template<typename _Arg>
 typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 _M_insert_equal(_Arg&& __v) {
   pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_equal_pos(_KeyOfValue()(__v));
   _Alloc_node __an(*this);
   return _M_insert_(__res.first, __res.second,
_GLIBCXX_FORWARD(_Arg, __v), __an);
 }

- insert_unique()：插入新值，不允许重复，返回一个pair，第一个是 RB-tree 迭代器，第二表示插入是否成功

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
template <class Key, class Value, class KeyOfValue, Class Compare, class Alloc>
pair<typename _Rb_tree<Key,  Value, KeyOfValue, Compare, Alloc>::iterator, bool>
_Rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::

#if __cplusplus >= 201103L
    _M_insert_uniuque(_Arg&& v)
#else
    _M_insert_unique(const Value& v)
#endif
{
    link_type y = header;
    link_type x = root(); // 从跟节点开始
    bool comp = true;
    while ( x != 0 ) {
        y = x;
        comp = key_compare(KeyOfValue()(v), key(x)); // v 小于当前节点的键值嘛？
        x = comp ? left(x) : right(x);            // 遇到大的往左走，遇到小的往右走
    }
    // 离开while之后，y就是要插入位置的父节点，也就是新值是y的子节点

    iterator j = iterator(y);
    if ( comp ) { // 如果离开 while 的时候是true，也就是表示遇到大的，应该插入到左变
        if ( j == begin() ) // 如果插入点的父节点是最左节点
            // 直接插入
            return pair<iterator, bool>(__insert(x, y, v), true);
        else
            --j; // 调整j，继续测试？？？
    }

    if ( key_compare(key(j.node), KeyOfVAlue()(v)) ) { // 新键值不与已有键值重复
        return pair<interator, bool>(__insert(x, y, v), true);
    }

    // 至此，树种一定已经有了重复键值，插入失败
    return pair<iterator, bool>(j, false);
}


- `__insert()` 真正的插入操作

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
template <class Key, class Value, class KeyOfValue, Class Compare, class Alloc>
pair<typename _Rb_tree<Key,  Value, KeyOfValue, Compare, Alloc>::iterator, bool>
_Rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::
__insert(base_ptr x_, base_ptr y_, const Value& v) {
    // x_为新值插入点，y_为新值插入点的父节点，v为新值
    link_type x = (link_type)x_;
    link_type y = (link_type)y_;
    link_type z;

    if ( y == header || x != 0 || key_compare(KeyOfValue()(v), key(y)) ) { //插入到左边
        z = create_node(v); // 创建一个节点
        left(y) = z; // 当y就是header时， leftmost() = z
        if ( y == header ) { // 如果 y 就是 header
            root() = z; // 
            rightmost() = z;
        }
        else if ( y == leftmost() )  // y 是最左节点
            leftmost() = z;          // 维护 leftmost(), 使其永远指向最左节点
    }
    else {
        z = create_node(v);
        right(y) = z;           // 令新节点为插入点之父的右节点
        if ( y == rightmost() ) // 如果插入点之父已经是最右，那么此时新节点才是最右
            rightmost() = z;
    }
    parent(z) = y;
    left(z) = 0;
    right(z) = 0;

    // 设定颜色并调整
    __rb_tree_rebalance(z, header->parent);
    ++node_count; // 节点数量
    return iterator(z);
}


- `__rb_tree_rebalance()` 旋转以及改变颜色操作
每次插入操作之后，都要作出调整，使得树满足 RB-tree 的要求。

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
inline void __rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base*& root) {
    x->color = __rb_tree_red; // 新节点必然是红色，规则4
    while ( x != root && x->parent->color == __rb_tree_red ) { 父节点为红
        if ( x->parent == x->parent->parent->left) { // 父节点是祖父节点的左孩子
            __rb_tree_node_base *y = x->parent-parent->right; // 令y为父节点的兄弟节点
            if ( y && y->color == __rb_tree_red ) { // 伯父节点存在而且是红色
                x->parent->color = __rb_tree_black; // 更改父节点为黑色
                y->color = __rb_tree_black          // 更改伯父节点也为黑色
                x->parent->parent->color = __rb_tree_red; // 祖父节点改为红
                x = x->parent->parent;
            }
            else { // 没有伯父节点或者伯父节点是黑色
                if ( x == x->parent->right ) { // 新节点是父节点的右子节点
                    x = x->parent;
                    __rb_tree_rotate_left(x, root); // 左旋一次
                }
                x-parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_right(x->parent->parent, root); // 右旋一次
            }

        }
        else { // 父节点是祖父节点的右孩子
            __rb_tree_node_base* y = x->parent->parent->left; // y 为伯父节点
            if ( y && y->color == __rb_tree_red ) { // 伯父节点存在而且是红色
                x->parent->color = __rb_tree_black;
                y->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                x = x->parent->parent; // 继续向上查找
            }
            else { // 无伯父节点或者伯父节点是黑色
                if ( x == x->parent->left ) { // 如果新节点是父节点的左孩子
                    x = x->parent;
                    __rb_tree_rotate_right(x, root); // 右旋一次
                }
                x->parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_left(x->parent->parent, root);
            }
        }
    } // end while 
    root->color = __rb_tree_black; // 跟节点是黑色
}


- `__rb_tree_rotate_left()`和`_rb_tree_rotate_right()` 旋转操作
新节点必然是红色节点，如果此时父节点也是红色，那么就违反了 RB-tree 的规则，可能需要做出旋转

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
// x 为旋转点，root为根
inline void __rb_tree_rotate_left(__rb_tree_node_base* x, __rb_tree_node_base*& root) {
    __rb_tree_node_base *y = x->right;
    x->right = y->left;
    if ( y->left != 0 ) {
        y->left->parent = x;
    }
    y->parent = x->parent;

    if ( x == root ) {
        root = y;
    }
    else if ( x == x->parent->left ) {
        x->parent->left = y;
    }
    else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

inline void __rb_tree_rotate_right(__rb_tree_node_base *x, __rb_tree_node_base*& root) {
    __rb_tree_node_base *y = x->left;
    x->left = y->right;
    if ( y->right != 0 )
        y->right->parent = x;
    y->parent = x->parent;

    if  ( x == root )
        root = y;
    else if ( x == x->parent->right )
        x->parent->right = y;
    else 
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}


其实到了这里，我仅仅是直到要通过改变颜色，旋转来调整树，而不知道具体是怎么改变颜色的，也不知道具体是怎么旋转的！
- find() 搜索元素
查找元素是 RB-tree 的拿手项目

1
2
3
4
5
6
7
8
9
10
11
12
13
14

iterator find(const Key& k) {
    link_type y = header;
    link_type x = root();
    while ( x != 0 ) {
        if ( !key_compare(key(x), k) ) { // x键值大于k，往左走
            y = x, x = left(x);
        }
        else // x键值小于k，往右走
            x = right(x);
    }
    iterator j = iterator(y);
    return ( j == end() || key_compare(k, key(j.node))) ? end() : j;
}

2. set

set 中的所有元素会根据键值自动排序，不允许有相同的键值。set的元素值就是其键值，键值关系到 set 元素的排列规则，不可以通过 set 的迭代器改变元素值，在 set 的源代码中，将 set::iterator 定义为底层的 RB-tree 的 const_iterator ，无法写入。当 set 的元素增加（insert）或者减少（erase）之后，和 list 类似的，之前的迭代器还可以继续使用。set 开放的各种接口，事实上都是由 RB-tree 实现的，因此几乎所有的 set 操作都是调用了 RB-tree 的操作而已。set 的一些源代码如下：

// set 默认是升序，使用内存分配器 std::allocator
template<typename _Key, typename _Compare = std::less<_Key>, typename _Alloc = std::allocator<_Key> >
class set {
public:
    /// Public typedefs.
    typedef _Key     key_type;
    typedef _Key     value_type;
    typedef _Compare key_compare;
    typedef _Compare value_compare;
    typedef _Alloc   allocator_type;

private:
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<_Key>::other _Key_alloc_type;

    typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
           key_compare, _Key_alloc_type> _Rep_type;
    _Rep_type _M_t;  // 底层使用 RB-tree 实现 set
    typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;

public:
    // default constructor
    set() = default;
    // 使用比较器,空 set
    explicit set(const _Compare& __comp, const allocator_type &__a = allocator_type())
    : _M_t(__comp, _Key_alloc_type(__a)) { }
    
    // 接受一对迭代器,调用 RB-tree 的 insert_unique()
    // multiset 才会调用 RB-tree 的 insert_equal()
    template<typename _InputIterator>
    set(_InputIterator __first, _InputIterator __last) : _M_t() {
        _M_t._M.insert_unique(__first, __last);
    }
    // 接受一对迭代器,比较运算子,内存分配器 
    template<typename _InputIterator>
    set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
        const allocator_type& __a = allocator_type())
    : _M_t(_comp, _Key_allo_type(__a)) {
        _M_t._M_insert_unique(__first, __last);
    }
    // copy constructor
    set(const set&) = default;
    // move constructor
    set(set&&) = default;
    // 提供一个 initializer_list
    set(initializer_list<value_type> __l, const _Compare& __comp = _Compare(),
        const allocator_type& __a = allocator_type())
    : _M_t(__comp, _Key_alloc_type(__a)) {
        _M_t._M_insert_unique(__l.begin(), __l.end());
    }
    // 还有其他一些 constructor 就不一一列出了吧...
    ~set() = default;
    
    set& operator=(const set&) = default;
    set& operator(set&&) = default;
    set& operator(initializer_list<value_type> __l) {
        _M_t._M_assign_unique(__l.begin(), __l.end());
        return *this;
    }

    key_compare key_comp() const {
        return _M_t.key_comp();
    }

    value_compare value_comp() const {
        return _M_t.key_comp();
    }

    // 接下来还有一些关于 set 的操作,都是 RB-tree 已经提供了的,所以只需要 set 调用即可
    // 这些操作包括：begin(),end(), rbegin(), rend(), empty(), size(), max_size()
    // swap(), insert(), erase(), clear(), find(), count(), lower_bound(), upper_bound()\
    // equal_range()等

    // 面对关联式容器,应该使用容器的成员find来查找元素,而不要使用STL的算法
    // 因为STL算法仅仅是按照顺序查找(迭代器递增的方式)
};

3. map

map 的所有元素会根据键值自动排序，map 的元素都是 pair，同时有 key 和 value，不允许两个元素有相同的 key。类似于 set，同样不可以通过迭代器改变键值，因为 RB-tree 是依靠键值开排列元素的，但是却可以通过迭代器改变元素值（value），在 RB-tree 中，每个节点都是一个 key-value，根据 key 组织整棵 RB-tree 。源代码实现在 stl_map.h 中, 900多行的源代码，看看怎么调用 RB-tree 的接口的吧！源码大概如下:

// 默认是升序的map
// 内存分配器是 std::allocator
template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map {
public:
  typedef _Key					key_type;
  typedef _Tp					mapped_type;
  typedef std::pair<const _Key, _Tp>		value_type;
  typedef _Compare					key_compare;
  typedef _Alloc					allocator_type;

private:
#ifdef _GLIBCXX_CONCEPT_CHECKS
  // concept requirements
  typedef typename _Alloc::value_type		_Alloc_value_type;
# if __cplusplus < 201103L
  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
# endif
  __glibcxx_class_requires4(_Compare, bool, _Key, _Key,
            _BinaryFunctionConcept)
  __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept)
#endif

#if __cplusplus >= 201103L && defined(__STRICT_ANSI__)
  static_assert(is_same<typename _Alloc::value_type, value_type>::value,
  "std::map must have the same value_type as its allocator");
#endif

public:
    class value_compare : public std::binary_function<value_type, value_type, bool> {
friend class map<_Key, _Tp, _Compare, _Alloc>;
protected:
    _Compare comp;

value_compare(_Compare __c) : comp(__c) { }

public:
    bool operator()(const value_type& __x, const value_type& __y) const
        { return comp(__x.first, __y.first); }
};

private:
    /// This turns a red-black tree into a [multi]map.
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<value_type>::other _Pair_alloc_type;

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
           key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    // 底层用 RB-tree 实现
    _Rep_type _M_t;

    typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;

// some constructors:
map() = default;

// 指定升序降序,内存分配器
explicit map(const _Compare& __comp, const allocator _type& __a = allocator_type())
    : _M_t(__comp, _Pair_alloc_type(__a)) { }

map(const map&) = defautle;

map(map&&) = default;

map(initializer_list<value_type> __l, const _Compare& __comp = _Compare(),
    const allocator_type& __a = allocator_type()) : _M_t(__comp, _Pair_alloc_type(__a))
    { _M_t._M_insert_unique(__l.begin(), __l.end()); }

/// Allocator-extended default constructor.
explicit map(const allocator_type& __a)
    : _M_t(_Compare(), _Pair_alloc_type(__a)) { }

/// Allocator-extended copy constructor.
map(const map& __m, const allocator_type& __a)
    : _M_t(__m._M_t, _Pair_alloc_type(__a)) { }

/// Allocator-extended move constructor.
map(map&& __m, const allocator_type& __a) noexcept(is_nothrow_copy_constructible<_Compare>::value
   && _Alloc_traits::_S_always_equal())
: _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }

/// Allocator-extended initialier-list constructor.
map(initializer_list<value_type> __l, const allocator_type& __a)
    : _M_t(_Compare(), _Pair_alloc_type(__a))
    { _M_t._M_insert_unique(__l.begin(), __l.end()); }

/// Allocator-extended range constructor.
template<typename _InputIterator>
map(_InputIterator __first, _InputIterator __last,
const allocator_type& __a)
    : _M_t(_Compare(), _Pair_alloc_type(__a))
    { _M_t._M_insert_unique(__first, __last); }

~map() = default;

map& operator=(const map&) = default;
map& operator=(map&&) = default;
// 将一个 initializer_list 拷贝给 map
map& operator=(initializer _list<value_type> __l) {
    _M_t._M.assign_unique(__l.begin(), __l.end());
    return *this;
}

iterator begin() { return _M_t.begin(); }
const_iterator begin() { return _M_t.begin(); }

iterator end() { return _M_t.end(); }
const_iterator end() { return _M_t.end(); }

// 省略一些获取迭代器的方法
// rbegin(), rend(), cbegin(), cend(), crbegin(), crend()

bool empty() const { return _M_t.empty(); }

size_type size() const { return _M_t.size(); }

// 返回 map 最大的 size
size_type max_size() const { return _M_t.max_size(); }

// operator[] 获取元素值 value
mapped_type& operator[](const key_type& __k) {
    iterator __i = lower_bound(__k);
    // 如果 __i->first  大于或者等于 __k
    // 插入这个pair
    if ( __i == end() || key_comp()(__k, (*__i).first)) {
        __i = _M_t._M.emplace_hint_unique(__i, std::piecewise_consttrct,
                            std::tuple<const key_type&>(__k),
                            std::tuple<>());
    }
    return (*__i).second;
}

mapped_type& at(const key_type &__k) {
    iterator __i = lower_bound(__k);
    // 抛异常
    if ( __i == end() || key_comp()(__k, (*__i).first))
        __throw_out_of_range(__N("map::at"));
    return (*__i).second;
}

// lower_bound(): 返回第一个大于等于给定值的元素(pair)
// upper_bound(): 类似
// 还有其他的一些成员
// insert(), try_emplace(), insert_or_assign(), erase(), swap(), clear(), key_compare(), find(), count()等
};

4. mutilset

mutilset 的用法和特性和 set 完全相同，唯一不同就是 multiset 允许元素重复，这是因为 multiset 的 insert 操作采用的是 RB-tree 的 insert_equal() 而不是 insert_unique()。

iterator insert(const value_type& __x) {
    return _M_t.M_insert_equal(__x);
}

iterator insert(value_type&& __x) {
    return __M_t._M_insert_equal(std::move(__x));
}
// 省略其他的insert，都是调用 insert_equal()