Перейти к содержанию

Последнее обновление：2026-10-12

Анализ исходников STL unordered_map

0. Введение

Ранее мы изучили hashtable, а этот раздел посвящён адаптеру контейнера над hashtable — unordered_map.

Поэтому нижележащим контейнером неупорядоченной map является hashtable.

Исходники unordered_map и unordered_multimap находятся в файле unordered_map.h.

1. Принципиальное различие unordered_map и unordered_multimap

Сначала взглянем на исходники 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;
};

Посмотрим объявление нижележащего контейнера __umap_hashtable:

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>;
Можно сделать следующий вывод: шаблонные параметры hashtable: 
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
typename _RehashPolicy, typename _Traits>
По умолчанию unordered_map использует: - H1 — hash - H2 — _Mod_range_hashing - _Hash — _Default_ranged_hash - _RehashPolicy — _Prime_rehash_policy - _Traits — _Tr Последний параметр _Tr чрезвычайно важен, ведь именно благодаря нему существует unordered_multimap. Подробный разбор — ниже.

_Tr выглядит так:

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

_Tr использует __umap_traits, копаем дальше: 

template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
Сравнив два фрагмента выше, обнаруживаем, что внутри __umap_traits фигурирует __cache_default. Параметр шаблона имеет тип bool, значит, можно вывести, false это или true; на практике получается false — это означает «не кэшировать hash code».

template<typename _Tp, typename _Hash>
using __cache_default
=  __not_<__and_<__is_fast_hash<_Hash>,
__detail::__is_noexcept_hash<_Tp, _Hash>>>;
Продолжаем смотреть __umap_traits — фактически это вызов _Hashtable_traits, идём дальше:

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>;
};
Видим три using — понимаем их как три typedef, обозначающих, по порядку: кэшируется ли hash code, являются ли итераторы константными, являются ли key уникальными. Возвращаясь чуть назад: внутрь передаются три шаблонных параметра — false, false, true, что ещё раз подтверждает: у unordered_map key уникальны; соответственно, у unordered_multimap key не уникальны — последний параметр false. Находим соответствующий код:

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

Итог: из проведённого анализа мы узнали принципиальное различие между unordered_map и unordered_multimap, а заодно увидели, как на уровне нижележащих исходников одним контейнером реализуются два адаптера контейнера!

2. Принципиальное различие unordered_set и unordered_multiset

Анализ такой же, как прежде; сначала смотрим 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>;
Видно, что в _Hashtable_traits передаются false,true,true. Для unordered_set используются const iterator и уникальные key; теперь взглянем на unordered_multiset:

template<bool _Cache>
using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
Сравнив оба, заключаем: суть в том, что unordered_set не допускает повторов key, а unordered_multiset — допускает.

3. Три главных вывода

Теперь, располагая изложенной выше базой, перечислим все четыре адаптера контейнера:

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

Сравнив, получаем:

  • Вывод 1: unordered_map и unordered_set не допускают повторов key, а варианты с multi — допускают;
  • Вывод 2: unordered_map и unordered_multimap используют итератор iterator, тогда как unordered_set и unordered_multiset — const_iterator.
  • Вывод 3: у unordered_map и unordered_multimap key — это key, а value — это key+value; у unordered_set и unordered_multiset key — это Value, и Value — это Key.

Последний вывод наглядно показан ниже (смотрим на первый и второй параметры, передаваемые в hashtable):

unordered_map и 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 и 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. Важные функции unordered_map

Инициализация

В приведённом ниже конструкторе видно, что число корзин unordered_map по умолчанию равно 10.

В нижележащем слое unordered_map по умолчанию используется hasher(), то есть H1, то есть 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)
{ }
Проверим ниже, используется ли hash по умолчанию:

unordered_map<string,int> um;
hash<string> h;
cout<<um.hash_function()("hhhhhawq")<<endl;
cout<<h("hhhhhawq")<<endl;
Вывод:

9074142923776869151
9074142923776869151
Что ещё раз подтверждает использование hash по умолчанию.

Пуст ли, размер, максимальный размер

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 и end

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

insert Пять способов вставки

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

Удаление

Три способа удаления

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

Очистка

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

hash_function

Получить hash_function данного unordered_map 

hasher
hash_function() const
{ return _M_h.hash_function(); }
Использование: 
unordered_map<string,int> um;
cout<<um.hash_function()("hhhhhawq")<<endl; //传递的内容要与上面key类型一致。

key_eq key_eq возвращает std::equal_to Используется так: 

unordered_map<string,int> um;
cout<<um.key_eq()("1","2")<<endl;
Поиск и получение 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); }
Помимо этих функций есть ещё получение корзин, максимального числа корзин, коэффициента загрузки, rehash и так далее — но нет сортировки, поскольку hashtable не предоставляет функциональность сортировки. Hashtable выполняет поиск, удаление и вставку узлов за константное время, что лучше красно-чёрного дерева RB-Tree.

Аналогично, у unordered_set, unordered_multiset и unordered_multimap те же функции, что и у unordered_map, поэтому на них останавливаться не будем.

Похожие темы

Комментарии