unordered_map和unordered_set的使用

未知陨落

已于 2024-12-08 21:18:52 修改

阅读量1.2k

点赞数 59

分类专栏： C++ 文章标签： c++ 开发语言 stl 容器 leetcode

于 2024-11-20 07:15:00 首次发布

本文链接：https://blog.csdn.net/w200514/article/details/143893886

版权

C++ 专栏收录该内容

28 篇文章

订阅专栏

一.unordered_map

二.unordered_set

三.相关OJ题

1.在长度为2N的数组中找出重复了N次的数

2.两个数组的交集

四.整体代码

一.unordered_map

unordered_map文档说明

unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value
在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同
在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中
unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value
它的迭代器至少是前向迭代器

void test_unordered_map()
{
	unordered_map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("vector", "数组"));
	dict.insert(make_pair("deque", "双端队列"));

	unordered_map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

二.unordered_set

unordered_set文档说明

void test_unordered_set()
{
	unordered_set<int> us;
	us.insert(4);
	us.insert(1);
	us.insert(3);
	us.insert(2);
	us.insert(5);

	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

unordered_set和unordered_map的使用与map和set基本相同,那么他们之间有什么区别和联系?

都可以实现key和key/value的搜索场景,功能和使用基本相同
map和set底层使用红黑树,遍历出来是有序的,增删查改的时间复杂度是O(log2N)
unordered_set和unordered_map底层使用的是哈希表,遍历出来是无序的,增删查改的时间复杂度是O(1)
map和set是双向迭代器,unordered_set和unordered_map是单向迭代器

我们可以通过下面的代码来测试他们之间性能的差异

void test_op()
{
	unordered_set<int> us;
	set<int> s;
	const int n = 1000000;
	vector<int> v;
	v.reserve(n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		v.push_back(rand());
	}

	size_t begin1 = clock();
	for (auto ch : v)
	{
		us.insert(ch);
	}
	size_t end1 = clock();

	size_t begin2 = clock();
	for (auto ch : v)
	{
		s.insert(ch);
	}
	size_t end2 = clock();

	size_t begin3 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		(void)us.find(v[i]);
	}
	size_t end3 = clock();

	size_t begin4 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		(void)s.find(v[i]);
	}
	size_t end4 = clock();

	size_t begin5 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		us.erase(v[i]);
	}
	size_t end5 = clock();

	size_t begin6 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		s.erase(v[i]);
	}
	size_t end6 = clock();

	cout << "unordered_set: " << end1 - begin1 << endl;
	cout << "set: " << end2 - begin2 << endl;
	cout << "unordered_set find: " << end3 - begin3 << endl;
	cout << "set find: " << end4 - begin4 << endl;
	cout << "unordered_set erase: " << end5 - begin5 << endl;
	cout << "set erase: " << end6 - begin6 << endl;
}

在Debug和Release下测试的结果可以看出unordered系列的性能是比较好的

三.相关OJ题

1.在长度为2N的数组中找出重复了N次的数

https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/description/

对于这道题是需要创建一个unordered_map来存储数组中的数,并记录每个数据的次数,如果次数为N的话,就输出

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_map<int,int> countMap;
        for(auto kv:nums)
        {
            countMap[kv]++;
        }

        size_t n=nums.size()/2;
        for(auto& e:countMap)
        {
            if(e.second==n)
                return e.first;
        }
        return -1;
    }
};

2.两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/description/

我们先使用两个unordered_set来存储两个数组中的数据,并将重复的去除,同时创建一个vector,遍历一个数组,如果在另一个中找到相同的数,就插入到vector中,最后输出vector中的数据即可

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //去除重复元素
        unordered_set<int> s1;
        for(auto e:nums1)
        {
            s1.insert(e);
        }

        //去除重复元素
        unordered_set<int> s2;
        for(auto e:nums2)
        {
            s2.insert(e);
        }

        vector<int> v;
        for(auto e:s1)
        {
            if(s2.find(e)!=s2.end())
            {
                v.push_back(e);
            }
        }
        return v;
    }
};

四.整体代码

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<set>
#include<time.h>
using namespace std;

void test_unordered_map()
{
	unordered_map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("string", "字符串"));
	dict.insert(make_pair("vector", "数组"));
	dict.insert(make_pair("deque", "双端队列"));

	unordered_map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

void test_unordered_set()
{
	unordered_set<int> us;
	us.insert(4);
	us.insert(1);
	us.insert(3);
	us.insert(2);
	us.insert(5);

	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

void test_op()
{
	unordered_set<int> us;
	set<int> s;
	const int n = 1000000;
	vector<int> v;
	v.reserve(n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		v.push_back(rand());
	}

	size_t begin1 = clock();
	for (auto ch : v)
	{
		us.insert(ch);
	}
	size_t end1 = clock();

	size_t begin2 = clock();
	for (auto ch : v)
	{
		s.insert(ch);
	}
	size_t end2 = clock();

	size_t begin3 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		(void)us.find(v[i]);
	}
	size_t end3 = clock();

	size_t begin4 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		(void)s.find(v[i]);
	}
	size_t end4 = clock();

	size_t begin5 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		us.erase(v[i]);
	}
	size_t end5 = clock();

	size_t begin6 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		s.erase(v[i]);
	}
	size_t end6 = clock();

	cout << "unordered_set: " << end1 - begin1 << endl;
	cout << "set: " << end2 - begin2 << endl;
	cout << "unordered_set find: " << end3 - begin3 << endl;
	cout << "set find: " << end4 - begin4 << endl;
	cout << "unordered_set erase: " << end5 - begin5 << endl;
	cout << "set erase: " << end6 - begin6 << endl;
}

int main()
{
	test_unordered_map();
	test_unordered_set();
	test_op();
	return 0;
}