1.unordered_set系列的使用1.1 unordered_set和unordered_multiset参考文档参考文档1.2 unordered_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的功能高度相似只是底层结构不同有一些性能和使用差异这里我们只讲他们的差异部分。templateclassKey,// unordered_set::key_type/value_typeclassHashhashKey,// unordered_set::hasherclassPredequal_toKey,// unordered_set::key_equalclassAllocallocatorKey// unordered_set::allocator_typeclassunordered_set;1.3 unordered_set和set的使用差异• 查看文档我们会发现unordered_set的支持增删查且跟set的使用一模一样关于使用我们这里就不再赘述和演示了。• unordered_set和set的第一个差异是对key的要求不同set要求Key支持小于比较而unordered_set要求Key支持转成整形且支持等于比较要理解unordered_set的这个两点要求得后续我们结合哈希表底层实现才能真正理解也就是说这本质是哈希表的要求。• unordered_set和set的第二个差异是迭代器的差异set的iterator是双向迭代器unordered_set是单向迭代器其次set底层是红黑树红黑树是二叉搜索树走中序遍历是有序的所以set迭代器遍历是有序去重。而unordered_set底层是哈希表迭代器遍历是无序去重。• unordered_set和set的第三个差异是性能的差异整体而言大多数场景下unordered_set的增删查改更快一些因为红黑树增删查改效率是O(logN)而哈希表增删查平均效率是O(1)具体可以参看下面代码的演示的对比差异。pairiterator,boolinsert(constvalue_typeval);size_typeerase(constkey_typek);iteratorfind(constkey_typek);#includeunordered_set#includeunordered_map#includeset#includeiostreamusingnamespacestd;inttest_set2(){constsize_t N1000000;unordered_setintus;setints;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i){//v.push_back(rand()); // N比较大时重复值比较多v.push_back(rand()i);// 重复值相对少//v.push_back(i); // 没有重复有序}size_t begin1clock();for(autoe:v){s.insert(e);}size_t end1clock();coutset insert:end1-begin1endl;size_t begin2clock();us.reserve(N);for(autoe:v){us.insert(e);}size_t end2clock();coutunordered_set insert:end2-begin2endl;intm10;size_t begin3clock();for(autoe:v){autorets.find(e);if(ret!s.end()){m1;}}size_t end3clock();coutset find:end3-begin3-m1endl;intm20;size_t begin4clock();for(autoe:v){autoretus.find(e);if(ret!us.end()){m2;}}size_t end4clock();coutunorered_set find:end4-begin4-m2endl;cout插入数据个数s.size()endl;cout插入数据个数us.size()endlendl;size_t begin5clock();for(autoe:v){s.erase(e);}size_t end5clock();coutset erase:end5-begin5endl;size_t begin6clock();for(autoe:v){us.erase(e);}size_t end6clock();coutunordered_set erase:end6-begin6endlendl;return0;}intmain(){test_set2();return0;}1.4 unordered_multimap/unordered_multiset• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似支持Key冗余。• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个方面的差异key的要求的差异iterator及遍历顺序的差异性能的差异。