C++STL详解（六）unordered_set&unordered_map介绍_unordered_set和unordered_map

前言

其实unordered_set&unordered_map和set、map的使用基本没有啥区别，会用set、map就肯定会用unordered_set&unordered_map

1.unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时的效率可达到$O(logN)$ ，即最差情况下需要比较红黑树的高度次，当树中的结点非常多时，查询效率也不理想。最好的查询是，进行常数的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

2.unordered_set&unordered_map

介绍

unordered_set 文档

unordered_map 文档

unordered_xxx 对比 set、map

总的来说，会用 set、map 就肯定会用 unordered_set 、unordered_map。

void test_set1()
{
    unordered_set<int> s;
    //set<int> s;
    s.insert(2);
    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(5);

    //unordered_set<int>::iterator it = s.begin();
    auto it = s.begin(); // unordered_set 只有单向迭代器，也就是没有rbegin、reend等等
    while (it != s.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl; // 2 3 1 5

    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl; // 2 3 1 5
}
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

set 的迭代器是双向迭代器，而 unordered_set 的是单向迭代器。

性能比较

一、有大量重复数据的情况

void test_op()
{
    int n = 10000000;
    vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        v.push_back(rand());  // 重复多
    }

    size_t begin1 = clock();
    set<int> s;
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    unordered_set<int> us;
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();

    cout << s.size() << endl;

    cout << "set insert:" << end1 - begin1 << endl;
    cout << "unordered_set insert:" << end2 - begin2 << 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

注意：rand 生成的伪随机数范围是有限制的，最大也就是 RAND_MAX 。

此时大体可以看出unordered_set的效率比set效率高。

二、大量随机数据的情况

void test_op()
{
    int n = 10000000;
    vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        v.push_back(rand() + i);  // 重复少
    }

    size_t begin1 = clock();
    set<int> s;
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    unordered_set<int> us;
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();

    cout << s.size() << endl;

    cout << "set insert:" << end1 - begin1 << endl;
    cout << "unordered_set insert:" << end2 - begin2 << 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

对于插入，数据量过大之后，unordered_set 效率反而不如 set。

void test_op()
{
    int n = 10000000;
    vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        //v.push_back(i);
        v.push_back(rand()+i);  // 重复少
        //v.push_back(rand());  // 重复多
    }

    size_t begin1 = clock();
    set<int> s;
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    unordered_set<int> us;
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();

    cout << s.size() << endl;

    cout << "set insert:" << end1 - begin1 << endl;
    cout << "unordered_set insert:" << end2 - begin2 << endl;

    size_t begin3 = clock();
    for (auto e : v)
    {
        s.find(e);
    }
    size_t end3 = clock();

    size_t begin4 = clock();
    for (auto e : v)
    {
        us.find(e);
    }
    size_t end4 = clock();
    cout << "set find:" << end3 - begin3 << endl;
    cout << "unordered_set find:" << end4 - begin4 << 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
39
40
41
42
43
44
45
46
47
48
49
50

Debug版本下，unordered_set的插入、查找、删除的效率都是较高的。

而在release版本下，查找的效率都被优化到了O(1)，其实也不难理解。一个O(logN)一个O(1)
除非数据量及其大，不然是很难看出明显区别的。

void test_op()
{
    int n = 10000000;
    vector<int> v;
    v.reserve(n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        //v.push_back(i);
        //v.push_back(rand()+i);  // 重复少
        //v.push_back(rand());  // 重复多
        v.push_back(rand()*rand());  
    }

    size_t begin1 = clock();
    set<int> s;
    for (auto e : v)
    {
        s.insert(e);
    }
    size_t end1 = clock();

    size_t begin2 = clock();
    unordered_set<int> us;
    for (auto e : v)
    {
        us.insert(e);
    }
    size_t end2 = clock();

    cout << s.size() << endl;

    cout << "set insert:" << end1 - begin1 << endl;
    cout << "unordered_set insert:" << end2 - begin2 << endl;

    size_t begin3 = clock();
    for (auto e : v)
    {
        s.find(e);
    }
    size_t end3 = clock();

    size_t begin4 = clock();
    for (auto e : v)
    {
        us.find(e);
    }
    size_t end4 = clock();
    cout << "set find:" << end3 - begin3 << endl;
    cout << "unordered_set find:" << end4 - begin4 << endl;

    size_t begin5 = clock();
    for (auto e : v)
    {
        s.erase(e);
    }
    size_t end5 = clock();

    size_t begin6 = clock();
    for (auto e : v)
    {
        us.erase(e);
    }
    size_t end6 = clock();
    cout << "set erase:" << end5 - begin5 << endl;
    cout << "unordered_set erase:" << end6 - begin6 << 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

就 erase 而言，unordered_set 的效率也是要高一点的。

总的来说，unordered_xxx 的效率还是挺不错的，不过因为底层是哈希实现，在查找上的优势是更大的。

unordered_multixxx

multi版本是允许键值冗余，也就是可以存相同的元素。

#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
	unordered_multiset<int> ums;
	//插入元素（允许重复）
	ums.insert(1);
	ums.insert(4);
	ums.insert(3);
	ums.insert(3);
	ums.insert(2);
	ums.insert(2);
	ums.insert(3);
	for (auto e : ums)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 3 2 2
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

同样，unordered_multimap 的find、count也是类似的。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
	unordered_multimap<int, string> umm;
	umm.insert(make_pair(2022, "吃饭"));
	umm.insert(make_pair(2022, "睡觉"));
	umm.insert(make_pair(2022, "敲代码"));
	for (auto e : umm)
	{
		cout << e.first << "->" << e.second << " ";
	}
	cout << endl; //2022->吃饭 2022->睡觉 2022->敲代码
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：由于unordered_multimap容器允许键值对的键值冗余，调用operator[]时，应该返回键值为key的哪一个键值对的value的引用存在歧义，因此在unordered_multimap容器当中没有实现operator[]

尾声