为什么我们需要“无序”在学习 C 的过程中我们首先接触的关联式容器通常是 set 和 map。它们底层由红黑树实现能够自动将元素按照 key 的大小排序遍历时得到一个有序序列增删查改的时间复杂度稳定在 O(log N)。既然它又有序又稳定为什么还要引入 unordered_set 和 unordered_map 呢答案藏在哈希表里。对于大多数只需要“快速查找、快速插入、快速删除”的场景我们并不关心元素是否有序。哈希表能够在平均 O(1) 的时间内完成这些操作比 O(log N) 快得多。因此C11 引入了以哈希表为底层的无序关联容器它们就是 unordered_set、unordered_map、unordered_multiset 和 unordered_multimap。1. unordered_set 系列的使用1.1unordered_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);voidtest_set1(){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); // 无重复有序}// 1. 插入测试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;// 实际插入的元素个数cout插入数据个数(set): s.size()endl;cout插入数据个数(unordered_set): us.size()endlendl;// 2. 查找测试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();coutunordered_set find: end4-begin4 - m2endlendl;// 3. 删除测试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;}1.4 unordered_map和map的使⽤差异• 查看⽂档我们会发现unordered_map的⽀持增删查改且跟map的使⽤⼀模⼀样关于使⽤我们这⾥就不再赘述和演⽰了。• unordered_map和map的第⼀个差异是对key的要求不同map要求Key⽀持⼩于⽐较⽽unordered_map要求Key⽀持转成整形且⽀持等于⽐较要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解也就是说这本质是哈希表的要求。• unordered_map和map的第⼆个差异是迭代器的差异map的iterator是双向迭代器unordered_map是单向迭代器其次map底层是红⿊树红⿊树是⼆叉搜索树⾛中序遍历是有序的所以map迭代器遍历是Key有序去重。⽽unordered_map底层是哈希表迭代器遍历是Key⽆序去重。• unordered_map和map的第三个差异是性能的差异整体⽽⾔⼤多数场景下unordered_map的增删查改更快⼀些因为红⿊树增删查改效率是O(logN) ⽽哈希表增删查平均效率是O(1) 具体可以参看下⾯代码的演⽰的对⽐差异。pairiterator,boolinsert(constvalue_typeval);size_typeerase(constkey_typek);iteratorfind(constkey_typek);mapped_typeoperator[](constkey_typek);1.5 unordered_multimap/unordered_multiset• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似⽀持Key冗余。• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异key的要求的差异iterator及遍历顺序的差异性能的差异。哈希相关接口桶与负载因子unordered_set 和 unordered_map 提供了许多与哈希表底层相关的接口虽然平常不常用但了解它们有助于理解性能调优。这些接口在文档中分为 Buckets 和 Hash policy 两组。4.1 Buckets桶相关• bucket_count()返回当前桶的总数。• max_bucket_count()系统允许的最大桶数。• bucket_size(n)第 n 个桶中元素的个数。• bucket(const key_type k)返回键 k 会被放在哪个桶桶索引。这些接口可以帮助你分析哈希分布是否均匀。例如遍历所有桶统计每个桶的大小如果发现个别桶特别长说明哈希函数不够均匀或者负载因子太高。4.2 Hash policy哈希策略• load_factor()当前负载因子计算公式为 size() / bucket_count()。• max_load_factor()获取或设置最大负载因子。当 load_factor() 超过该值时容器会自动rehash增加桶的数量并重新分配所有元素。• rehash(count)手动触发 rehash将桶数调整为至少 count。• reserve(n)为至少容纳 n 个元素预留桶。
为什么我们需要“无序”在学习 C 的过程中我们首先接触的关联式容器通常是 set 和 map。它们底层由红黑树实现能够自动将元素按照 key 的大小排序遍历时得到一个有序序列增删查改的时间复杂度稳定在 O(log N)。既然它又有序又稳定为什么还要引入 unordered_set 和 unordered_map 呢答案藏在哈希表里。对于大多数只需要“快速查找、快速插入、快速删除”的场景我们并不关心元素是否有序。哈希表能够在平均 O(1) 的时间内完成这些操作比 O(log N) 快得多。因此C11 引入了以哈希表为底层的无序关联容器它们就是 unordered_set、unordered_map、unordered_multiset 和 unordered_multimap。1. unordered_set 系列的使用1.1unordered_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);voidtest_set1(){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); // 无重复有序}// 1. 插入测试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;// 实际插入的元素个数cout插入数据个数(set): s.size()endl;cout插入数据个数(unordered_set): us.size()endlendl;// 2. 查找测试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();coutunordered_set find: end4-begin4 - m2endlendl;// 3. 删除测试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;}1.4 unordered_map和map的使⽤差异• 查看⽂档我们会发现unordered_map的⽀持增删查改且跟map的使⽤⼀模⼀样关于使⽤我们这⾥就不再赘述和演⽰了。• unordered_map和map的第⼀个差异是对key的要求不同map要求Key⽀持⼩于⽐较⽽unordered_map要求Key⽀持转成整形且⽀持等于⽐较要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解也就是说这本质是哈希表的要求。• unordered_map和map的第⼆个差异是迭代器的差异map的iterator是双向迭代器unordered_map是单向迭代器其次map底层是红⿊树红⿊树是⼆叉搜索树⾛中序遍历是有序的所以map迭代器遍历是Key有序去重。⽽unordered_map底层是哈希表迭代器遍历是Key⽆序去重。• unordered_map和map的第三个差异是性能的差异整体⽽⾔⼤多数场景下unordered_map的增删查改更快⼀些因为红⿊树增删查改效率是O(logN) ⽽哈希表增删查平均效率是O(1) 具体可以参看下⾯代码的演⽰的对⽐差异。pairiterator,boolinsert(constvalue_typeval);size_typeerase(constkey_typek);iteratorfind(constkey_typek);mapped_typeoperator[](constkey_typek);1.5 unordered_multimap/unordered_multiset• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似⽀持Key冗余。• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异key的要求的差异iterator及遍历顺序的差异性能的差异。哈希相关接口桶与负载因子unordered_set 和 unordered_map 提供了许多与哈希表底层相关的接口虽然平常不常用但了解它们有助于理解性能调优。这些接口在文档中分为 Buckets 和 Hash policy 两组。4.1 Buckets桶相关• bucket_count()返回当前桶的总数。• max_bucket_count()系统允许的最大桶数。• bucket_size(n)第 n 个桶中元素的个数。• bucket(const key_type k)返回键 k 会被放在哪个桶桶索引。这些接口可以帮助你分析哈希分布是否均匀。例如遍历所有桶统计每个桶的大小如果发现个别桶特别长说明哈希函数不够均匀或者负载因子太高。4.2 Hash policy哈希策略• load_factor()当前负载因子计算公式为 size() / bucket_count()。• max_load_factor()获取或设置最大负载因子。当 load_factor() 超过该值时容器会自动rehash增加桶的数量并重新分配所有元素。• rehash(count)手动触发 rehash将桶数调整为至少 count。• reserve(n)为至少容纳 n 个元素预留桶。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
