Última atualização：2026-10-12

STL map e multimap

map/multimap têm o rb_tree como estrutura subjacente e, portanto, possuem a característica de ordenação automática dos elementos, sendo a ordenação baseada na key.

map/multimap oferecem a operação de "travessia" e iterators. Percorrendo com a regra normal (++iter), obtém-se o estado ordenado.

Não é possível usar os iterators de map/multimap para alterar a key dos elementos (porque a key tem regras rígidas de ordenação), mas é possível usá-los para alterar o data dos elementos. Por isso, map/multimap definem internamente o key type especificado pelo usuário como const, conseguindo assim proibir a atribuição à key dos elementos pelo usuário.

A key dos elementos de map deve ser única; por isso, o seu insert usa o _M_insert_unique() do rb_tree, enquanto a key dos elementos de multimap pode se repetir; por isso, o seu insert usa o _M_insert_equal() do rb_tree.

Nesta seção, abordaremos os seguintes pontos:

• no map, a key é key e o value é key+data, o que é diferente do set: no set, a key é o value e o value é a key.
• a key do map não pode ser modificada; as funções de inserção chamadas por map e multimap são diferentes, o que afeta se a key corresponde a um value.
• uso de initializer_list
• map tem o operador [], enquanto multimap não tem o operador [].

1. map

key é key, value é key+data

No map abaixo, vemos que value_type é um 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;
};

O functor padrão acima é o _Select1st; em stl_function vemos o código-fonte a seguir:

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 o _Select1st acima é um struct — como pode ser chamado de functor?

Porque dentro dele há uma sobrecarga do operador (), haha~

Agora, vamos implementar o nosso:

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

A key não pode ser alterada, o data pode

No código-fonte acima: um const é acrescentado automaticamente à key, por isso a key não pode ser alterada.

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

2. insert

O insert usa _M_insert_unique

Os vários métodos de insert:

（1）inserir um pair

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

Dentro do map

（2）inserir um pair na posição especificada

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

（3）inserir a partir de um intervalo

template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_t._M_insert_equal(__first, __last); }

（4）inserir a partir de uma list

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

Para o último insert, há um initializer_list; um exemplo basta para entender.

3. Uso de initializer_list

Prática real de programação

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

Quanto a essa inicialização de vector, todos estão bem familiarizados; por que é possível inicializar assim? Vejamos o código-fonte do 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 um dos parâmetros do seu construtor é um initializer_list, podemos usá-lo também com map. Mas o map não tem um construtor análogo; ele também é aplicado no construtor do map, no insert e no ``, exatamente como acima, nos mesmos três lugares, haha~

Os três 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ática real de programação

Uso de initializer_list no map (o uso no set é 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插入[

O acima levanta outra questão:

map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符

Por que, nesses dois casos, um chama o construtor e o outro chama o operador = ?

Na inicialização, definir e atribuir já invoca diretamente o construtor; atribuir de novo depois passa a chamar primeiro o construtor de cópia (que pode ser otimizado pelo compilador) e, em seguida, o operador = .

Análise de um exemplo

Vamos analisar com um exemplo 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;
    }

};

Chamada:

Foo<int> foo=ll;
foo={1,2};

Resultado sem otimização do compilador:

Foo(initializer_list<_Tp> &list)
调用了=操作符重载

Desativando a otimização do compilador: g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors

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

4. multimap

Assim como o map, o multimap não permite modificar a key. Mas a inserção 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;   
}

Agora, use multimap e rbtree de duas formas para praticar.

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;

Saída:

1 asdqw
1 qweq
2 abc
2 cde

5. Operadores importantes de map e multimap

Quanto ao operador [] de map e multimap: o operador [] do map retorna o segundo parâmetro passado ao map.

Passe uma key para o []: se for encontrada, obtém-se o value; caso contrário, o valor padrão 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的第二个参数。
}

Mas o multimap não tem o operador []!!!

Pensemos um pouco: como o multimap, dada uma key, pode corresponder a vários values, se obtivéssemos por meio de [] o value correspondente a uma key, qual value seria obtido afinal? Por isso, o código-fonte da STL não sobrecarrega esse operador!

Tópicos relacionados

• Análise do código-fonte do STL array | C++那些事
• Análise aprofundada do STL string | C++那些事
• Questões de entrevista sobre STL string explicadas | C++那些事
• Análise do código-fonte do STL deque | C++那些事
• STL otimização de classe base vazia EBO | C++那些事
• STL implementação manual de tabela hash | C++那些事
• STL hashtable tabela hash | C++那些事
• Análise do código-fonte dos iteradores da STL | C++那些事
• Análise do código-fonte do STL list | C++那些事
• Análise do código-fonte do STL queue e stack | C++那些事

Comentários