目录
一.unordered_set系列
1.1unordered_set类的介绍
1.2unordered_set与set的差异
二.unordered_map的系列
三.unordered_multimap/unordered_multiset
一.unordered_set系列
1.1unordered_set类的介绍
• unordered_set的声明如下,Key就是unordered_set底层关键字的类型
• unordered_set默认要求Key支持转换为整形,如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数
• unordered_set默认要求Key支持比较相等,如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数
• unordered_set底层存储数据的内存是从空间配置器申请的,如果需要可以自己实现内存池,传给第四个参数。
• 一般情况下,我们都不需要传后三个模板参数
• unordered_set底层是用哈希桶实现,增删查平均效率是O(1) ,迭代器遍历不再有序,为了跟set区分,所以取名unordered_set。
• 在我的上一篇博客里我说了set容器的使用,set和unordered_set的功能高度相似,只是底层结构不同。
1.2unordered_set与set的差异
• unordered_set和set的第一个差异是对key的要求不同,set要求Key支持小于比较,而unordered_set要求Key支持转成整形且支持等于比较。
• unordered_set和set的第二个差异是迭代器的差异,set的iterator是双向迭代器,unordered_set是单向迭代器,其次set底层是红黑树,红黑树是二叉搜索树,走中序遍历是有序的,所以set迭代器遍历是有序+去重。而unordered_set底层是哈希表,迭代器遍历是无序+去重。
• unordered_set和set的第三个差异是性能的差异,整体而言大多数场景下,unordered_set的增删查改更快一些,因为红黑树增删查改效率是O(logN),而哈希表增删查平均效率是 O(1)。
可以用下面的代码来看set与unordered_set 的差异
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<set>
using namespace std;
void test1()
{int 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); // 没有重复,有序}//测试set的插入size_t begin1 = clock();for (auto e : v){s.insert(e);} size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;//测试unordered_set的插入size_t begin2 = clock();us.reserve(N);for (auto e : v){us.insert(e);} size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;//测试set的查找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;//测试unordered_set的查找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;cout << "插入数据个数:" << s.size() << endl;cout << "插入数据个数:" << us.size() << endl << endl;//测试set的删除size_t begin5 = clock();for (auto e : v){s.erase(e);} size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;//测试unordered_set的删除size_t begin6 = clock();for (auto e : v){us.erase(e);} size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl << endl;}
int main()
{test1();return 0;
}
二.unordered_map的系列
• unordered_map和map的第一个差异是对key的要求不同,map要求Key支持小于比较,而unordered_map要求Key支持转成整形且支持等于比较。
• unordered_map和map的第二个差异是迭代器的差异,map的iterator是双向迭代器,unordered_map是单向迭代器,其次map底层是红黑树,红黑树是二叉搜索树,走中序遍历是有序的,所以map迭代器遍历是Key有序+去重。而unordered_map底层是哈希表,迭代器遍历是Key无序+去重。
• unordered_map和map的第三个差异是性能的差异,整体而言大多数场景下,unordered_map的增删查改更快一些,因为红黑树增删查改效率是O(logN),而哈希表增删查平均效率是 O(1)。
三.unordered_multimap/unordered_multiset
• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似,支持Key冗余。
• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个方面的差异,key的要求的差异,iterator及遍历顺序的差异,性能的差异。
其实这里的使用的话除了上面的那些差异,其他的就把unordered_set当做set来用就行。