【C++】unordered_map和unordered_set的使用

羚羊角

发布于 2025-06-25 08:19:14

2570

unordered就是无序的，unordered_map和unordered_set 是C++11之后才有的容器，功能上和map/set基本相同，从底层看map和set是红黑树，unordered_map和unordered_set底层是哈希表。本篇也会着重讲解功能上的不同点。

1.unordered_set系列

unordered_set和unordered_multiset参考⽂档：<unordered_set> - C++ Reference

1.1 unordered_set类的介绍

unordered_set的声明如下。

Key就是unordered_set底层关键字的类型。
unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key转成整形的仿函数传给第⼆个模板参数。
unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数
unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第四个参数。
一般情况下，我们都不需要传后三个模板参数。

unordered_set底层是⽤哈希桶实现， 增删查平均效率是O(1) ，迭代器遍历 不再有序 ，为了跟set

区分，所以取名unordered_set。

#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
	unordered_set<int> s = { 4,5,6,2,3,1,7 };
	unordered_set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

遍历出来的结果不再有序。

前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不

同，有⼀些性能和使⽤的差异，这⾥我们只讲他们的差异部分。

set的详细介绍在：【C++】set和multiset的常用接口详解

1.2 unordered_set和set的差异

查看⽂档我们会发现unordered_set的⽀持增删查且跟set的使⽤⼀模⼀样，关于使⽤我们这⾥就不

再赘述和演⽰了。

迭代器的差异：

set的iterator是双向迭代器，unordered_set 是单向迭代器，只支持++和--。
其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

unordered_set<int> s = { 4,5,5,5,6,2,1,3,1,1,1,7 };//有重复值
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
	cout << *it << " ";
	++it;
}
cout << endl;

性能的差异： 整体⽽⾔⼤多数场景下，unordered_set的增删查改更快⼀些，因为红⿊树增删查改效率是 O(logN)，⽽哈希表增删查平均效率是 O(1)，具体可以参看下⾯代码的演⽰的对⽐差异。

int main()
{
	const size_t N = 1000000;
	unordered_set<int> us;
	set<int> s;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N比较大时，重复值比较多
		v.push_back(rand() + i); // 重复值相对少
		//v.push_back(i); // 没有重复，有序
	}
	// 21:15
	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e); //插入到set
	}
	size_t end1 = clock();
	cout << "set insert:" << end1 - begin1 << endl;
	size_t begin2 = clock();
	us.reserve(N);
	for (auto e : v)
	{
		us.insert(e); //插入到unordered_set
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;
	cout << endl;
	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl << endl;
	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();
	cout << "set erase:" << end5 - begin5 << endl;
	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl;
	return 0;
}

先测重复值少的情况。

重复值很多时，unordered系列的优势更明显。

可以看出unordered系列的效率是更高的，所以如果以后需要容器遍历的数据是有序的，就用set或map，没有这个需求，就用unordered系列的map和set。

使用要求的差异： set要求Key⽀持⼩于的或大于的⽐较，⽽unordered_set要求Key⽀持 转成整形 且 ⽀持等于⽐较 ，要理解unordered_set的这个要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

1.3 其他接口介绍

文档中下面这些接口是我们之前没接触过的。

bucket_count就是返回有多少个哈希桶。

这是Release下，产生1千万个数据的哈希桶数量。

bucket_size可以获取每个桶的大小，我们可以找到最大的桶的大小。

size_t max = 0;
for (int i = 0; i < us.bucket_count(); i++)
{
	if (us.bucket_size(i) > max)
		max = us.bucket_size(i);
}
cout << "最大的桶大小：" << max << endl << endl;

load_factor，就是负载因子，rehash就是扩容，和这个reserve差不多，但还是有区别的，在这里如果要扩容，尽量选择rehash。

我们先用一下load_factor和max_load_factor。

cout << us.load_factor() << endl;
cout << us.max_load_factor() << endl << endl;

前面的代码，erase之前测负载因子。

这是Release下，产生1千万个数据的负载因子和最大负载因子。

这是Release下，产生8百万个数据的负载因子和最大负载因子。

负载因子接近1，快扩容了。

2.unordered_map系列

unordered_map和unordered_multimap的相关文档：<unordered_map> - C++ Reference

前⾯部分我们已经学习了map容器的使⽤，map和unordered_smap的功能⾼度相似，只是底层结构不同，有⼀些性能和使⽤的差异，这⾥我们只讲他们的差异部分。

map的详细讲解在：【C++】map和multimap的常用接口详解

unordered_map和map的差异就是unordered_set和set的那三个差异，差不多的。

本篇介绍就是这么多，我们下篇见~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-06-24，如有侵权请联系 cloudcommunity@tencent.com 删除

map

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度