コンテンツにスキップ

最終更新：2026-10-12

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である。

具体的なコードは2番目の問題のところで示します。ここでは、私たちが普段コードを書いたときの内部ロジックを示します。中に赤黒木があり、赤黒木の定義では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.
};

set_key.png

2番目の問題：イテレータを使って要素の値を変更することはできない。

イテレータで要素の値を変更できない理由として、後述のイテレータを見ると、すべてconst_iteratorが使われていることがわかります。したがって、2番目の問題も解決です。

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、すなわちコンテナアダプタと呼ぶことができます。

3番目の問題：挿入されるkeyは一意である。

基盤で呼ばれているのは_M_insert_uniqueです。 

template<typename _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t()
{ _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を構築します。

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

先ほど触れた関数を見てみましょう： 

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

上記のpairの使い方にヒントを得ました。このような使い方ができるなら、勉強してみましょう： 

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

同様に、multisetとsetの定義はほぼ同じです。異なるのは挿入に別の関数を使っている点で、それによって重複したkeyの挿入を実現しているのです！

 template<typename _InputIterator>
multiset(_InputIterator __first, _InputIterator __last)
: _M_t()
{ _M_t._M_insert_equal(__first, __last); }
次に_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));
}

上記の_M_get_insert_equal_pos関数を引き続き追跡します：

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);
}
multisetとsetのこれらの関数を比較すると、返されるpairに顕著な違いがあることがわかります。先ほどのsetはkeyの重複が許されないため、最終的に挿入に成功したかどうかを返す必要がありました。一方、multisetは挿入の成否を返す必要がないため、pairにbool型は存在せず、挿入位置で構成されるpairをそのまま返します。したがって、先ほどと比べて、keyがいくつあっても、どれだけ重複していても、すべて挿入できるのです。

関連トピック

コメント