C++ STL源码剖析之unordered_map、unordered_multimap、unordered_set、unordered_multiset

0.导语

前面学到了hashtable，而这节是hashtable的容器适配器：unordered_map。

所以无序map的底层容器采用hashtable。

unordered_map与unordered_multimap的源码在unordered_map.h这个文件中。

1.undered_map与unordered_multimap本质区别

先来看一下undered_map源码：

  1. template<class _Key, class _Tp,
  2. class _Hash = hash<_Key>,
  3. class _Pred = std::equal_to<_Key>,
  4. class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  5. class unordered_map
  6. {
  7.     typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
  8.     _Hashtable _M_h;
  9. };

去看底层容器的__umap_hashtable的声明：

  1. template<bool _Cache>
  2. using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
  4. template<typename _Key,
  5.     typename _Tp,
  6.     typename _Hash = hash<_Key>,
  7.     typename _Pred = std::equal_to<_Key>,
  8.     typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
  9.     typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
  10. using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
  11. _Alloc, __detail::_Select1st,
  12. _Pred, _Hash,
  13. __detail::_Mod_range_hashing,
  14. __detail::_Default_ranged_hash,
  15. __detail::_Prime_rehash_policy, _Tr>;

可以得到下面结论:hashtable的模板参数：

  1. template<typename _Key, typename _Value, typename _Alloc,
  2. typename _ExtractKey, typename _Equal,
  3. typename _H1, typename _H2, typename _Hash,
  4. typename _RehashPolicy, typename _Traits>

默认情况下，undered_map采用：- H1为hash- H2为_Mod_range_hashing- _Hash为_Default_ranged_hash- _RehashPolicy为_Prime_rehash_policy- _Traits为_Tr对于最后的_Tr,非常重要，因为正是因为这个参数，才有undered_multimap。具体分析看下面：

_Tr如下：

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

_Tr使用了__umap_traits，我们继续往下看：

  1. template<bool _Cache>
  2. using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;

可以对比上述两个发现umap_traits里面有一串cache_default，我们再看一下模板参数为bool类型，故可以打印出来是false还是true，经过实测，为false，表示不缓存hash code。

  1. template<typename _Tp, typename _Hash>
  2. using __cache_default
  3. =  __not_<__and_<__is_fast_hash<_Hash>,
  4. __detail::__is_noexcept_hash<_Tp, _Hash>>>;

继续看__umap_traits，这个实际上是调用_Hashtable_traits，我们继续往下：

  1. template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
  2. struct _Hashtable_traits
  3. {
  4.     using __hash_cached = __bool_constant<_Cache_hash_code>;
  5.     using __constant_iterators = __bool_constant<_Constant_iterators>;
  6.     using __unique_keys = __bool_constant<_Unique_keys>;
  7. };

看到有三个using，理解为三个typedef，依次表示：hash code缓存与否，是否是常迭代器，是否是唯一的key，再往上回头看，传递进来的是三个模板参数，分别是false,false,true，也验证了undered_map是唯一的key，那么对应的undered_multimap就是不唯一的key，最后一个参数为false。我们翻阅到相应代码如下：

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

小结，在上面分析，我们知道了unordered_map与unordered_multimap的本质区别，也发现了如何在底层源码上用一个容器实现两个容器适配器！

2.undered_set与unordered_multiset本质区别

分析同前面一样，先看undered_set:

  1. template<class _Value,
  2.     class _Hash = hash<_Value>,
  3.     class _Pred = std::equal_to<_Value>,
  4.     class _Alloc = std::allocator<_Value> >
  5. class unordered_set
  6. {
  7.     typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
  8.     _Hashtable _M_h;
  9. }
  11. template<bool _Cache>
  12. using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
  14. template<typename _Value,
  15.     typename _Hash = hash<_Value>,
  16.     typename _Pred = std::equal_to<_Value>,
  17.     typename _Alloc = std::allocator<_Value>,
  18.     typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
  19. using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
  20.                 __detail::_Identity, _Pred, _Hash,
  21.                 __detail::_Mod_range_hashing,
  22.                 __detail::_Default_ranged_hash,
  23.                 __detail::_Prime_rehash_policy, _Tr>;

可以看到传递给_Hashtable_traits的是false,true,true。对于undered_set来说使用的是const iterator与唯一的key,我们再看一下unordered_multiset：

  1. template<bool _Cache>
  2. using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;

再将两者对比一下，本质就是undered_set不允许key重复，而undered_multiset允许key重复。

3.三大结论

现在，我们有了前面基础，依次列出前面四个容器适配器：

(1) undered_map

  1. template<bool _Cache>
  2. using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;

(2) undered_multimap

  1. template<bool _Cache>
  2. using __umap_traits = __detail::_Hashtable_traits<_Cache, false, false>;

(3) undered_set

  1. template<bool _Cache>
  2. using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;

(4) undered_set

  1. template<bool _Cache>
  2. using __uset_traits = __detail::_Hashtable_traits<_Cache, true, false>;

对比后，得出

  • 结论1：undered_map与undered_set不允许key重复,而带multi的则允许key重复；
  • 结论2：undered_map与undered_multimap采用的迭代器是iterator，而undered_set与undered_multiset采用的迭代器是const_iterator。
  • 结论3：undered_map与undered_multimap的key是key，value是key+value；而undered_set与undered_multiset的key是Value，Value也是Key。

最后一个结论对比看下面(我们看传递给hashtable的第一与第二个参数)：

undered_map与undered_multimap：

  1. using __umap_hashtable = _Hashtable<_Key, 
  2. std::pair<const _Key, _Tp>,
  3. _Alloc, __detail::_Select1st,
  4. _Pred, _Hash,
  5. __detail::_Mod_range_hashing,
  6. __detail::_Default_ranged_hash,
  7. __detail::_Prime_rehash_policy, _Tr>;

undered_set与undered_multiset：

  1. template<typename _Value,
  2. typename _Hash = hash<_Value>,
  3. typename _Pred = std::equal_to<_Value>,
  4. typename _Alloc = std::allocator<_Value>,
  5. typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
  6. using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
  7. __detail::_Identity, _Pred, _Hash,
  8. __detail::_Mod_range_hashing,
  9. __detail::_Default_ranged_hash,
  10. __detail::_Prime_rehash_policy, _Tr>;

4.undered_map重要函数

初始化

可以在下面的构造函数中看到undered_map的默认桶数为10。

在undered_map的底层默认采用hasher(),也就是H1,也就是std::hash

  1. unordered_map(size_type __n = 10,
  2.     const hasher& __hf = hasher(),
  3.     const key_equal& __eql = key_equal(),
  4.     const allocator_type& __a = allocator_type())
  5. : _M_h(__n, __hf, __eql, __a)
  6. { }

下面测试是否采用默认的hash：

  1. unordered_map<string,int> um;
  2. hash<string> h;
  3. cout<<um.hash_function()("hhhhhawq")<<endl;
  4. cout<<h("hhhhhawq")<<endl;

输出：

  1. 9074142923776869151
  2. 9074142923776869151

进一步验证了采用默认的hash。

是否空、大小、最大大小

  1. bool
  2. empty() const noexcept
  3. { return _M_h.empty(); }
  4. ///  Returns the size of the %unordered_map.
  5. size_type
  6. size() const noexcept
  7. { return _M_h.size(); }
  9. ///  Returns the maximum size of the %unordered_map.
  10. size_type
  11. max_size() const noexcept
  12. { return _M_h.max_size(); }

begin与end

  1. iterator
  2. begin() noexcept
  3. { return _M_h.begin(); }
  4. iterator
  5. end() noexcept
  6. { return _M_h.end(); }

insert 五种插入方式

  1. // value
  2. std::pair<iterator, bool>
  3. insert(const value_type& __x)
  4. { return _M_h.insert(__x); }
  6. // pair 
  7. std::pair<iterator, bool>
  8. insert(_Pair&& __x)
  9. { return _M_h.insert(std::forward<_Pair>(__x)); }
  11. // iterator+value
  12. iterator
  13. insert(const_iterator __hint, const value_type& __x)
  14. { return _M_h.insert(__hint, __x); }
  17. // first到last范围插入
  18. template<typename _InputIterator>
  19. void
  20. insert(_InputIterator __first, _InputIterator __last)
  21. { _M_h.insert(__first, __last); }
  23. // 初始化列表插入
  25. void
  26. insert(initializer_list<value_type> __l)
  27. { _M_h.insert(__l); }

删除

三种删除方式

  1. // iterator
  2. iterator
  3. erase(iterator __position)
  4. { return _M_h.erase(__position); }
  6. // key
  7. size_type
  8. erase(const key_type& __x)
  9. { return _M_h.erase(__x); }
  11. // first到last范围
  13. iterator
  14. erase(const_iterator __first, const_iterator __last)
  15. { return _M_h.erase(__first, __last);

清除

  1. void
  2. clear() noexcept
  3. { _M_h.clear(); }

hash_function

得到该undered_map的hash_function

  1. hasher
  2. hash_function() const
  3. { return _M_h.hash_function(); }

使用：

  1. unordered_map<string,int> um;
  2. cout<<um.hash_function()("hhhhhawq")<<endl; //传递的内容要与上面key类型一致。

key_eq key_eq返回的是std::equal_to 使用如下：

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

查找与获取value

  1. iterator
  2. find(const key_type& __x)
  3. { return _M_h.find(__x); }
  4. mapped_type&
  5. operator[](const key_type& __k)
  6. { return _M_h[__k]; }
  7. mapped_type&
  8. at(const key_type& __k)
  9. { return _M_h.at(__k); }

除了这些函数还有获取桶，最大桶数、加载因子、rehash等等，就是没有排序，因为hashtable没有提供排序功能。hashtable在查找、删除和插入节点是常数时间，优于RB-Tree红黑树。

同理，unordered_set、unordered_multiset、unordered_multimap与undered_map一样的函数，所以就不阐述了。