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)。

  1. template<typename _Key, typename _Compare = std::less<_Key>,
  2.     typename _Alloc = std::allocator<_Key> >
  3. class set
  4. {
  5.     // concept requirements
  6.     typedef typename _Alloc::value_type                   _Alloc_value_type;
  8. public:
  9.     // typedefs:
  10.     //@{
  11.     /// Public typedefs.
  12.     typedef _Key     key_type;
  13.     typedef _Key     value_type; // value也是key
  14.     typedef _Compare key_compare;
  15.     typedef _Compare value_compare;
  16.     typedef _Alloc   allocator_type;
  17.     //@}
  19. private:
  21.     typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
  22.             key_compare, _Key_alloc_type> _Rep_type;
  23.     _Rep_type _M_t;  // Red-black tree representing set.
  24. };

set_key.png

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

无法使用迭代器改变元素值我们看后面迭代器，发现全部用的是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,即容器适配器。

第三个问题：插入是唯一的key。

底部调用的是_M_insert_unique。

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

我们来简单看一下这个函数实现：下面_M_get_insert_unique_pos返回的是个pair，如果插入的key相同则pair的second为0，根据是否为0可以判断是否key重复，在下面代码中判断时候，当second不为0，也就是不重复的时候，那么就可以直接插入，此时直接构造一个second为true的pair,否则构造一个second为false的pair。

  1. template<typename _Key, typename _Val, typename _KeyOfValue,
  2.      typename _Compare, typename _Alloc>
  3. #if __cplusplus >= 201103L
  4. template<typename _Arg>
  5. #endif
  6. pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
  7.                _Compare, _Alloc>::iterator, bool>
  8. _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
  9. _M_insert_unique( _Arg && __v )
  11. {
  12.     typedef pair<iterator, bool> _Res;
  13.     pair<_Base_ptr, _Base_ptr> __res
  14.         = _M_get_insert_unique_pos( _KeyOfValue() ( __v ) );
  16.     if ( __res.second )
  17.         return(_Res( _M_insert_( __res.first, __res.second,
  18.                      _GLIBCXX_FORWARD( _Arg, __v ) ),
  19.                  true ) );
  21.     return(_Res( iterator( static_cast<_Link_type>(__res.first) ), false ) );
  22. }

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

  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
  8.     typedef pair<_Base_ptr, _Base_ptr> _Res;
  9.     // _x表示当前节点,_y表示_x的父节点
  10.     _Link_type __x = _M_begin();
  11.     _Link_type __y = _M_end();
  12.     bool __comp = true;
  14.     // 寻找插入点
  15.     while (__x != 0)
  16.     {
  17.         __y = __x;
  18.         // __k<__x是否为true
  19.         __comp = _M_impl._M_key_compare(__k, _S_key(__x));
  20.         // __k<__x就往左孩子查找，否则右孩子查找
  21.         __x = __comp ? _S_left(__x) : _S_right(__x);
  22.     }
  23.     iterator __j = iterator(__y);
  24.     // __k<__y，往__y的左孩子插入节点即可，不是做插入，是找到位置即可。
  25.     if (__comp)
  26.     {
  27.         // 特殊位置
  28.         if (__j == begin())
  29.         return _Res(__x, __y);
  30.         else
  31.         --__j;  // 左孩子 这里调用了--操作符
  32.     }
  33.     // __j<__k，返回当前节(__x=0)点与父节点
  34.     if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
  35.         return _Res(__x, __y);
  36.     // _j>=__k,插入失败
  37.     return _Res(__j._M_node, 0);
  38. }

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

  1. cout<<"flag: "<<itree._M_insert_unique(5).second<<endl;  // 学习返回值
  2. typedef pair<int ,bool> _Res;    // 也来用一下typedef后的pair
  3. cout<<_Res(1,true).first<<endl;  // 直接包裹
  4. _Res r=make_pair(2,false);    // 定义新对象
  5. cout<<r.first<<endl;   // 输出结果

2.multiset

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

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

下面来分析一下_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);
  20. }

我们对比multiset与set的这几个函数发现，返回的pair有着显著的差异，之前的set需要返回最终是否插入成功，因为key不可重复，而multiset不需要返回是否插入成功，所以pair中不存在bool类型，故它是直接返回的插入点所构成的pair，因此，与之前相比较而言，不管你有多少个key，重复如何，都可以插入进去。