1. unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查找时效率可达到O ( l o g 2 N ) O(log_2 N)O(log2N)，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查找效率也不理想。效率最高的查找方式是：进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
实际上，unordered_map和unordered_set从名字看来，它储存的元素是unordered（无序的），而在使用上大体和set和map并无二致。
不同的是，unordered系列的容器使用了哈希结构，这也是它们存储的元素不在有序的原因。由于STL良好的封装，使得即使底层实现不同，但上层使用上还是类似的。
友情链接：map和set
unordered的命名的历史背景：
如果在现在看来，包括Java标准库也是这样设计的：根据底层实现方式的不同，set和map都以设计结构为前缀，例如：TreeMap、TreeSet；HashMap、HashSet等。
C++标准库在早期并没有将哈希结构的map和set另外作为一类容器，而是将以红黑树为底层结构的map和set作为内置容器，原因是当时计算机的CPU的算力和实际数据量还无需使用查找效率更高的哈希结构封装的map和set。但是已经推出的标准无法改变，C++的某个语言标准中提出了增加
hash_*类模板，最终接受为unordered_*。
2. unordered_set
2.1 unordered_set的介绍
- unordered_set是存储<key, value>键值对的关联式容器，其允许通过key值快速的索引到与其对应的value值；键值key通常用于唯一地标识元素，而value值是一个对象，它的内容和键值key关联；
- unordered_set没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_set将相同哈希值的键值对放在相同的桶中；
- unordered_set容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低；
- 它只有单向迭代器。
2.2 unordered_set的使用
unordered_set的模板参数列表
头文件
#include <unordered_set>
模板参数列表
template< class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator< std::pair<const Key, T> > > class unordered_map;
- Key：容器中存储元素的类型；
- Hash：确定元素存储位置所用的哈希函数；
- KeyEqual：判断各个元素是否相等所用的函数；
- Allocator：指定分配器对象的类型（暂不做了解）。
| 参数 | 含义 |
| Key | 确定容器存储元素的类型，如果将unordered_set看做是存储键和值相同的键值对的容器，则此参数则用于推导各个键值对的键和值的类型，因为它们是完全相同的，因此一定是同一数据类型的数据。 |
| Hash=hash<Key> | 指定unordered_set容器底层存储各个元素时，所使用的哈希函数。需要注意的是，默认哈希函数hash<Key>只适用于基本数据类型（包括 string 类型），而不适用于自定义类型。 |
| Pred=equal_to<Key> | unordered_set容器内部不能存储相同的元素，而衡量2个元素是否相等的标准，取决于该参数指定的函数。默认情况下，使用STL标准库中提供的equal_to<key>规则，该规则仅支持可直接使用==运算符做比较的数据类型。 |
unordered_set的构造器
| 函数声明 | 功能 |
unordered_set(size_type()) {} |
构造空的unordered_set容器 |
unordered_set ( InputIterator first, InputIterator last); |
用[first, last)区间中的元素构造 unordered_set |
unordered_set( unordered_set&& other ); |
unordered_set的拷贝构造 |
示例：
void unordered_set_test1() { unordered_set<int> us1; // 构造int类型的空容器 string str = "hello world"; unordered_set<char> us2(str.begin(), str.end()); // 使用迭代器区间构造 unordered_set<int> us3(us1); // 拷贝构造 }
unordered_set常用接口
| 成员方法 | 功能 |
| empty() | 若容器为空，则返回true；否则false。 |
| size() | 返回当前容器中存有元素的个数。 |
| max_size() | 返回容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。 |
| find(key) | 查找以值为key的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果end()方法返回的迭代器）。 |
| count(key) | 在容器中查找值为key的元素的个数。 |
| equal_range(key) | 返回一个pair对象，其包含2个迭代器，用于表明当前容器中值为key的元素所在的范围。 |
| emplace() | 向容器中添加新元素，效率比insert()方法高。 |
| emplace_hint() | 向容器中添加新元素，效率比insert()方法高。 |
| insert() | 向容器中添加新元素。 |
| erase() | 删除指定元素。 |
| clear() | 清空容器，即删除容器中存储的所有元素。 |
| swap() | 交换2个unordered_set容器存储的元素，前提是必须保证这2个容器的类型完全相等。 |
| bucket_count() | 返回当前容器底层存储元素时，使用桶（一个线性链表代表一个桶）的数量。 |
| max_bucket_count() | 返回当前系统中，unordered_set 容器底层最多可以使用多少桶。 |
| bucket_size(n) | 返回第n个桶中存储元素的数量。 |
| bucket(key) | 返回值为key的元素所在桶的编号。 |
| load_factor() | 返回unordered_set容器中当前的负载因子。负载因子，指的是的当前容器中存储元素的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。 |
| max_load_factor() | 返回或者设置当前unordered_set容器的负载因子。 |
| rehash(n) | 将当前容器底层使用桶的数量设置为n。 |
| reserve() | 将存储桶的数量（也就是bucket_count()方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。 |
| hash_function() | 返回当前容器使用的哈希函数对象。 |
迭代器相关
| 成员方法 | 功能 |
| begin() | 返回指向容器中第一个元素的正向迭代器。 |
| end(); | 返回指向容器中最后一个元素之后位置的正向迭代器。 |
| cbegin() | 和begin()功能相同，只不过其返回的是const类型的正向迭代器。 |
| cend() | 和end()功能相同，只不过其返回的是const类型的正向迭代器。 |
unordered_set没有反向迭代器。
示例
void unordered_set_test2() { unordered_set<int> us; us.insert(1); us.insert(1); // 去重 us.insert(2); us.insert(5); us.insert(4); us.insert(3); us.insert(6); for (auto e : us) // 使用范围for遍历 { cout << e << " "; } cout << endl; unordered_set<int>::iterator pos = us.find(2); // 找到key为2的位置 us.erase(pos); // 删除key为2的元素 unordered_set<int>::iterator it = us.begin(); while (it != us.end()) // 迭代器遍历 { cout << *it << " "; ++it; } cout << endl; cout << us.count(1) << endl; // 容器中key为1的元素个数 cout << us.size() << endl; // 容器中元素的个数、 us.clear(); // 清空容器 cout << us.empty() << endl; }
输出
1 2 5 4 3 6
1 5 4 3 6
1
5
1
3. unordered_multiset
unordered_multiset和unordered_set的唯一区别是它允许键值冗余，即可以储存key值重复的元素。因此，两种容器的find和count的意义也有所区别。
3.1 成员函数的区别
find
| find | 功能 |
| unordered_set | 返回key值为x的元素的迭代器 |
| unordered_multiset | 返回哈希表中第一个key值为x的元素的迭代器 |
count
| count | 功能 |
| unordered_set | 键值key为x的元素存在则返回1，不存在则返回0 |
| unordered_multiset | 返回键值key为x的元素个数 |
3.2 示例
void unordered_multiset_test() { unordered_multiset<int> ums; ums.insert(1); ums.insert(1); ums.insert(2); ums.insert(7); ums.insert(5); ums.insert(4); ums.insert(2); for(auto e : ums) { cout << e << " "; } cout << endl; }
输出
4 5 2 2 7 1 1
4. unordered_map
4.1 unordered_map的介绍
通过查阅官方文档们可以知道unordered_map的特性：
- unordered_map是存储<key, value>键值对的关联式容器，其允许通过key值快速的索引到与其对应的value值；键值key通常用于唯一地标识元素，而value值是一个对象，它的内容和键值key关联；
- unordered_map没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中；
- unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低；
- unordered_map实现了直接访问操作符（
operator[]），它允许使用key作为参数直接访问value； - 它只有单向迭代器。
4.2 unordered_map的使用
unordered_map的参数列表
头文件
#include <unordered_map>
模板参数列表
template< class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator< std::pair<const Key, T> > > class unordered_map;
- Key：容器中存储元素的类型；
- Hash：确定元素存储位置所用的哈希函数；
- KeyEqual：判断各个元素是否相等所用的函数；
- Allocator：指定分配器对象的类型（暂不做了解）。
unordered_map的构造器
| 函数声明 | 功能介绍 |
unordered_map (const Compare& comp = Compare(), const Allocator& = Allocator()); |
构造空的unordered_map |
unordered_map (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); |
用[first, last)区 间中的元素构造 unordered_map |
unordered_map (const map<Key,Compare,Allocator>& x); |
unordered_map的拷贝构造 |
示例：
void unordered_map_test() { unordered_map<int, string> um1; // 构造一个键值对为<int, string>的空容器 unordered_map<int, string> um2(um1.begin(), um1.end()); // 迭代器区间构造 unordered_map<int, string> um3(um1); // 拷贝构造 }
unordered_map的常用接口
| 函数声明 | 功能 |
pair<iterator,bool> insert ( const value_type& x ) |
在map中插入键值对x，注意x是一个键值对，返回值也是键值对。iterator代表新插入元素的位置，bool代表插入成功。 |
void erase ( iterator position ) |
删除position位置的元素 |
size_type erase ( const key_type& x ) |
删除键值key为x的元素，返回删除元素的个数 |
void erase ( iterator first, iterator last ) |
删除[first, last)之间所有元素 |
iterator find ( const key_type& x ) |
查找键值key为x的元素，找到则返回该元素的迭代器，否则返回end() |
const_iterator find ( const key_type& x ) const |
查找键值key为x的元素，找到则返回该元素的const迭代器，否则返回cend() |
size_type size() const |
返回unordered_map容器中有效元素的个数 |
bool empty ( ) const |
判断unordered_map容器是否为空 |
void clear ( ) |
清空unordered_map容器 |
void swap ( unordered_map<Key,T,Compare,Allocator>& mp ) |
交换两个unordered_map容器的数据 |
size_type count ( const key_type& x ) const |
返回键值key为x的元素的个数 |
mapped_type& operator[] (const key_type& k) |
返回键值key为x对应的value |
在常用的接口中，unordered_map新增了一个操作符[]，它可以根据传入的key找到对应的value。
[key]表示返回key对应的value的==引用==，所以我们不仅可以通过operator[]查找，还能修改key对应的value。
- 如果key不存在：operator[]会调用默认构造函数创建一个匿名对象用来构造一个pair，然后插入，接着才会返回它的引用；
- 如果key存在：返回键值为key的元素对应的pair对象的引用。
迭代器相关
| 成员函数 | 功能 |
iterator begin() |
获取容器中第一个元素的正向迭代器 |
iterator end() |
获取容器中最后一个元素下一个位置的正向迭代器 |
const_iterator cbegin() |
同上，但是不能修改迭代器对应的元素 |
const_iterator end() |
同上，但是不能修改迭代器对应的元素 |
unordered_map没有反向迭代器。
示例
void unordered_map_test2() { unordered_map<int, string> um; um.insert(make_pair(1, "一")); um.insert(make_pair(2, "二")); um.insert(make_pair(3, "三")); um.insert(make_pair(4, "四")); // 迭代器遍历 unordered_map<int, string>::iterator it = um.begin(); while (it != um.end()) { cout << "<" << it->first << ", " << it->second << ">" << endl; it++; } cout << endl; // 删除key=2的元素 um.erase(2); for (auto e : um) { cout << "<" << e.first << ", " << e.second << ">" << endl; } cout << endl; // 查找key=3的元素 auto pos = um.find(3); if(pos != um.end()) { cout << "<" << pos->first << ", " << pos->second << ">" << endl; } // 清空容器 um.clear(); // 容器判空 cout << um.empty() << endl; }
输出
<4, 四>
< 3, 三>
<2, 二>
<1, 一>
<4, 四>
< 3, 三>
<1, 一>
< 3, 三>
1
5. unordered_multimap
unordered_multimap容器与unordered_map容器的唯一区别就是它允许键值冗余，即unordered_multimap容器当中存储的键值对的key值是可以重复的。因此，两种容器的find和count的意义也有所区别。
5.1 成员函数的区别
find
| find | 功能 |
| unordered_map | 返回key值为x的元素的迭代器 |
| unordered_multimap | 返回哈希表中第一个key值为x的元素的迭代器 |
count
| count | 功能 |
| unordered_map | 键值key为x的元素存在则返回1，不存在则返回0 |
| unordered_multimap | 返回键值key为x的元素个数 |
5.2 示例
void unordered_multimap_test() { unordered_multimap<int, string> umm; umm.insert(make_pair(1, "一")); umm.insert(make_pair(1, "first")); umm.insert(make_pair(1, "one")); for (auto e : umm) { cout << "<" << e.first << ", " << e.second << ">" << endl; } cout << endl; }
输出
<1, 一>
<1, first>
<1, one>
