【STL】unordered_map

在 $C$++$11$ 中，$STL$ 标准库引入了一个新的标准关联式容器：$unordered\_map$（无序集合）。功能和 $set$ 类似，都用于存储唯一元素。但是其底层数据结构是哈希表，因此集合中的元素都是无序存储的，所以增删查的时间复杂度为 $O(1)$，增删查的效率比 $set$ 高。

---

一、unordered_map 的介绍

前面部分我们已经详细介绍了 $map$ 容器，可以参考我的这篇博客：【STL】$map$。由于 $map$ 和 $unordered\_map$ 这两个容器只是底层实现结构不同，其功能高度相似，基本上只要掌握 $map$ 的用法，$unordered\_map$ 也就会用了。因此，和 $map$ 相比只有一些性能和使用的差异，这里只介绍其差异部分。

$unordered\_map$ 的声明如下：

template < class Key,                                   // unordered_map::key_typeclass T,                                     // unordered_map::mapped_typeclass Hash = hash<Key>,                      // unordered_map::hasherclass Pred = equal_to<Key>,                  // unordered_map::key_equalclass Alloc = allocator< pair<const Key,T> >	// unordered_map::allocator_type> class unordered_map;

1. $Key$ 就是 $unordered\_map$ 底层关键字的类型。

2. $T$ 就是 $unordered\_map$ 底层 $value$ 的类型。

3. $unordered\_map$ 默认要求 $Key$ 支持转换为整形，如果不支持或者有自己的需求可以自行实现支持将 $Key$ 转成整形的仿函数传给第三个模板参数。

4. $unordered\_map$ 默认要求 $Key$ 支持比较相等，如果不支持或者有自己的需求可以自行实现支持将 $Key$ 比较相等的仿函数传给第四个模板参数。

5. $unordered\_map$ 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第五个模板参数。

注意：一般情况下，我们都不需要传后三个模板参数。

$unordered\_map$ 底层是用哈希桶实现，增删查平均效率是 $O(1)$，迭代器遍历不再有序，为了跟 $map$ 区分，所以取名 $unordered\_map$（无序集合）。

---

二、unordered_map 的使用（常用接口）

$unordered\_map$ 的底层结构是哈希表，因此不支持比较排序，所以细节上根据这一点和 $map$ 有略微不同，其他都完全类似。这里只给出常用接口，更多详细信息可以自行查官方文档：$unordered\_map$。

1. 常见构造

构造 $(constructor)$ 函数声明	接口说明
$unordered\_map()$	无参默认构造
$unordered\_map(constunordered\_map\&ump)$	拷贝构造
$unordered\_map(InputIteratorfirst,InputIteratorlast)$	使用迭代器区间构造
$unordered\_map(initializer\_list<value\_type>il)$	使用 $initializer$ 列表构造

2. iterator 的使用

$iterator$ 的使用	接口说明
$begin()$ $+$ $end()$	$iterator$
$cbegin()$ $+$ $cend()$	$const\_iterator$

$unordered\_map$ 的迭代器是一个单向迭代器：iterator -> a forward iterator to const value_type。

3. 增删查

$unordered\_map$ 增删查	接口说明
$insert$	插入 $val$ 数据
$erase$	删除 $val$ 数据
$find$	查找 $val$，返回 $val$ 位置的迭代器（没找到返回 $end()$）
$count$	查找 $val$，返回 $val$ 的个数

由于 $unordered\_map$ 不支持比较大小，且容器内元素是无序的，因此就没有 $lower\_bound$ 和 $upper\_bound$ 接口了。

4. unordered_multimap

$unordered\_multimap$ 和 $multimap$ 的使用基本完全类似，都支持关键值（$Key$）冗余。

和 $multimap$ 完全类似，$insert/find/count/erase$ 都围绕着支持值冗余有所差异：

1. $insert$ 可以插入相同的值。

2. 如果要查找的 $x$ 有多个值，$find$ 会返回第一个迭代器。

3. $count$ 会返回 $x$ 的实际个数。

4. $erase$ 指定值删除时，会删除所有的 $x$。

并且 $unordered\_multimap$ 也不支持 $[]$，因为支持 $key$ 冗余，$[]$ 就只能支持插入了，不能支持修改。

---

三、unordered_map 的模拟实现

1. STL 中的 hash_map 源码

$SGI-STL30$ 版本是 $C$++$11$ 之前的 $STL$ 版本，源代码中没有 $unordered\_map$，因为这个容器是 $C$++$11$ 之后才更新的。但是 $SGI-STL30$ 实现了哈希表，$hash\_map$ 作为非标准容器出现。关于哈希表这个数据结构的详细介绍，可以参考我的这篇博客：【数据结构】哈希表。

$stl\_hash\_map$：

// stl_hash_map
template <class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc>
class hash_map
{
private:typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht;ht rep;
public:typedef typename ht::key_type 		key_type;typedef T 							data_type;typedef T 							mapped_type;typedef typename ht::value_type 	value_type;typedef typename ht::hasher 		hasher;typedef typename ht::key_equal 		key_equal;typedef typename ht::iterator 		iterator;typedef typename ht::const_iterator const_iterator;
};

2. unordered_map 的迭代器

$unordered\_map$ 的 $iterator$ 不支持修改 $key$ 但是可以修改 $value$，我们把 $unordered\_map$ 的第二个模板参数 $pair$ 的第一个参数改成 $constK$ 即可。

typedef typename hashtable<K, pair<const K, V>, MapKeyOfT, Hash>::hash_iterator iterator;
typedef typename hashtable<K, pair<const K, V>, MapKeyOfT, Hash>::hash_const_iterator const_iterator;hashtable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;

3. unordered_map 支持 operator[]

$unordered\_map$ 要支持 $operator[]$ 主要需要修改 $insert$ 返回值支持，修改 $hashtable$ 中的 $insert$ 返回值为 pair<iterator, bool> insert(const T& data) 即可。

V& operator[](const K& key)
{pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));return ret.first->second;
}

4. 模拟实现 unordered_map

1. $hashtable.h$：

2. $unordered\_map.h$：

3. $test.cpp$：

---

总结