【C++】unordered_set和unordered_map介绍及使用【附OJ题】

目录

一、unordered_set和unordered_map的介绍和使用 

1、介绍

 2、使用及与set和map的区别

3、O（logN）和 O（1）的效率对比 

二、力扣OJ题

1、重复N次的元素

2、两个数组的交集

---

一、unordered_set和unordered_map的介绍和使用 

1、介绍

 unordered_set和unordered_map是c++11才引入的 

unordered_set 和unordered_map都不支持修改（这一点和set和map一样，本质是key值不允许修改），不然底层哈希结构就乱了，且对于数据不会自动排序，并且他不支持双向迭代器，其是单向迭代器

从命名风格来看，JAVA中的unordered_set称为HashSet，set称为TreeSet；unordered_map称为HashMap，map称为TreeMap，因为一个底层是哈希表实现的，一个是红黑树实现的

---

 2、使用及与set和map的区别

使用下 unordered_set和unordered_map，并对比set和map

#include
#include
#include
#include
#include
#include
using namespace std;
 
void test_unordered_set_map()
{
	cout << "测试unordered_set:" << endl;
	//unordered_set能去重，但不能排序
	unordered_set<int> us;
	us.insert(4);
	us.insert(2);
	us.insert(1);
	us.insert(5);
	us.insert(6);
	us.insert(2);
 
	//unordered_set的迭代器遍历
	unordered_set<int>::iterator it = us.begin();
	while (it != us.end())
	{
		//*it = 4;//报错，因为不能修改
		cout << *it << " ";  // 4 2 1 5 6
		++it;
	}
	cout << endl;
 
	cout << "测试set:" << endl;
	//set能去重，也能排序
	set<int> s;
	s.insert(4);
	s.insert(2);
	s.insert(1);
	s.insert(5);
	s.insert(6);
	s.insert(2);
 
	//set的迭代器遍历
	set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";  //1 2 4 5 6
		++sit;
	}
	cout << endl;
 
	cout << "测试unordered_map" << endl;
	unordered_map dict;
	dict.insert(make_pair("sort", "排序"));
	dict["string"] = "字符串";//第一次operator[]相当于插入操作
	dict.insert(make_pair("left", "左边"));
	unordered_map::iterator dit = dict.begin();
	while (dit != dict.end())
	{
		cout << dit->first << ":" << dit->second << endl;
		++dit;
	}
 
	cout << "测试map:" << endl;
	map dicts;
	dicts.insert(make_pair("sort", "排序"));
	dicts["string"] = "字符串";//第一次operator[]相当于插入操作
	dicts.insert(make_pair("left", "左边"));
	map::iterator dits = dicts.begin();
	while (dits != dicts.end())
	{
		cout << dits->first << ":" << dits->second << endl;
		++dits;
	}
}
 
int main()
{
	test_unordered_set_map();
 
	return 0;
}

运行结果如下：

总结： 

---

3、O（logN）和 O（1）的效率对比 

注：O（1）是常数次，不是说的就是1次 

O（logN）和 O（1）差别不算大，但是累计起来就有差别了，所以这也是引入unordered_set和unordered_map的原因

利用代码测试下两者的效率差异：

void test_efficiency()
{
	unordered_set<int> us;
	set<int> s;
 
	const int n = 1000000;
	vector<int> v;
	v.reserve(n);//需要初始化，才用resize，resize是开空间+初始化，reserve是开空间
	srand((unsigned int)time(0));//设立随机数种子，使每次运行程序都产生不同的数
	for (size_t i = 0; i < n; ++i)
	{
		v.push_back(rand());//插入每次生成的随机数
	}
	//测试unordered_set insert
	size_t begin1 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		us.insert(v[i]);
	}
	size_t end1 = clock();
	cout << "unordered_set insert:" << end1 - begin1 << endl;
 
	//测试set insert
	size_t begin2 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		s.insert(v[i]);
	}
	size_t end2 = clock();
	cout << "set insert:" << end2 - begin2 << endl;
 
	//测试unordered_set find
	size_t begin3 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		us.find(v[i]);
	}
	size_t end3 = clock();
	cout << "unordered_set find:" << end3 - begin3 << endl;
 
	//测试set find
	size_t begin4 = clock();
	for (size_t i = 0; i < n; ++i)
	{
		s.find(v[i]);
	}
	size_t end4 = clock();
	cout << "set find:" << end4 - begin4 << endl;
}

注：性能测试：要用release版本+多次测试取平均值

运行结果【10万个数据下】：

运行结果【100万个数据下】：

其实实际情况下，如果我们使用的环境支持C++11，unordered_set的查找效率会比set查找效率要高的 ，综合而言还是unordered_xxx的效率要高，进而说明了O（logN）和O（1）的效率差距

---

二、力扣OJ题

1、重复N次的元素

 思路：

这跟我们之前讲过的出现水果的次数的题差不多，利用map或unordered_map就可秒杀这道题了

class Solution {
public:
	int repeatedNTimes(vector<int>& nums) {
		//用map或unordered_map都行
		unordered_map<int, int> countMap;
		for (auto e : nums)
		{
			countMap[e]++;//利用operator[]，传入key，返回对应value再++
		}
 
		int N = nums.size() / 2;
		for (auto& kv : countMap)
		{
			if (kv.second == N)
			{	//若出现频率为N
				return kv.first;//返回key值，即nums中的数据
			}
		}
 
		return -1;//若不存在，返回一个值即可
	}
}

2、两个数组的交集

class Solution {
public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		//nums1和nums2的元素都要去重，不然最后结果可能出现重复数据
		
		//用unordered_set对nums1中的元素去重
		unordered_set<int> s1;
		for (auto e : nums1)
			s1.insert(e);
 
		//用unordered_set对nums2中的元素去重
		unordered_set<int> s2;
		for (auto e : nums2)
			s2.insert(e);
 
		//遍历s1,如果s1中某个元素在s2中出现过，即为交集
		vector<int> ret;
		for (auto e : s1)
		{
			if (s2.find(e) != s2.end())
				ret.push_back(e);
		}
 
		return ret;
	}
};