前言

很多人只会用 umap ，或者只是学过 CPP11 以前的 hashmap 实现，实际上，从 hashmap 演化过来的 unordered_map 也可以很 modern cpp。

这里只考虑 unordered_multimap ,不考虑 unordered_multimap

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<typename _Key, //键类型
	   typename _Tp, //值类型
	   typename _Hash = hash<_Key>, //哈希函数，默认类型为k的hash函数
	   typename _Pred = std::equal_to<_Key>, //比较函数，默认为_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;
      ....
    }

constructor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
     /// Default constructor.
     unordered_map() = default;

     /**
      *  @brief  Default constructor creates no elements.
      *  @param __n  Minimal initial number of buckets.
      *  @param __hf  A hash functor.
      *  @param __eql  A key equality functor.
      *  @param __a  An allocator object.
      */
     explicit
     unordered_map(size_type __n,
	    const hasher& __hf = hasher(),
	    const key_equal& __eql = key_equal(),
	    const allocator_type& __a = allocator_type())
     : _M_h(__n, __hf, __eql, __a)
     { }

     /**
      *  @brief  Builds an %unordered_map from a range.
      *  @param  __first  An input iterator.
      *  @param  __last  An input iterator.
      *  @param __n  Minimal initial number of buckets.
      *  @param __hf  A hash functor.
      *  @param __eql  A key equality functor.
      *  @param __a  An allocator object.
      *
      *  Create an %unordered_map consisting of copies of the elements from
      *  [__first,__last).  This is linear in N (where N is
      *  distance(__first,__last)).
      */
     template<typename _InputIterator>
unordered_map(_InputIterator __first, _InputIterator __last,
	      size_type __n = 0,
	      const hasher& __hf = hasher(),
	      const key_equal& __eql = key_equal(),
	      const allocator_type& __a = allocator_type())
: _M_h(__first, __last, __n, __hf, __eql, __a)
{ }

explicit 关键字使被修饰的构造函数的类，只能发生显式类型转换而不能发生隐式类型转换。