unordered_set和unordered_map的使用【STL】

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查找时效率可达到$O(lo{g}_{2}N)$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查找效率也不理想。效率最高的查找方式是：进行很少的比较次数就能够将元素找到，因此在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关联；
• unordered_set没有对按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_set将相同哈希值的键值对放在相同的桶中；
• unordered_set容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低；
• 它只有单向迭代器。

2.2 unordered_set的使用

unordered_set的模板参数列表

头文件

#include 
1

模板参数列表

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;
1
2
3
4
5
6
7

• Key：容器中存储元素的类型；
• Hash：确定元素存储位置所用的哈希函数；
• KeyEqual：判断各个元素是否相等所用的函数；
• Allocator：指定分配器对象的类型（暂不做了解）。

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);					 // 拷贝构造
}
1
2
3
4
5
6
7
8
9

unordered_set常用接口

迭代器相关

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
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

输出

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

count

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;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输出

4 5 2 2 7 1 1

4. unordered_map

4.1 unordered_map的介绍

通过查阅官方文档们可以知道unordered_map的特性：

• unordered_map是存储键值对的关联式容器，其允许通过key值快速的索引到与其对应的value值；键值key通常用于唯一地标识元素，而value值是一个对象，它的内容和键值key关联；

• unordered_map没有对按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中；

• unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低；

• unordered_map实现了直接访问操作符（operator[]），它允许使用key作为参数直接访问value；

• 它只有单向迭代器。

4.2 unordered_map的使用

unordered_map的参数列表

头文件

#include 
1

模板参数列表

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;
1
2
3
4
5
6
7

• Key：容器中存储元素的类型；
• Hash：确定元素存储位置所用的哈希函数；
• KeyEqual：判断各个元素是否相等所用的函数；
• Allocator：指定分配器对象的类型（暂不做了解）。

unordered_map的构造器

示例：

void unordered_map_test()
{
	unordered_map<int, string> um1; // 构造一个键值对为的空容器

	unordered_map<int, string> um2(um1.begin(), um1.end()); // 迭代器区间构造

	unordered_map<int, string> um3(um1); // 拷贝构造
}
1
2
3
4
5
6
7
8

unordered_map的常用接口

在常用的接口中，unordered_map新增了一个操作符[]，它可以根据传入的key找到对应的value。

[key]表示返回key对应的value的==引用==，所以我们不仅可以通过operator[]查找，还能修改key对应的value。

• 如果key不存在：operator[]会调用默认构造函数创建一个匿名对象用来构造一个pair，然后插入，接着才会返回它的引用；
• 如果key存在：返回键值为key的元素对应的pair对象的引用。

迭代器相关

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;
}
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

输出

<4, 四>

< 3, 三>

<2, 二>

<1, 一>

<4, 四>

< 3, 三>

<1, 一>

< 3, 三>

1

5. unordered_multimap

unordered_multimap容器与unordered_map容器的唯一区别就是它允许键值冗余，即unordered_multimap容器当中存储的键值对的key值是可以重复的。因此，两种容器的find和count的意义也有所区别。

5.1 成员函数的区别

find

count

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
2
3
4
5
6
7
8
9
10
11
12

输出

<1, 一>

<1, first>

<1, one>