1. 前言

本文介绍set、map与unordered_set、unordered_map这四个容器，此类容器为关联式容器，主要是set（集合）和map（映射表）两大类。所谓关联式容器，即每笔数据都有一个键值（key）和一个实值（value），当元素被插入关联式容器中时，容器内部结构便会以键值大小，按照某中特定规则将元素放置在适当位置。关联式容器不存在头尾概念，因此也不会有push_back()、pop_front()等操作。

2. RB-tree

关联式容器的内部结构一般是一个balanced binary tree（平衡二叉树），以便获得良好的搜寻效率。RB-tree（红黑树）也是一种特殊的平衡二叉树，被广泛应用于STL的关联式容器中。

提到RB-tree，首先就需要了解二叉树、二叉搜索树、平衡二叉搜索树的概念:

• 1.如图1.1所示：二叉树树由父子节点组成，树的最上端为根节点，每个节点可以最多有左右两个子节点，有子节点即为父节点，否则为叶子节点。

图1.1 二叉树示意图

• 2.二叉搜索树是特殊的二叉树，它满足：任何节点的键值一定大于其左子树中每一节点的键值，并小于其右子树中的每一个节点的键值。以上图为例，4大于其左子树上的所有节点，小于其右子树上的节点，2大于左子树上的节点，小于右子树上的节点，所以此树是一个二叉搜索树。二叉搜索树通过中序遍历即可得到一个有序的排列，因此，二叉搜索树可提供**对数时间O(lgn)**平均时间复杂度的元素插入和访问。但二叉搜索树存在某个分支过长的情况,如图1.2所示,该二叉搜索树由于某个分支较长,其搜索元素的时间复杂度可能会退化成O(n).

图1.2 非平衡二叉搜索树示意图

• 3.平衡二叉搜索树是特殊的二叉搜索树，它在满足二叉搜索树的前提下，还需要满足：任何节点的左右子树高度差最多为1，从而保证了二叉搜索树的高度平衡;平衡二叉树由于其左右子树平衡的性质,因此其元素的搜索时间复杂度为对数时间O(lgn)。

• 4.RB-tree不仅是一个平衡二叉搜索树，而且还满足以下规则： |RB-tree规则| |:--| |每个节点不是红色就是黑色| |根节点为黑色| |如果节点为红，其子节点必须为黑| |任一节点至叶子节点的任何路径，所含黑节点数必须相同|

为了保持高度平衡，二叉树需要需要通过旋转等操作进行自我调整。由于红黑树的旋转算法较为复杂，这里只是对红黑树满足的规则进行简要介绍，不对红黑树的旋转算法做过多梳理。通过上述几个规则的保证，使红黑树能够保持一定的平衡，又不需要过度进行旋转调整。

2.1 RB-tree迭代器

通过内存模型，我们可以知道，RB-tree的迭代器至少要保证能指向树的节点(node)，且能支持按中序遍历的前进和后退动作，从而实现有序的遍历容器中的元素。

STL中将树型结构容器的迭代器此分为两层，先设计了基础迭代器，然后再派生出子类进行特性封装。

基础迭代器中最重要的便是定义了迭代器在二叉搜索树中如何进行前进和后退; 众所周知,二叉搜索树的中序遍历结果是一个有序的列表，基础迭代器的前进和后退就是定义了中序遍历的前进和后退的一个步骤。

// 基础迭代器
struct __rb_tree_base_iterator {
    ……
    /**
     * 二叉树中序遍历前进
     **/
    void increment()
    {
        if(node->right != 0)						   // 如果有右子节点）
        {
            node = node->right;						// 就向右走
            while(node->left != 0)					 // 然后一直沿左子树走到底
                node = node->left;					 // 走到底的左子节点前进到达的节点
        }
        else										   //如果没右子节点
        {
            __rb_tree_node_base* y = node->parent;	  // 找出父节点
            while(node == y->right)					 // 如果现在的节点本身就是父节点的右子节点
            {	
                node = y;							   // 一直向上找，直到不为右子节点
                y = y->parent;
            }
            if(node->right != y)					    // 如果此时的右子节点不是此时的父节点
                node = y;							   // 父节点就是下一节点
        }
    }

    /**
     * 二叉树中序遍历后退
     **/
    void decrement()
    {
        if(node->color == red && 					   // 如果是红节点，且
           node->parent->parent == node)			    // 父节点的父节点等于自己
        {
            node=node->right;					   	// 右子节点便是上一节点
        }
        else if(node->left != 0)					    // 如果有左子节点
        {
            __rb_tree_node_base* y = node->left;	    // 令y为左子节点
            while(y->right != 0)				    	// 若y有右子节点，
            {
                y = y->right;						   // 走到底
            }
            node = y;								   // 就是上一节点
        }
        else										    // 既不是根节点，也没有左子节点
        {
            __rb_tree_node_base* y = node->parent;	  // 找出父节点
            while(node == y->left)					  // 当node自身为左子节点时
            {
                node = y;
                y = y->parent;						  // 继续上溯至不为左子节点
            }
            node = y;								   // 就是上一节点
        }
    }
};
// rb_tree的迭代器
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
    ……
    // ++和--只需要调用base中的接口函数即可
    self& operator++()
    {
        increment();
        return *this;
    }
    self operator++(int)
    {
        self tmp = *this;
        increment();
        return tmp;
    }
    self& operator--()
    {
        decrement();
        return *this;
    }
    self operator--(int)
    {
        self tmp = *this;
        decrement();
        return tmp;
    }
};

2.3 RB-tree的元素操作

红黑树的核心就是其有序性，所以元素操作本质上还是在有序的基础上进行的。

2.3.1 插入操作

插入是红黑树的核心操作，其难点在于如何在插入后仍然保持红黑树的多个规则不被破坏：

pair<iterator,bool> insert_unique(const Value& v) 
{
    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);						 	// 小于则左走，大于则右走（二叉搜索树的特性，左边节点小于父节点）
    }															  // 退出循环时，y节点为插入点的父节点，插入点必为叶子节点
    iterator j = iterator(y);									  // 迭代器j指向其父节点
    if(comp) 
    {												 	         // 如果comp为真，则说明比父节点小，插入左侧  
        if(j == begin())									   	// 如果父节点是最左节点
            return pair<iterator,bool>(__insert(x,y,v),true);	  // 直接插入，x为插入点，y为父节点，v为插入值
        else
            --j;												   // 否则调整j
    }
    if(key_compare(key(j.node),KeyOfValue()(v)))				   // 新键值不与既有节点键值重复，则插入操作
        return pair<iterator,bool>(__insert(x,y,v),true);
    return pair<iterator,bool>(j,false);						   // 进行到此处，则说明有重复键值，不插入新值
}
// 真正的插入操作，x为插入点，y为父节点，v为插入值
iterator __insert(RB_tree_node* x,RB_tree_node* y,const Value& 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))) 
    {	 
        // 当父节点为header或者节点不为红色或者小于当前节点,左插
        z = create_node(v);												// 创造节点
        left(y) = z;													   // 父节点的左孩子为此节点
        if(y == header) 
        {												                  // 如果父节点为header
            root() = z;													// 此节点即为根节点
            rightmost() = z;											   // 本身就是左右极值
        }
        else if(y == leftmost()) 
        {										                          // 如果父节点是原树左极点
            leftmost() = z;												// 此节点插入父节点左侧，成为左极点
        }
    }
    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);													// 返回新增节点
}

2.3.2 查找操作

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 = right(x);												 // 否则向右走
    }
    iterator j = iterator(y);											 // 迭代器j指向y节点
    return (j == end() || key_compare(k,key(j.node))) ? end() : j;		// 如果j为end()，或者不存在此节点，返回end()；否则j即为搜寻到的节点
}

红黑树精髓便在左右判断上，也是二叉搜索树的重点特性：

struct __rb_tree_node_base {
    bool color;							// 红0黑1,false||true
    __rb_tree_node_base* parent