STL源码剖析-set容器

SGI STL中的容器set，以RB-Tree作为其底层的实现(rb_tree的大体分析见上文)。在set容器键值key和实值value是相同的，且在容器里面的元素是根据元素的键值自动排序的，同时我们不能修改set容器里面的元素值，所以set的迭代器是采用RB-Tree的const_iterator，不允许用户对其进行修改操作。

首先，给出上面的rb_tree的更详细的定义(主要给出模板Value的声明)：

template<typename Key, typename Value, typename Compare>
class rb_tree1{
protected:
    typedef typename __rb_tree_node_base* base_ptr;
    // Value是rb_tree的节点值，Key用于排序
    typedef __rb_tree_node<Value> rb_tree_node;
    // 空间配置器
    typedef allocator<rb_tree_node> rb_tree_node_allocator;
};

下面看下set, map中rb_tree的使用:

在set中对于rb_tree而言key, value都是一样的，内部成员就只有一个rb_tree

template <typename Key, class Compare = std::less<Key>>
class set{
    public:
        typedef Key key_type;
        typedef Key value_type;

        typedef Compare key_compare;

    private:
        // 对于set而言,Key, Value类型是一样的
        typedef rb_tree1<key_type, value_type, key_compare> rep_type;

        // set的成员变量
        rep_type t;
};

在map中对于rb_tree而言key, value不一样，key用于rb_tree排序，pair

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // 用于re_tree排序
    typedef Key    key_type;
    // rb_tree节点的value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // 对于map而言,Key, Value类型不一样，一个排序，另一个节点实值
    typedef rb_tree1<key_type, value_type, key_compare> rep_type;

    // map的成员变量
    rep_type t;
};

首先看构造函数：

set():t(Compare()){}

template<typename InputIterator>
set(InputIterator first, InputIterator last):t(Compare()){
    // 直接调用rb_tree的insert_unique
    t.insert_unique(first, last);
}

其他的操作基本上也是调用rb_tree的函数.