【C++】map/set 与 unordered_map/set 的核心区别与选型

我不是呆头

发布于 2025-12-20 15:02:11

160

引言

本文深度解析了C++中map/set与unordered_map/unordered_set这两类关联容器的核心区别。基于红黑树实现的有序容器提供稳定的O(log n)操作复杂度与元素自动排序，适用于需要顺序遍历和范围查询的场景；而基于哈希表实现的无序容器则在平均情况下提供O(1)的极致访问速度，适合对单点操作性能要求极高且不关心元素顺序的应用。

一、核心区别

特性	map / set	unordered_map / unordered_set
底层数据结构	红黑树	哈希表
元素排序	元素自动排序（按 key 升序）	元素无序存储（顺序不确定）
时间复杂度	增删查：O(log n)	平均情况增删查：O(1) 最坏情况增删查：O(n)
迭代器功能	提供正向和反向迭代器迭代顺序是确定的、有序的	通常只提供正向迭代器迭代顺序是不确定的、无序的
是否需要哈希函数	不需要，只需定义 < 比较运算符	必须为 key 定义有效的哈希函数
自定义 Key 要求	需要定义 < 运算符或传入自定义比较器	需要定义 == 运算符和 std::hash 特化（或自定义哈希函数）
内存占用	通常较高（树节点结构开销）	通常较低，但存在哈希桶的数组开销和可能的负载因子浪费
适用场景	1. 需要元素有序遍历2. 需要按顺序进行范围查询3. 需要稳定性和可预测的性能	1. 对单点访问速度要求极高2. 不关心元素顺序3. 哈希函数分布均匀，能避免最坏情况

选择 map/set 当：你需要元素始终保持有序，或者需要频繁地进行范围查询（如“找出所有年龄在20到30之间的人”），或者你无法为一个复杂的 key 设计出高效的、分布均匀的哈希函数。
选择 unordered_map/unordered_set 当：你的主要操作是快速的单点查找、插入和删除，并且元素的顺序完全无关紧要。在大多数情况下，如果你的 key 是基础类型或标准库字符串，并且不要求顺序，unordered_ 版本会提供更好的性能。

二、性能对比

说到一个容器的性能，我们最关心的实际就是该容器增删查改的效率。我们可以通过下列代码测试set容器和unordered_set容器insert、find以及erase的效率。

效率的对比肯定是需要对比执行相应操作的时间，这里我们来介绍一下相关的类型和函数：

cloxk_t clock_t 是一个算术类型（通常是 long 或 long long），用于存储处理器时间值。
clock() clock() 返回的值单位是时钟滴答，要转换为秒，需要除以CLOCKS_PER_SEC宏。

clock() 函数 + clock_t 类型的主要作用：测量程序使用的 CPU 时间（处理器时间）。

//红黑树/哈希表的性能对比
#include<iostream>
#include<vector>

#include<time.h>
#include<set>
#include<unordered_set>

using namespace std;

int main()
{
	int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(NULL));
	//随机生成N个数字
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	/****************插入效率测试****************/
	//将这N个数插入set容器
	set<int> s;
	clock_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	clock_t end1 = clock();

	//将这N个数插入unordered_set容器
	unordered_set<int> us;
	clock_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	clock_t end2 = clock();

	//分别输出插入set容器和unordered_set容器所用的时间
	cout << "set insert: " << end1 - begin1 << endl;
	cout << "unordered_set insert: " << end2 - begin2 << endl;

	/****************查找效率测试****************/
	//在set容器中查找这N个数
	clock_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	clock_t end3 = clock();

	//在unordered_set容器中查找这N个数
	clock_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	clock_t end4 = clock();

	//分别输出在set容器和unordered_set容器中查找这N个数所用的时间
	cout << "set find: " << end3 - begin3 << endl;
	cout << "unordered_set find: " << end4 - begin4 << endl;

	/****************删除效率测试****************/
	//将这N个数从set容器中删除
	clock_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	clock_t end5 = clock();

	//将这N个数从unordered_set容器中删除
	clock_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	clock_t end6 = clock();

	//分别输出将这N个数从set容器和unordered_set容器中删除所用的时间
	cout << "set erase: " << end5 - begin5 << endl;
	cout << "unordered_set erase: " << end6 - begin6 << endl;
	return 0;
}

随机数的生成代码+原理解析<----------请点击

当N为100000时，set容器和unordered_set容器增删查改的效率差异并不大，在Debug版本下的测试结果如下：

在Release版本下，set容器和unordered_set容器对1000个数做增删查改操作所用的时间更是被优化到了接近0毫秒。

注意：这里给出的N值仅作参考，在不同的测试环境下可能不同。

总结

根据测试结果可以得出以下结论：

当处理数据量小时，map/set容器与unordered_map/unordered_set容器增删查改的效率差异不大。
当处理数据量大时，map/set容器与unordered_map/unordered_set容器增删查改的效率相比，unordered系列容器的效率更高。 因此，当处理数据量较大时，建议选用对应的unordered_set/unordered_map容器。