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; }
