コンテンツにスキップ

最終更新：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>;
上の2つを対比すると、__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>;
};
3つのusingがあり、3つのtypedefとして理解できます。順に、hash codeをキャッシュするかどうか、定数イテレータかどうか、keyが一意かどうかを表します。さらに上に戻って見ると、渡されてくるのは3つのテンプレートパラメータで、それぞれ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の本質的な違いがわかり、基盤のソースコードで1つのコンテナを使って2つのコンテナアダプタを実現する方法も発見できました！

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はkeyの重複を許すという点です。

3.三大結論

さて、これまでの基礎をもとに、前の4つのコンテナアダプタを順に列挙します：

(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付きのものはkeyの重複を許します；
  • 結論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に渡される第1と第2のパラメータを見ます）：

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 5つの挿入方法

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

削除

3つの削除方法

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

このunordered_mapのhash_functionを取得します 

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と同じ関数があるので、ここでは述べません。

関連トピック

コメント