map/set与unordered_map/unordered_set的区别

map/set与unordered_map/unordered_set虽然它们的接口函数名称近乎一致但是它们的底层实现却大不相同

容器	底层数据结构	是否有序	实现版本	增删查改的效率	迭代器类型
unordered_map/unordered_set	哈希表/散列表	遍历无序	C++11	O(1)	单向迭代器
map/set	红黑树	遍历有序	C++98	O(logN)	双向迭代器

map/set与unordered_map/unordered_set的性能测试

我们这里分别使用不同的数据量对这两种容器进行增删查改的效率测试

我们使用set和unordered_set来进行测试

首先我们生成N个随机数将它们插入到一个容器vector里

代码标识如下

	vector<int> v;v.reserve(N);srand((unsigned int)time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());}

这里利用我们之前学过的一个知识点我们使用const修饰的全局变量N

在这里插入图片描述

插入效率测试

代码表示如下

我们分别使用两个时间标志来记录它们插入的时间

	// 插入 set<int> s;clock_t begin1 = clock();for (auto x : v){s.insert(x);}clock_t end1 = clock();unordered_set<int> us;clock_t begin2 = clock();for (auto x : v){us.insert(x);}clock_t end2 = clock();

查找效率测试

	// 查找clock_t begin3 = clock();for (auto x : v){s.find(x);}clock_t end3 = clock();clock_t begin4 = clock();for (auto x : v){us.find(x);}clock_t end4 = clock();

删除效率测试

	// 删除clock_t begin5 = clock();for (auto x : v){s.erase(x);}clock_t end5 = clock();clock_t begin6 = clock();for (auto x : v){us.erase(x);}

测试数为10000

debug

在这里插入图片描述

release

在这里插入图片描述

我们可以发现在小数据的时候它们之间的效率差别不大在release版本下都被优化的很好

测试数为10000000

debug

在这里插入图片描述

realease

在这里插入图片描述
我们可以发现在测试数量巨大的时候它们之间的效率就开始出现差别了

unordered系列的效率明显快于set 尤其是查找操作

测试结论

当测试数据较小时选择map/set容器与unordered_map/unordered_set容器都可以
当测试数据较大时 unordered_map/unordered_set容器的效率明显高于map/set

但是unordered_map/unordered_set容器对比map/set有一个缺点就是它是无序的

所以说当我们要排序的时候冒着牺牲效率的代价也要选择map/set

测试代码

大家可以自行修改N的值进行测试

#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include<set>
#include<unordered_set>
#include<iostream>
using namespace std;
const int N = 10000000;int main()
{vector<int> v;v.reserve(N);srand((unsigned int)time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());}// 插入 set<int> s;clock_t begin1 = clock();for (auto x : v){s.insert(x);}clock_t end1 = clock();unordered_set<int> us;clock_t begin2 = clock();for (auto x : v){us.insert(x);}clock_t end2 = clock();//分别输出插入set容器和unordered_set容器所用的时间cout << "set insert: " << end1 - begin1 << endl;cout << "unordered_set insert: " << end2 - begin2 << endl;// 查找clock_t begin3 = clock();for (auto x : v){s.find(x);}clock_t end3 = clock();clock_t begin4 = clock();for (auto x : v){us.find(x);}clock_t end4 = clock();//分别输出在set容器和unordered_set容器中查找这N个数所用的时间cout << "set find: " << end3 - begin3 << endl;cout << "unordered_set find: " << end4 - begin4 << endl;// 删除clock_t begin5 = clock();for (auto x : v){s.erase(x);}clock_t end5 = clock();clock_t begin6 = clock();for (auto x : v){us.erase(x);}clock_t end6 = clock();//分别输出将这N个数从set容器和unordered_set容器中删除所用的时间cout << "set erase: " << end5 - begin5 << endl;cout << "unordered_set erase: " << end6 - begin6 << endl;return 0;
}