Ir para o conteúdo

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

Análise do código-fonte do STL unordered_map

0. Introdução

Nas seções anteriores aprendemos o hashtable, e esta seção trata do seu adaptador de contêiner: o unordered_map.

Por isso, o contêiner subjacente do map não ordenado é o hashtable.

O código-fonte de unordered_map e unordered_multimap está no arquivo unordered_map.h.

1. A diferença essencial entre unordered_map e unordered_multimap

Primeiro, vamos olhar o código-fonte do unordered_map:

template<class _Key, class _Tp,
class _Hash = hash<_Key>,
class _Pred = std::equal_to<_Key>,
class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class unordered_map
{
    typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
    _Hashtable _M_h;
};

Vejamos a declaração do __umap_hashtable, o contêiner subjacente:

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;

template<typename _Key,
    typename _Tp,
    typename _Hash = hash<_Key>,
    typename _Pred = std::equal_to<_Key>,
    typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
    typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
_Alloc, __detail::_Select1st,
_Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;
Podemos chegar à conclusão abaixo: parâmetros de template do hashtable: 
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
typename _RehashPolicy, typename _Traits>
Por padrão, unordered_map usa: - H1 é hash - H2 é _Mod_range_hashing - _Hash é _Default_ranged_hash - _RehashPolicy é _Prime_rehash_policy - _Traits é _Tr Quanto ao último, _Tr, ele é muito importante, pois é exatamente por causa desse parâmetro que existe o unordered_multimap. A análise concreta vem a seguir:

_Tr é o seguinte:

typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>

_Tr usa __umap_traits; continuemos: 

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
Comparando os dois acima, percebemos que dentro de __umap_traits há um __cache_default; vejamos: o parâmetro de template é do tipo bool, então dá para imprimir se é false ou true — testado na prática, é false, o que significa não cachear o hash code.

template<typename _Tp, typename _Hash>
using __cache_default
=  __not_<__and_<__is_fast_hash<_Hash>,
__detail::__is_noexcept_hash<_Tp, _Hash>>>;
Continuando com __umap_traits, que na verdade chama _Hashtable_traits; sigamos em frente:

template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
struct _Hashtable_traits
{
    using __hash_cached = __bool_constant<_Cache_hash_code>;
    using __constant_iterators = __bool_constant<_Constant_iterators>;
    using __unique_keys = __bool_constant<_Unique_keys>;
};
Vemos três using, que podemos entender como três typedef, significando, em ordem: se o hash code é cacheado, se os iteradores são constantes e se a key é única. Voltando um pouco, os três parâmetros de template passados são, respectivamente, false, false e true, o que confirma que unordered_map tem key única; correspondentemente, o unordered_multimap tem key não única, com o último parâmetro false. Encontramos o código correspondente:

/// Base types for unordered_multimap.
template<bool _Cache>
using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;

Em resumo, com a análise acima, conhecemos a diferença essencial entre unordered_map e unordered_multimap e descobrimos como implementar dois adaptadores de contêiner sobre um único contêiner no código-fonte subjacente!

2. A diferença essencial entre unordered_set e unordered_multiset

A análise é igual à anterior; primeiro, unordered_set:

template<class _Value,
    class _Hash = hash<_Value>,
    class _Pred = std::equal_to<_Value>,
    class _Alloc = std::allocator<_Value> >
class unordered_set
{
    typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
    _Hashtable _M_h;
}

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;

template<typename _Value,
    typename _Hash = hash<_Value>,
    typename _Pred = std::equal_to<_Value>,
    typename _Alloc = std::allocator<_Value>,
    typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
                __detail::_Identity, _Pred, _Hash,
                __detail::_Mod_range_hashing,
                __detail::_Default_ranged_hash,
                __detail::_Prime_rehash_policy, _Tr>;
Vemos que o passado para _Hashtable_traits é false,true,true. Para unordered_set, usam-se const iterator e key única; vejamos agora o unordered_multiset:

template<bool _Cache>
using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
Comparando os dois, a essência é que unordered_set não permite keys repetidas, enquanto unordered_multiset permite.

3. Três conclusões

Agora, com a base anterior, listamos em ordem os quatro adaptadores de contêiner:

(1) unordered_map 

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
(2) unordered_multimap 
template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
(3) unordered_set

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
(4) unordered_multiset

template<bool _Cache>
using __uset_traits = __detail::_Hashtable_traits<_Cache, true, false>;

Após a comparação, concluímos:

  • Conclusão 1: unordered_map e unordered_set não permitem keys repetidas, enquanto os que têm multi permitem keys repetidas;
  • Conclusão 2: unordered_map e unordered_multimap usam o iterador iterator, enquanto unordered_set e unordered_multiset usam o iterador const_iterator.
  • Conclusão 3: em unordered_map e unordered_multimap, a key é key e o value é key+value; já em unordered_set e unordered_multiset, a key é Value, e Value também é Key.

Para a última conclusão, compare abaixo (observe o primeiro e o segundo parâmetros passados ao hashtable):

unordered_map e unordered_multimap: 

using __umap_hashtable = _Hashtable<_Key, 
std::pair<const _Key, _Tp>,
_Alloc, __detail::_Select1st,
_Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;
unordered_set e unordered_multiset: 
template<typename _Value,
typename _Hash = hash<_Value>,
typename _Pred = std::equal_to<_Value>,
typename _Alloc = std::allocator<_Value>,
typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
__detail::_Identity, _Pred, _Hash,
__detail::_Mod_range_hashing,
__detail::_Default_ranged_hash,
__detail::_Prime_rehash_policy, _Tr>;

4. Funções importantes do unordered_map

Inicialização

No construtor abaixo, vê-se que o número padrão de buckets do unordered_map é 10.

Na camada subjacente do unordered_map, o padrão é hasher(), ou seja, H1, ou seja, std::hash

unordered_map(size_type __n = 10,
    const hasher& __hf = hasher(),
    const key_equal& __eql = key_equal(),
    const allocator_type& __a = allocator_type())
: _M_h(__n, __hf, __eql, __a)
{ }
Agora, teste se é usado o hash padrão:

unordered_map<string,int> um;
hash<string> h;
cout<<um.hash_function()("hhhhhawq")<<endl;
cout<<h("hhhhhawq")<<endl;
Saída:

9074142923776869151
9074142923776869151
O que confirma ainda mais o uso do hash padrão.

Vazio, tamanho e tamanho máximo

bool
empty() const noexcept
{ return _M_h.empty(); }
///  Returns the size of the %unordered_map.
size_type
size() const noexcept
{ return _M_h.size(); }

///  Returns the maximum size of the %unordered_map.
size_type
max_size() const noexcept
{ return _M_h.max_size(); }

begin e end

iterator
begin() noexcept
{ return _M_h.begin(); }
iterator
end() noexcept
{ return _M_h.end(); }

insert Cinco formas de inserção

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

// pair 
std::pair<iterator, bool>
insert(_Pair&& __x)
{ return _M_h.insert(std::forward<_Pair>(__x)); }

// iterator+value
iterator
insert(const_iterator __hint, const value_type& __x)
{ return _M_h.insert(__hint, __x); }


// first到last范围插入
template<typename _InputIterator>
void
insert(_InputIterator __first, _InputIterator __last)
{ _M_h.insert(__first, __last); }

// 初始化列表插入

void
insert(initializer_list<value_type> __l)
{ _M_h.insert(__l); }

Remoção

Três formas de remoção

// iterator
iterator
erase(iterator __position)
{ return _M_h.erase(__position); }

// key
size_type
erase(const key_type& __x)
{ return _M_h.erase(__x); }

// first到last范围

iterator
erase(const_iterator __first, const_iterator __last)
{ return _M_h.erase(__first, __last);

Limpeza

void
clear() noexcept
{ _M_h.clear(); }

hash_function

Obtém a hash_function deste unordered_map 

hasher
hash_function() const
{ return _M_h.hash_function(); }
Uso: 
unordered_map<string,int> um;
cout<<um.hash_function()("hhhhhawq")<<endl; //传递的内容要与上面key类型一致。

key_eq key_eq retorna std::equal_to Uso: 

unordered_map<string,int> um;
cout<<um.key_eq()("1","2")<<endl;
Busca e obtenção de value

iterator
find(const key_type& __x)
{ return _M_h.find(__x); }
mapped_type&
operator[](const key_type& __k)
{ return _M_h[__k]; }
mapped_type&
at(const key_type& __k)
{ return _M_h.at(__k); }
Além dessas funções, há também as que obtêm buckets, número máximo de buckets, fator de carga, rehash etc. — só não há ordenação, porque o hashtable não oferece funcionalidade de ordenação. No hashtable, buscar, remover e inserir nós levam tempo constante, sendo melhor que a red-black tree RB-Tree.

Pelo mesmo raciocínio, unordered_set, unordered_multiset e unordered_multimap têm as mesmas funções de unordered_map, por isso não serão detalhados.

Tópicos relacionados

Comentários