1 RB-tree

平衡二叉搜索树

按 Key 自动排序(默认递增排序, std::less<Key> )

1.1 节点

    struct __rb_tree_node_base
    {
        // ...
        typedef __rb_tree_node_base* base_ptr;
        
        // 4个成员数据
        color_type color;
        base_ptr parent;
        base_ptr left;
        base_ptr right;
        
        // 求以某节点为根的子树的 最小/大值: 一直向左/右走, 到头
        static base_ptr 
        minimum(base_ptr x)
        {
            while(x->left)
                x = x->left;
            return x;
        }
        
        static base_ptr maximum(base_ptr x) {/* ... */}
    };

    template <class Value>
    struct __rb_tree_node: public __rb_tree_node_base
    {
        typedef __rb_tree_node<Value>* link_type;
        // 1个新增成员数据
        Value value_field;
    };

1.2 迭代器

    struct __rb_tree_base_iterator
    {
        // 1个成员 
        base_ptr node;
        
        void increment(); // ++ 的 指针域操作
        void decrement(); // -- 
    };

    template<class Value, class Ref, class Ptr>
    struct __rb_tree_iterator：public __rb_tree_base_iterator
    {
        typedef __rb_tree_node<Value>* link_type;
        
        reference operator*() const
        {
            return ((link_type)node)->value_field;
        }
        
        self& operator++() // 前++
        {
            increment（）；
            return *this;
        }
    };

1.3 数据结构

    ExtractKey  
        |
        | 据 Value(node 的 data) 获取 key: RB-tree 内部用, 插入  
        |/
        Key 

    Compare
        据 `key 比较函数(对象)` 判2个 key 是否满足比较条件, 插入时用, hash_set/map 相等不插入     
        if(key_compare( key(targetIter->node), ExtractKey()(v) ) )
            ...

    template<class Key, class Value, class ExtractKey, class CompareKey, class Alloc = alloc>
    class rb_tree
    {
    protected:
        // 3个成员数据 
        size_type node_count;
        link_type header; // 是 root 的 parent
        CompareKey key_compare;
    public:
        __rb_tree_iterator<Value, reference, pointer> iterator;
        
    public:
        iterator begin() { return leftmost(); }
        iterator end(){ return header; }
        
    protected:
        // ...
        link_type& leftmost() const { (link_type&)header->left; }
        link_type& rightmost() const { (link_type&)header->right; }
        
        static reference value(link_type x){return x->value_field; }
        static const Key& key(link_type x){return ExtractKey()(value(x) );}
    };

2 set: 模板参数 模板形参中不必指定 Value(Key就是 Value), ExtractKey: std::identity

    template<class Key, class CompareKey, class Alloc = alloc>
    class set 
    {
        // ...
        typedef Key Value;
        typedef rb_tree<Key, Value, std::identity, CompareKey, Alloc> rep_type;
        
        // 1个成员数据 
        rep_type t;
    };

3 map: 模板形参中不必指定 ExtractKey: std::select1st<pair<const Key, T> >, pair<const Key, T> 为 rb_tree 中的 Value

    template<class Key, class T, 
             class CompareKey = std::less<Key>, // 默认递增排序 
             class Alloc = alloc>
    class map 
    {
        typedef pair<const Key, T> value_type;
        
        typedef rb_tree<Key, value_type, std::select1st<value_type>, CompareKey, Alloc> rep_type;
        
        // 1个成员数据 
        rep_type t;
    };

insert 返回 pair, 第1元素是迭代器, 指向插入的新元素或插入失败点(key 重复)的旧元素

4 multiset

5 multimap