Skip to content

Last updated：2026-10-12

STL unordered_map source code analysis

0.Introduction

We learned about hashtable earlier; this section covers its container adaptor: unordered_map.

So the unordered map's underlying container is a hashtable.

The source of unordered_map and unordered_multimap lives in the file unordered_map.h.

1.The essential difference between unordered_map and unordered_multimap

First, a look at the unordered_map source:

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

Go look at the declaration of the underlying container __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>;
We can draw the following conclusion: the hashtable's template parameters: 
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash,
typename _RehashPolicy, typename _Traits>
By default, unordered_map uses: - H1 is hash - H2 is _Mod_range_hashing - _Hash is _Default_ranged_hash - _RehashPolicy is _Prime_rehash_policy - _Traits is _Tr The final _Tr is very important, because it is precisely due to this parameter that unordered_multimap exists. See the concrete analysis below:

_Tr is as follows:

typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
_Tr uses __umap_traits; let's keep going: 
template<bool _Cache>
using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
Comparing the two above, we find that inside __umap_traits there is a string of __cache_default. The template parameter is of bool type, so we can print whether it is false or true; by actual testing it is false, meaning the hash code is not cached.

template<typename _Tp, typename _Hash>
using __cache_default
=  __not_<__and_<__is_fast_hash<_Hash>,
__detail::__is_noexcept_hash<_Tp, _Hash>>>;
Continuing with __umap_traits, which actually calls _Hashtable_traits; we keep going:

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>;
};
We see three usings; understand them as three typedefs, meaning in order: whether the hash code is cached, whether the iterators are constant, and whether the keys are unique. Looking back up, what is passed in are three template parameters — false, false, true — which also confirms that unordered_map has unique keys, while the corresponding unordered_multimap has non-unique keys, its last parameter being false. We flip to the corresponding code:

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

To sum up, the analysis above shows us the essential difference between unordered_map and unordered_multimap, and also how a single underlying container implements two container adaptors in the source!

2.The essential difference between unordered_set and unordered_multiset

The analysis is the same as before; first look at 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>;
We can see that what is passed to _Hashtable_traits is false,true,true. For unordered_set, a const iterator and unique keys are used; now let's look at unordered_multiset:

template<bool _Cache>
using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
Comparing the two again: essentially, unordered_set does not allow duplicate keys, while unordered_multiset allows duplicate keys.

3.Three conclusions

Now, with the previous groundwork, let's list the four container adaptors in turn:

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

After comparing, we conclude:

  • Conclusion 1: unordered_map and unordered_set do not allow duplicate keys, while the multi variants do allow duplicate keys;
  • Conclusion 2: unordered_map and unordered_multimap use iterator as their iterator, while unordered_set and unordered_multiset use const_iterator.
  • Conclusion 3: for unordered_map and unordered_multimap the key is the key and the value is key+value; while for unordered_set and unordered_multiset the key is the Value, and the Value is also the Key.

For the last conclusion, compare the following (look at the first and second parameters passed to the hashtable):

unordered_map and 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 and 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.Important functions of unordered_map

Initialization

In the constructor below you can see that unordered_map's default bucket count is 10.

At its base, unordered_map defaults to hasher(), which is H1, which is 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)
{ }
Next, test whether the default hash is used:

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

9074142923776869151
9074142923776869151
This further confirms that the default hash is used.

Empty, size, maximum size

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

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

insert Five ways to 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); }

Erase

Three ways to erase

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

Clear

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

hash_function

Obtain this unordered_map's hash_function 

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

key_eq key_eq returns std::equal_to Used as follows: 

unordered_map<string,int> um;
cout<<um.key_eq()("1","2")<<endl;
Find and get values

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); }
Besides these functions there are also getting buckets, maximum bucket count, load factor, rehash, and so on — but there is no sorting, because hashtable provides no sorting functionality. Hashtable performs search, deletion, and node insertion in constant time, beating the RB-Tree red-black tree.

Similarly, unordered_set, unordered_multiset, and unordered_multimap have the same functions as unordered_map, so they need no elaboration.

Comments