STL之set与multiset那些事

set/multiset以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key，而set/multiset元素的value和key合二为一：value就是key。

我们无法使用set/multiset的iterators改变元素值(因为key有其严谨排列规则)。 set/multiset的iterator是其底部RB tree的const-iterator，就是为了禁止用户对元素赋值。

set元素的key必须独一无二，因此其insert使用的是rb_tree的_M_insert_unique()，而multiset元素的key可以重复，因此其insert使用的是rb_tree的_M_insert_equal()。

1.set

针对set源码比较简单，故从下面几个问题出发。

第一个问题：key是value,value也是key。

具体代码再第二个问题中会有，这里给出我们通常写代码后内部逻辑，我们看到里面有个红黑树，而红黑树的定义key与value是一样的，所以回答了这个问题。(源码中typedef都是来自key)。

template<typename _Key, typename _Compare = std::less<_Key>,
    typename _Alloc = std::allocator<_Key> >
class set
{
    // concept requirements
    typedef typename _Alloc::value_type                   _Alloc_value_type;

public:
    // typedefs:
    //@{
    /// Public typedefs.
    typedef _Key     key_type;
    typedef _Key     value_type; // value也是key
    typedef _Compare key_compare;
    typedef _Compare value_compare;
    typedef _Alloc   allocator_type;
    //@}

private:

    typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
            key_compare, _Key_alloc_type> _Rep_type;
    _Rep_type _M_t;  // Red-black tree representing set.
};

第二个问题：无法使用迭代器改变元素值。

无法使用迭代器改变元素值我们看后面迭代器，发现全部用的是const_iterator，所以第二个问题也回答完毕。

template<typename _Key, typename _Compare = std::less<_Key>,
    typename _Alloc = std::allocator<_Key> >
class set
{
private:

    typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
            key_compare, _Key_alloc_type> _Rep_type;
    _Rep_type _M_t;  // Red-black tree representing set.

public:
    typedef typename _Rep_type::const_iterator            iterator;
    typedef typename _Rep_type::const_iterator            const_iterator;
    typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
    typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
};

经过前面分析，让我们想起了queue、priority_queue、stack，他们都使用的是底层的容器，所以称为容器适配器，而set也是使用底层的容器，所以也可以被称为container adapter,即容器适配器。