STL源码剖析 关联式容器 红黑树

• 边界情况的考虑，也就是走到根节点的时候需要有特殊的处理
• SGI STL为根节点载设计了一个父节点 名为header。每当插入节点的时候，不仅仅需要按照红黑树的规则进行调整，还需要维护header的正确性，使其父节点执行根节点，左子节点指向最小节点、右子节点指向最大节点

• 元素的插入和搜寻。插入元素的键值是否可以重复作为区分
• 用户需要明确设定所谓的KeyOfValue仿函数

#include 

#ifdef __STL_USE_EXCEPTIONS
#define __STL_TRY   try
#define __STL_UNWIND(action)   catch(...) { action; throw; }
#else
#define __STL_TRY
#define __STL_UNWIND(action)
#endif

typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false;  //红色为0
const __rb_tree_color_type __rb_tree_black = true; //黑色为1

struct __rb_tree_node_base{
    typedef __rb_tree_color_type color_type;
    typedef __rb_tree_node_base* base_ptr;

    color_type color;   //节点颜色 非红即黑
    base_ptr parent;    //RB-Tree的许多 *** 作 都是需要父节点的参与
    base_ptr left;      //指向左节点
    base_ptr right;     //指向右节点

    static base_ptr minimum(base_ptr x){
        while (x->left != 0){
            //二叉搜索树的特性
            //一直向左走 就会找到最小值
            x = x->left;
        }
        return x;
    }

    static base_ptr maximum(base_ptr x){
        while(x->right != 0){
            //二叉搜索树的特性
            //一直向右走 就会找到最大值
            x = x->right;
        }
        return x;
    }
};

template 
struct __rb_tree_node : public __rb_tree_node_base{
    typedef __rb_tree_node* link_type;
    Value value_field; //节点值
};

//基层迭代器
struct __rb_tree_base_iterator{
    typedef __rb_tree_node_base::base_ptr base_ptr;
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;

    base_ptr node; //用于和容器之间产生一个连接关系(make a reference)

    //以下实现于operator++内，因为再无其他地方会调用这个函数了
    void increment(){
        if (node->right != 0){        //如果有右节点，状况一
            node = node->right;       //就向右走
            while(node->left != 0){   //然后一直往左子树前进
                node = node->left;    //即为答案
            }
        } else{                       //没有右节点 状况二
            base_ptr y = node->parent;//找出父节点
            while(node == y->right){  //如果现行节点本身是个右子节点
                node = y;             //需要一直上溯  直到不为右子节点为止
                y = y->parent;
            }
            if (node->right != y){    //如果此时node的右子节点不等于此时的父节点
                node = y;             //状况三 此时的父节点即为解答
            }                         //否则 此时的node即为解答  状况四
        }
        
    }

    //以下实现于operator--内，因为再无其他地方会调用这个函数了
    void decrement(){
        //状况一
        //如果是红节点 且 父节点的父节点等于自己 右子节点即为答案
        //状况一 发生于node为header的时候(亦即node为end()时)
        //注意：header的右子节点 即 mostright指向整棵树的max节点
        if (node->color == __rb_tree_red && node->right->right == node){
            node = node->right;
        }
        //状况二
        //如果有左子节点 令y指向左子节点；只有当y有右子节点的时候 一直往右走 到底，最后即为答案
        else if (node->left!=0){
            base_ptr y = node->left;
            while (y->right != 0){
                y = y->right;
            }
            node = y;
        } else{
            //状况三
            //既不是根节点 也没有左节点
            //找出父节点，当现行的节点身为左子节点时，一直交替往上走，直到现行节点不是左节点为止
            base_ptr y = node->parent;
            while(node == y->left){
                node = y;
                y = y->right;
            }
            node = y; //此时父节点即为答案
        }
    }
};

//RB-Tree的正规迭代器
template 
struct __rb_tree_iterator : public __rb_tree_base_iterator{
    typedef Value value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef __rb_tree_iterator iterator;
    typedef __rb_tree_iterator const_iterator;
    typedef __rb_tree_iterator self;
    typedef __rb_tree_node* link_type;

    __rb_tree_iterator(){}
    __rb_tree_iterator(link_type x){node = x;}
    __rb_tree_iterator(const iterator& it){node = it.node;}

    reference operator* () const {return link_type(node)->value_field; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
    reference operator->()const {return &(operator*());}
#endif //__SGI_STL_NO_ARROW_OPERATOR
    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;
    }

};

template
class simple_alloc{
public:
    static T* allocate(std::size_t n){
        return 0==n?0:(T*)Alloc::allocate(n * sizeof(T));
    }
    static T* allocate(void){
        return (T*)Alloc::allocate(sizeof (T));
    }

    static void deallocate(T* p,size_t n){
        if (n!=0){
            Alloc::deallocate(p,n * sizeof(T));
        }
    }
    static void deallocate(T* p){
        Alloc::deallocate(p,sizeof(T));
    }
};

namespace Chy{
    template 
    inline T* _allocate(ptrdiff_t size,T*){
        std::set_new_handler(0);
        T* tmp = (T*)(::operator new((std::size_t)(size * sizeof (T))));
        if (tmp == 0){
            std::cerr << "out of memory" << std::endl;
            exit(1);
        }
        return tmp;
    }

    template
    inline void _deallocate(T* buffer){
        ::operator delete (buffer);
    }

    template
    inline void _construct(T1 *p,const T2& value){
        new(p) T1 (value);  //没看懂
    }

    template 
    inline void _destroy(T* ptr){
        ptr->~T();
    }

    template 
    class allocator{
    public:
        typedef T           value_type;
        typedef T*          pointer;
        typedef const T*    const_pointer;
        typedef T&          reference;
        typedef const T&    const_reference;
        typedef std::size_t size_type;
        typedef ptrdiff_t   difference_type;

        template
        struct rebind{
            typedef allocatorother;
        };

        pointer allocate(size_type n,const void * hint = 0){
            return _allocate((difference_type)n,(pointer)0);
        }

        void deallocate(pointer p,size_type n){
            _deallocate(p);
        }

        void construct(pointer p,const T& value){
            _construct(p,value);
        }

        void destroy(pointer p){
            _destroy(p);
        }

        pointer address(reference x){
            return (pointer)&x;
        }

        const_pointer const_address(const_reference x){
            return (const_pointer)&x;
        }

        size_type max_size()const{
            return size_type(UINT_MAX/sizeof (T));
        }
    };
}

template 
class rb_tree{
protected:
    typedef void* void_pointer;
    typedef __rb_tree_node_base* base_ptr;
    typedef __rb_tree_node rb_tree_node;
    typedef simple_allocrb_tree_node_allocator;
    typedef __rb_tree_color_type color_type;
public:
    typedef Key key_type;
    typedef Value value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef rb_tree_node* link_type;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
protected:
    link_type get_node(){return rb_tree_node_allocator::allocate();}
    void put_node(link_type p){return rb_tree_node_allocator::deallocate(p);}
    link_type create_node(const value_type& x){
        link_type tmp = get_node(); //配置空间
        __STL_TRY{
            Chy::allocator::construct(&tmp->value_field,x);//构造内容
        };
        __STL_UNWIND(put_node(tmp));
        return tmp;
    }
    link_type clone_node(link_type x){//复制一个节点的颜色和数值
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = 0;
        tmp->right = 0;
        return tmp;
    }

    void destroy_node(link_type p){
        Chy::allocator::destroy(&p->value_field); //析构内容
        put_node(p); //释放内存
    }
protected:
    //RB-tree只使用三笔数据表现
    size_type node_count; //追踪记录树的大小 (节点的数量)
    link_type header;     //实现上的小技巧
    Compare key_compare;  //节点之间的键值大小的比较准则. 应该会是一个function object
    //以下三个函数用于方便获取header的成员
    link_type& root() const{return (link_type&)header->parent;}
    link_type& left_most() const{return (link_type&)header->left;}
    link_type& right_most() const{return (link_type&)header->right;}
    //以下六个函数用于方便获得节点x的成员
    static link_type& left(link_type x){ return(link_type&)x->left;}
    static link_type& right(link_type x){ return(link_type&)x->right;}
    static link_type& parent(link_type x){ return(link_type&)x->parent;}
    static reference value(link_type x){ return x->value_field;}
    static const Key& key(link_type x){ return KeyOfValue()(value(x));}
    static color_type& color(link_type x){return (color_type&) (x->color);}
    //获取极大值和极小值 node class有实现此功能
    static link_type minimum(link_type x){
        return (link_type) __rb_tree_node_base::minimum(x);
    }
    static link_type maximum(link_type x){
        return (link_type) __rb_tree_node_base::maximum(x);
    }
    //迭代器
    typedef __rb_tree_iteratoriterator;
public:
    iterator __insert(base_ptr x,base_ptr y,const value_type& v);
    link_type __copy(link_type x,link_type p);
    void __erase(link_type x);

    void clear() {
        if (node_count != 0) {
            __erase(root());
            left_most() = header;
            root() = 0;
            right_most() = header;
            node_count = 0;
        }
    }

    void init(){
        header = get_node(); //产生一个节点空间 令header指向它
        color(header) = __rb_tree_red;//令header为红色 用于区分header和root,在iterator的operator++中
        root() == 0;
        left_most() = header;   //令header的左子节点等于自己
        right_most() = header;  //令header的右子节点等于自己
    }
public:
    //allocation / deallocation
    rb_tree(const Compare& comp = Compare())
    : node_count(0),key_compare(comp){
        init();
    }
    ~rb_tree(){
        clear();
        put_node(header);
    }

    rb_tree&operator==(const rb_tree&x);
public:
    //accessors
    Compare key_comp() const {return key_compare;}
    iterator begin() {return left_most();} //RB树的起头为最左(最小)节点处
    iterator end(){return header;} //RB树的终点为header所指处
    bool empty() const {return node_count == 0;}
    size_type size() const {return node_count;}
    size_type max_size() const {return size_type (-1);}
public:
    //insert/erase
    //将x插入到RB-Tree中 (保持节点的独一无二)
    std::pair insert_unique(const value_type& x);
    //将x插入到RB-Tree中 (允许节点数值重复)
    iterator insert_equal(const value_type& x);
    //寻找键值为k的节点
    iterator find(const value_type& k);
};

//插入新的数值 节点键值允许重复
//注意：返回的是一个RB-Tree的迭代器，指向的是新增的节点
template 
typename rb_tree::iterator
        rb_tree::insert_equal(const value_type &v) {
    link_type y = header;
    link_type x = root(); //根节点开始
    while(x != 0){        //根节点开始 从上往下寻找适当的插入节点
        y = x;
        //如果当前根节点比 输入的v大，则转向左边，否则转向右边
        x = key_compare(KeyOfValue()(v), key(x)) ? left(x) : right(x);
    }
    //x为新值插入点 y为插入点的父节点 v为新值
    return __insert(x,y,v);
}

//插入新的数值 节点键值不允许重复
//注意：返回结果是pair类型，第一个元素是一个RB-Tree的迭代器，指向的是新增的节点；第二个参数表示插入成功与否
template 
std::pair::iterator,bool>
rb_tree::insert_unique(const value_type &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); //遇"大"则向左 遇"小"则向右
    }
    //离开while循环之后 y所指的即 插入点之父节点（此时它必为叶子结点）
    iterator j = iterator(y); //迭代器j指向插入点的父节点y
    if (comp){
        //如果while循环时候，判定comp的数值，如果comp为真(表示遇到大的元素，将插入左侧)
        //如果插入节点的父节点是最左侧的节点
        //x为插入点，y为插入节点的父节点，v表示新值
        if (j == begin()){
            return std::pair(__insert(x,y,v), true);
        } else{
            //插入节点的父节点不是最左侧的节点
            //调整j 回头准备测试
            --j;
        }
        if (key_compare(key(j.node),KeyOfValue()(v))){
            //小于新值（表示遇到小的数值，将插在右侧）
            return std::pair(__insert(x,y,v), true);
        }
    }
    //至此 表示新值一定和树中的键值重复 就不应该插入新的数值
    return std::pair(j, false);
}

//真正的插入执行程序 __insert()
template 
typename rb_tree::iterator
rb_tree::__insert(base_ptr x_, base_ptr y_, const value_type &v) {
    //参数x_为新的插入点 参数y_为插入点的父节点 参数v为新值
    link_type x = (link_type)x_;
    link_type y = (link_type)y_;
    link_type z ;
    //key_compare 是键值大小的比较准则，应该是一个function object
    if (y == header||x != 0||key_compare(KeyOfValue()(v),key(x))){
        z = create_node(v); //产生一个新的节点
        //当y即为header的时候，leftmost = z;
        if (y == header){
            root() = z;
            right_most() = z;
        } else if (y == left_most()){
            //y为最左节点
            //维护leftmost() 使其永远指向最左节点
            left_most() = z;
        } else{
            z = create_node(v);//产生一个新的节点
            //让新节成为插入点的父节点y的右子节点
            right(y) = z;
            if (y == right_most()){ //维护rightmost()让其永远指向最右的节点
                right_most() = z;
            }
        }
        parent(z) = y; //设定新节点的父节点
        left(z) = 0; //设定新节点的左子节点
        right(z) = 0; //设定新节点的右子节点
        //修改颜色
        //参数一为新增节点 ；参数二 为root
        __rb_tree_rebalance(z,header->parent);
        ++node_count;
        //返回一个迭代器 指向新的节点
        return iterator(z);
    }
}

//全局函数
//新节点必须为红色，如果插入出父节点同样为红色，就需要进行树形旋转
inline void __rb_tree_rotate_left(__rb_tree_node_base* x,__rb_tree_node_base*& root){
    //x为旋转点
    __rb_tree_node_base* y = x->right;//令y为旋转点的右子节点
    x->right = y->left;
    if (y->left != 0){
        //回马q设定父亲节点
        y->left->parent = x;
    }
    y->parent = x->parent;
    //令y完全替代x的地位 (需要将x对其父节点的关系完全接收回来)
    if (x == root){
        root = y; //x为根节点
    } else if (x == x->parent->left){
        x->parent->left = y;  //x为其父节点的左子节点
    } else{
        x->parent->right = y; //x为其父节点的右子节点
    }
    y->left = x;
    x->parent = y;
}

//全局函数
//新节点必须为红色，如果插入出父节点同样为红色，就需要进行树形旋转
inline void __rb_tree_rotate_right(__rb_tree_node_base* x,__rb_tree_node_base*& root){
    //x为旋转点
    __rb_tree_node_base* y = x->left; //y为旋转点的左子节点
    x->left = y->right;
    if (y->right != 0){
        y->right->parent = x;
    }
    y->parent = x->parent;
    //令y完全替代x的地位
    if(x == root){
        root = y;
    } else if (x == x->parent->right){
        x->parent->right = y;
    } else{
        x->parent->left = y;
    }
    y->parent = x;
    x->parent = y;
}

//调整RB_tree 插入节点之后，需要进行调整(颜色/翻转)从而满足要求
inline void __rb_tree_balance(__rb_tree_node_base* x,__rb_tree_node_base*& root){
    x->color = __rb_tree_red; //新节点的颜色必须是红色的
    while(x!=root && x->parent->color == __rb_tree_red){
        //父节点为红色的
        //父节点为祖父节点的左子节点
        if (x->parent == x->parent->parent->left){
            //令y为伯父节点
            __rb_tree_node_base* y = x->parent->right;
            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);
            }
        }
    } //while结束
    root->color = __rb_tree_black;
}

//元素查找程序
template 
typename rb_tree::iterator
rb_tree::find(const value_type &k) {
    link_type y = header; //last node which is  not less than k
    link_type x = root(); //current node
    while(x != 0){
        //key_compare 是节点大小的比较准则 function object
        if (!key_compare(key(x),k)){
            //进行到这里 表示x的数值大于k 。遇到大的数值向左走
            y = x,x = left(x);
        } else{
            x = right(x);
        }
    }
    iterator j = iterator (y);
    return (j == end() || key_compare(k,key(j.node))) ? end() : j;
}