STL 容器 -- unordered_map/set

7、unordered_map/unordered_set/unordered_multimap/unordered_multiset（C++11）

STL 这四个容器底层实现都是哈希表，因为哈希表不具备排序功能，所以这四个容器元素都是无序的。底层哈希表整体布局如下：

如果想进一步了解哈希表，可以查阅分析的文章

GCC 哈希表设计与实现

7.1、unordered_map

unordered_map 和 map 除了底层实现不同，其他接口类似。

unordered_map 只有一个成员变量 _M_h，是 __umap_hashtable 类型。__umap_hashtable 就是 GCC 哈希表实现 _Hashtable 的别名，使用的是 _Prime_rehash_policy 扩容策略。

_Hashtable 的数据域保存的是 pair<Key, Value> 类型。

/// unordered_map.h 
  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>;

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

_Hashtable_traits 最后一个表示是否元素唯一，unordered_map 指定的模板参数是 true，表示元素唯一。

/// hashtable_policy.h
  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>;
    };

插入和删除调用 _Hashtable 的实现。

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

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

_Hashtable 的 max_load_factor 是可以被修改，并且是使用过程中可以修改。

/// unordered_map.h
      void
      max_load_factor(float __z)
      { _M_h.max_load_factor(__z); }

7.2、unordered_set

unordered_set 和 unorsered_map 实现完全一致，只不过 _Hashtable 节点数据域保存的是 value，而不是想 unordered_map 保存的是 pair<Key, Value> 键值对。

/// unordered_set.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>;

  template<typename _Value,
       typename _Hash = hash<_Value>,
       typename _Pred = equal_to<_Value>,
       typename _Alloc = allocator<_Value>>
    class unordered_set
    {
      typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;
      /* ... */
    };

7.3、unordered_multimap

unordered_multimap 和 unordered_map 相似。两者的区别是使用了不同的 _Hashtable_traits。

/// unordered_map.h
  template<bool _Cache>
    using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;

  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 = __ummap_traits<__cache_default<_Key, _Hash>::value>>
    using __ummap_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>;

  template<typename _Key, typename _Tp,
       typename _Hash = hash<_Key>,
       typename _Pred = equal_to<_Key>,
       typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
    class unordered_multimap
    {
      typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;
      /* ... */
    };

_Hashtable_traits 最后一个表示是否元素唯一，unordermap_multimap 模板参数是 false，要求 _Hashtable 中元素不唯一。

7.4、unordered_multiset

unordered_multiset 和 unordered_multimap 实现一致，只不过 _Hashtable 节点数据域保存的是 Value，而 unordered_map 保存的是 pair<Key, Value> 键值对。

/// unordered_set.h
  template<bool _Cache>
    using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;

  template<typename _Value,
       typename _Hash = hash<_Value>,
       typename _Pred = std::equal_to<_Value>,
       typename _Alloc = std::allocator<_Value>,
       typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
    using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
                     __detail::_Identity,
                     _Pred, _Hash,
                     __detail::_Mod_range_hashing,
                     __detail::_Default_ranged_hash,
                     __detail::_Prime_rehash_policy, _Tr>;

  template<typename _Value,
       typename _Hash = hash<_Value>,
       typename _Pred = equal_to<_Value>,
       typename _Alloc = allocator<_Value>>
    class unordered_multiset
    {
      typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;
      /* ... */
    };