Skip to content

Last updated：2026-10-12

STL set and multiset

set/multiset use rb_tree as their underlying structure, and therefore have the characteristic of automatic element sorting. Sorting is based on the key, and for set/multiset elements the value and the key are one and the same: the value is the key.

We cannot use set/multiset iterators to change element values (because the key has its strict ordering rules). The iterators of set/multiset are the const-iterators of the underlying RB tree, precisely to forbid users from assigning to elements.

The key of a set element must be unique, so its insert uses the rb_tree's _M_insert_unique(), while the key of a multiset element may repeat, so its insert uses the rb_tree's _M_insert_equal().

1.set

The source code of set is fairly simple, so let's start from the following questions.

First question: the key is the value, and the value is also the key.

The concrete code will appear in the second question; here we give the internal logic after the code we usually write. We see there is a red-black tree inside, and in the red-black tree's definition the key and the value are the same, which answers this question. (In the source code the typedefs all come from the 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.
};

set_key.png

Second question: element values cannot be changed via iterators.

For not being able to change element values via iterators, we look at the iterators later and find that they all use const_iterator, so the second question is answered as well.

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;
};

The analysis above reminds us of queue, priority_queue, and stack: they all use an underlying container, which is why they are called container adaptors. set likewise uses an underlying container, so it too can be called a container adapter.

Third question: insertion requires a unique key.

What gets called underneath is _M_insert_unique. 

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

Let's take a quick look at this function's implementation: Below, _M_get_insert_unique_pos returns a pair; if the inserted key is the same, the pair's second is 0, so whether the key duplicates can be judged from whether it is 0. In the check in the code below, when second is not 0 — that is, not a duplicate — it can be inserted directly, in which case a pair with second true is constructed directly; otherwise a pair with second false is constructed.

template<typename _Key, typename _Val, typename _KeyOfValue,
     typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
template<typename _Arg>
#endif
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
               _Compare, _Alloc>::iterator, bool>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert_unique( _Arg && __v )

{
    typedef pair<iterator, bool> _Res;
    pair<_Base_ptr, _Base_ptr> __res
        = _M_get_insert_unique_pos( _KeyOfValue() ( __v ) );

    if ( __res.second )
        return(_Res( _M_insert_( __res.first, __res.second,
                     _GLIBCXX_FORWARD( _Arg, __v ) ),
                 true ) );

    return(_Res( iterator( static_cast<_Link_type>(__res.first) ), false ) );
}

Let's also look at the function mentioned above: 

template<typename _Key, typename _Val, typename _KeyOfValue,typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,typename _Rb_tree<_Key, _Val, _KeyOfValue,Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_unique_pos(const key_type& __k)
{
    // typedef pair
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    // _x表示当前节点,_y表示_x的父节点
    _Link_type __x = _M_begin();
    _Link_type __y = _M_end();
    bool __comp = true;

    // 寻找插入点
    while (__x != 0)
    {
        __y = __x;
        // __k<__x是否为true
        __comp = _M_impl._M_key_compare(__k, _S_key(__x));
        // __k<__x就往左孩子查找，否则右孩子查找
        __x = __comp ? _S_left(__x) : _S_right(__x);
    }
    iterator __j = iterator(__y);
    // __k<__y，往__y的左孩子插入节点即可，不是做插入，是找到位置即可。
    if (__comp)
    {
        // 特殊位置
        if (__j == begin())
        return _Res(__x, __y);
        else
        --__j;  // 左孩子 这里调用了--操作符
    }
    // __j<__k，返回当前节(__x=0)点与父节点
    if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
        return _Res(__x, __y);
    // _j>=__k,插入失败
    return _Res(__j._M_node, 0);
}

The use of pair above gave me an insight — so it can be used like this! Let's learn it: 

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

2.multiset

Similarly, multiset is defined basically like set; the difference is that its insertion uses another function, which is what enables it to accomplish inserting duplicate keys!

 template<typename _InputIterator>
multiset(_InputIterator __first, _InputIterator __last)
: _M_t()
{ _M_t._M_insert_equal(__first, __last); }
Next let's analyze _M_insert_equal:

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

We continue tracing the _M_get_insert_equal_pos function above:

template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr,
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::_Base_ptr>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_get_insert_equal_pos(const key_type& __k)
{
    typedef pair<_Base_ptr, _Base_ptr> _Res;
    _Link_type __x = _M_begin();
    _Link_type __y = _M_end();
    while (__x != 0)
    {
        __y = __x;
        __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
            _S_left(__x) : _S_right(__x);
    }
    return _Res(__x, __y);
}
Comparing these functions of multiset and set, we find a striking difference in the returned pair: the previous set needed to return whether the insertion ultimately succeeded, because keys cannot repeat, whereas multiset does not need to return insertion success, so its pair contains no bool type — it directly returns the pair formed from the insertion point. Therefore, compared with before, no matter how many keys you have or how they repeat, they can all be inserted.

Comments