STL之set与multiset那些事

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

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

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

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

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

    1. template<typename _Key, typename _Compare = std::less<_Key>,
    2.     typename _Alloc = std::allocator<_Key> >
    3. class set
    4. {
    5. private:
    7.     typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
    8.             key_compare, _Key_alloc_type> _Rep_type;
    9.     _Rep_type _M_t;  // Red-black tree representing set.
    11. public:
    12.     typedef typename _Rep_type::const_iterator            iterator;
    13.     typedef typename _Rep_type::const_iterator            const_iterator;
    14.     typedef typename _Rep_type::const_reverse_iterator    reverse_iterator;
    15.     typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
    16. };

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

    底部调用的是_M_insert_unique。

    1. template<typename _InputIterator>
    2. set(_InputIterator __first, _InputIterator __last)
    3. : _M_t()
    4. { _M_t._M_insert_unique(__first, __last); }

    我们再看看上面提到的函数：

    1. template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc>
    2. pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
    3. _Compare, _Alloc>::_Base_ptr,typename _Rb_tree<_Key, _Val, _KeyOfValue,Compare, _Alloc>::_Base_ptr>
    4. _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    5. _M_get_insert_unique_pos(const key_type& __k)
    6. {
    7.     // typedef pair
    9.     _Link_type __x = _M_begin();
    10.     _Link_type __y = _M_end();
    11.     bool __comp = true;
    13.     // 寻找插入点
    14.     while (__x != 0)
    15.     {
    16.         __y = __x;
    17.         // __k<__x是否为true
    18.         __comp = _M_impl._M_key_compare(__k, _S_key(__x));
    19.         // __k<__x就往左孩子查找，否则右孩子查找
    20.         __x = __comp ? _S_left(__x) : _S_right(__x);
    21.     }
    22.     iterator __j = iterator(__y);
    23.     // __k<__y，往__y的左孩子插入节点即可，不是做插入，是找到位置即可。
    24.     if (__comp)
    25.     {
    26.         // 特殊位置
    27.         if (__j == begin())
    28.         return _Res(__x, __y);
    29.         else
    30.         --__j;  // 左孩子 这里调用了--操作符
    31.     }
    32.     // __j<__k，返回当前节(__x=0)点与父节点
    33.     if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
    34.         return _Res(__x, __y);
    35.     // _j>=__k,插入失败
    36.     return _Res(__j._M_node, 0);
    37. }

    上述pair的使用给了我一个启发，竟然可以这样用，那么我们来学习一下：

    1. cout<<"flag: "<<itree._M_insert_unique(5).second<<endl;  // 学习返回值
    2. cout<<_Res(1,true).first<<endl;  // 直接包裹
    3. _Res r=make_pair(2,false);    // 定义新对象
    4. cout<<r.first<<endl;   // 输出结果

    2.multiset

    同理,multiset与set定义基本类似，不同之处，在于插入使用的是另一个函数,这样才使它能够完成重复key的插入！

    下面来分析一下_M_insert_equal:

    1. typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    2. _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    3. _M_insert_equal(_Arg&& __v)
    4. {
    5.     pair<_Base_ptr, _Base_ptr> __res = _M_get_insert_equal_pos(_KeyOfValue()(__v));
    6.     return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
    7. }

    我们继续追踪上述的_M_get_insert_equal_pos函数：

    1. template<typename _Key, typename _Val, typename _KeyOfValue,
    2. typename _Compare, typename _Alloc>
    3. pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
    4. _Compare, _Alloc>::_Base_ptr,
    5. typename _Rb_tree<_Key, _Val, _KeyOfValue,
    6. _Compare, _Alloc>::_Base_ptr>
    7. _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    8. _M_get_insert_equal_pos(const key_type& __k)
    9. {
    10.     typedef pair<_Base_ptr, _Base_ptr> _Res;
    11.     _Link_type __x = _M_begin();
    12.     _Link_type __y = _M_end();
    13.     while (__x != 0)
    14.     {
    15.         __y = __x;
    16.         __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
    17.             _S_left(__x) : _S_right(__x);
    18.     }
    19.     return _Res(__x, __y);