Saltar a contenido

Última actualización：2026-10-12

STL set y multiset

set/multiset usa rb_tree como estructura subyacente, por lo que sus elementos se ordenan automáticamente. El criterio de ordenación es la key, y en los elementos de set/multiset value y key se funden en uno solo: el value es la key.

No podemos usar los iterators de set/multiset para cambiar el valor de los elementos (porque la key tiene sus estrictas reglas de ordenación). El iterator de set/multiset es el const-iterator del RB tree subyacente, precisamente para prohibir que el usuario asigne a los elementos.

La key de un elemento de set debe ser única, por lo que su insert usa _M_insert_unique() de rb_tree, mientras que la key de un elemento de multiset puede repetirse, por lo que su insert usa _M_insert_equal() de rb_tree.

1.set

Como el código fuente de set es bastante sencillo, partimos de las preguntas siguientes.

Primera pregunta: la key es el value, y el value también es la key.

El código concreto aparecerá en la segunda pregunta; aquí damos la lógica interna del código que solemos escribir: vemos que dentro hay un árbol rojo-negro, y en la definición del árbol rojo-negro la key y el value son lo mismo, así que con eso queda respondida la pregunta. (En el código fuente los typedef provienen todos de 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

Segunda pregunta: no se puede usar el iterador para cambiar el valor de los elementos.

Lo de no poder usar el iterador para cambiar el valor de los elementos lo comprobamos en el iterador que viene a continuación: descubrimos que todo usa const_iterator, con lo que también queda respondida la segunda pregunta.

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

Tras el análisis anterior nos vienen a la memoria queue, priority_queue y stack: todos ellos usan un contenedor subyacente, por eso se llaman adaptadores de contenedor; y set también usa un contenedor subyacente, así que igualmente puede llamársele container adapter, es decir, adaptador de contenedor.

Tercera pregunta: la inserción usa una key única.

En la capa inferior se llama a _M_insert_unique. 

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

Echemos un vistazo sencillo a la implementación de esta función: El _M_get_insert_unique_pos de abajo devuelve un pair; si la key insertada coincide con otra, el second del pair es 0; según sea o no 0 se puede saber si la key está duplicada. Al comprobarlo en el código de abajo, cuando second no es 0, es decir, cuando no está duplicada, se puede insertar directamente: en ese caso se construye directamente un pair cuyo second es true; en caso contrario se construye un pair cuyo second es false.

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

Miremos también la función mencionada antes: 

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

El uso del pair anterior me ha dado una idea: si se puede usar así, aprendámoslo: 

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

Análogamente, multiset es básicamente igual que set en su definición; la diferencia está en que la inserción usa otra función, ¡y eso es justo lo que le permite completar la inserción de keys repetidas!

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

Seguimos rastreando la función _M_get_insert_equal_pos anterior:

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);
}
Si comparamos estas funciones de multiset y set descubrimos que el pair devuelto presenta una diferencia notable: antes, set necesitaba devolver si la inserción acabó teniendo éxito o no, porque la key no puede repetirse, mientras que multiset no necesita devolver si la inserción tuvo éxito, así que en su pair no existe el bool; devuelve directamente el pair formado por el punto de inserción. Por eso, comparado con lo anterior, por muchos keys que haya y por muy repetidos que estén, todos pueden insertarse.

Temas relacionados

Comentarios