Saltar a contenido

Última actualización：2026-10-12

STL map y multimap

map/multimap usa rb_tree como estructura subyacente, por lo que sus elementos se ordenan automáticamente; el criterio de ordenación es la key.

map/multimap proporciona la operación de "recorrido" e iterators. Recorriendo según la regla normal (++iter) se obtiene el estado ordenado.

No podemos usar los iterators de map/multimap para cambiar la key de un elemento (porque la key tiene sus estrictas reglas de ordenación), pero sí podemos usarlos para cambiar el data del elemento. Por eso map/multimap fija internamente de forma automática como const el key type especificado por el usuario, impidiendo así la asignación a la key de un elemento.

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

En esta sección lo abordamos desde los puntos siguientes:

  • En map la key es key y el value es key+data, a diferencia de set, donde la key es el value y el value es la key.
  • La key de map no se puede modificar; map y multimap llaman a funciones de inserción distintas, lo que afecta a si su key se corresponde con un value.
  • Uso de initializer_list
  • map tiene el operador [], mientras que multimap no tiene operador [].

1.map

la key es key, el value es key+data

En el map siguiente podemos ver que value_type es un pair.

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{
public:
    typedef _Key                                          key_type;
    typedef _Tp                                           mapped_type;
    typedef std::pair<const _Key, _Tp>                    value_type;
    typedef _Compare                                      key_compare;
    typedef _Alloc                                        allocator_type;
private:
    // key为key,value为key+data
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
            key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;
};
map_data.png

El functor por defecto anterior es _Select1st; en stl_function vemos su código fuente:

template<typename _Pair>
struct _Select1st
: public unary_function<_Pair, typename _Pair::first_type>
{
    typename _Pair::first_type&
    operator()(_Pair& __x) const
    { return __x.first; }
};
Vemos que el _Select1st anterior es un struct, ¿cómo puede decirse entonces que es un functor? Porque dentro hay sobrecargado un operador (), ja~

Ahora implementemos uno nosotros mismos:

template<typename _T1>
struct mySelect1st
        : public unary_function<_T1, typename _T1::first_type>
{
    template<typename _T2>
    typename _T2::first_type&
    operator()(_T2& __x) const
    { return __x.first; }
};
int main() {
     typedef pair<const int,int> value_type;
    _Rb_tree<int, value_type, mySelect1st<value_type>, less<int>> it;
    it._M_insert_unique(make_pair(1,3));
    it._M_insert_unique(make_pair(3,6));
    for(auto each:it)
        cout<<each.first<<" "<<each.second<<endl;
}

la key no se puede modificar, el data sí

En el código fuente anterior: se añade automáticamente un const a la key, así que la key no se puede modificar. 

typedef std::pair<const _Key, _Tp>                    value_type;

2.insert

dentro de insert se usa _M_insert_unique

Las varias formas de insert:

(1) Insertar un pair

std::pair<iterator, bool> insert(const value_type& __x)
{ return _M_t._M_insert_unique(__x); }

dentro de map

(2) Insertar un pair en la posición indicada 

iterator insert(iterator __position, const value_type& __x)
{ return _M_t._M_insert_equal_(__position, __x); }

(3) Insertar a partir de un rango

template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_t._M_insert_equal(__first, __last); }
(4) Insertar desde una list

void
insert(initializer_list<value_type> __l)
{ this->insert(__l.begin(), __l.end()); }

Para el último insert, que lleva un initializer_list, con un ejemplo quedará claro.

3.uso de initializer_list

Práctica de programación real

vector<int> v={1,2,3};   // 底层调用vector的构造函数
v={2,5,6};               // 底层调用vector的=操作符
initializer_list<int> ll={4,5,6};
v.insert(v.begin(),ll);  // 底层调用下面insert函数
for(auto x:v) cout<<x<<" ";
cout<<endl;
vector<int> vv(ll);      // 底层调用vector的构造函数
vector<string> city{"Berlin", "New York", "London", "Cairo","Tokyo", "Cologne"};
Esta inicialización de vector ya os resulta muy familiar, ¿por qué se puede inicializar así? Veamos el código fuente de vector:

 vector&
operator=(initializer_list<value_type> __l)
{
    this->assign(__l.begin(), __l.end());
    return *this;
}

iterator
insert(const_iterator __position, initializer_list<value_type> __l)
{ return this->insert(__position, __l.begin(), __l.end()); }

vector(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__a)
{
_M_range_initialize(__l.begin(), __l.end(),
    random_access_iterator_tag());
}

Porque en su constructor hay un parámetro initializer_list; por ello podemos hacer este uso en map. Pero map no tiene un constructor análogo; también se aplica en el constructor de map, en insert y en =, igual que arriba: son los mismos tres sitios, ja~

Los tres usos de initializer_list:

// map构造
map(initializer_list<value_type> __l, const allocator_type& __a)
: _M_t(_Compare(), _Pair_alloc_type(__a))
{ _M_t._M_insert_unique(__l.begin(), __l.end()); }
// =操作符重载
map&
operator=(initializer_list<value_type> __l)
{
    this->clear();
    this->insert(__l.begin(), __l.end());
    return *this;
}
// insert插入
void
insert(std::initializer_list<value_type> __list)
{ insert(__list.begin(), __list.end()); }

Práctica de programación real

Uso de initializer_list en map (en set se usa igual):

// 这里要注意，pair的first参数必[须是const
initializer_list<pair<const strin[g,int>> l = {{"hello", 1}, {"world", 2}};
map<string,int> mm(l);  // map构造函数
map<string, int> m2{{"hello", 1}, {"world", 2}}; // map构造函数
map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符
map<string, int> mp;
mp.insert(l);       // insert插入[

Lo anterior plantea otra cuestión:

map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符
¿Por qué de estas dos líneas una llama al constructor y la otra al operador =?

En el momento de la inicialización, al definirse y asignarse a la vez se llama directamente al constructor; en las asignaciones posteriores se llama primero al constructor copia (que el compilador podría optimizar) y después al operador =.

Análisis con un ejemplo concreto

Vamos a analizarlo con un ejemplo concreto:

template <typename _Tp>
class Foo
{
public:
    Foo(initializer_list<_Tp> &list)
    {
        cout << "Foo(initializer_list<_Tp> &list)"<< endl;
    }

    Foo(int)
    {
        cout << "Foo(int )"<< endl;
    }

    Foo(const Foo& f)
    {
        cout << "调用了拷贝构造函数"<< endl;
    }
    Foo& operator=(initializer_list<_Tp> __l)
    {
        cout<<"调用了=操作符重载"<<endl;
        return *this;
    }

};
La llamada: 
Foo<int> foo=ll;
foo={1,2};
Resultado sin optimizar del compilador:

Foo(initializer_list<_Tp> &list)
调用了=操作符重载
Desactivando la optimización del compilador: g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors

Foo(initializer_list<_Tp> &list)
调用了拷贝构造函数
调用了=操作符重载

4.multimap

Igual que map, multimap no permite modificar la key. Pero su inserción usa _M_insert_equal. 

template <typename _Key, typename _Tp,
typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class multimap
{
public:                                      
    typedef std::pair<const _Key, _Tp> value_type;   
}
A continuación usamos multimap y rbtree, dos formas de practicar. 
multimap<int, string> c;
c.insert(make_pair(1,"asdqw"));
c.insert(make_pair(1,"qweq"));

for(auto each:c) cout<<each.first<<" "<<each.second<<endl;

typedef pair<const int,string> valueT;
_Rb_tree<int, valueT, _Select1st<valueT>, less<int>> mulm;
mulm._M_insert_equal(make_pair(2,"abc"));
mulm._M_insert_equal(make_pair(2,"cde"));
for(auto each:mulm)
cout<<each.first<<" "<<each.second<<endl;
Salida:

1 asdqw
1 qweq
2 abc
2 cde

5.Operadores importantes de map y multimap

Sobre el operador [] de map y multimap: el operador [] de map devuelve el segundo parámetro que se le pasó a map.

Si se pasa una key al [], si se encuentra, devuelve el value; si no, el valor por defecto 0. 

mapped_type&
operator[](const key_type& __k)
{
    iterator __i = lower_bound(__k);// 找到__k第一个。
    // __i->first is greater than or equivalent to __k.
    if (__i == end() || key_comp()(__k, (*__i).first))
    #if __cplusplus >= 201103L
    __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
                    std::tuple<const key_type&>(__k),
                    std::tuple<>());
    #else
        __i = insert(__i, value_type(__k, mapped_type()));
    #endif
    return (*__i).second;  // 返回key的value，此value为传递进map的第二个参数。
}

¡Pero multimap no tiene operador []!!!

Pensemos un momento: como en multimap una key puede corresponderse con varios value, si obtuviéramos mediante [] el value de una key, ¿cuál de los value obtendríamos? Por eso el código fuente de STL no sobrecarga este operador.

Temas relacionados

Comentarios