C++ STL 无序容器详解：unordered_map和unordered_set｜set/map 与 unordered系列 性能对比与场景选型

目录引言1.unordered_map和unordered_multiset参考文档2.unordered_set类的介绍3.unordered_set和set的使用差异4.unordered_map和map的使用差异5.unordered_multimap和unordered_multiset6.unordered_xxx的哈希相关接口7.unordered系列容器结语引言提示阅读本文前需要掌握setmap的使用————C STL 关联式容器万字详解set、multiset、map、multimap接口用法 易错点 力扣真题实战-CSDN博客C11 标准新增了一类无序容器unordered_set、unordered_map、unordered_multiset、unordered_multimap。 在这之前我们已经学习过 set、map、multiset、multimap这类有序容器底层依托红黑树实现而 unordered 系列容器底层采用哈希表二者接口高度重合很多初学者很容易混淆不知道业务场景该如何选择。本文不会重复讲解容器基础增删查用法重点横向对比有序容器红黑树与无序容器哈希表核心区别、适用场景同时附带性能测试直观体现两者效率差距帮大家理清什么时候选 set/map什么时候优先 unordered_set/unordered_map。话不多说直接进入正文 ————1.unordered_map和unordered_multiset参考文档unordered_set - C Reference这类容器功能和之前讲解的 map、set、multiset、multimap 高度相似基本上掌握 set 的用法就能上手 unordered_set。核心区别体现在底层数据结构unordered 系列容器底层为哈希表map、set 等有序容器底层采用红黑树。头文件——unordered_set2.unordered_set类的介绍unordered_set 的声明如下Key 代表 unordered_set 底层关键字的类型unordered_set 默认要求 Key 能够转换成整型unordered_set 默认需要提供哈希函数将 Key 映射为 size_t 类型哈希值。若类型不满足该要求或是想要自定义哈希规则可以自行实现将 Key 转为整型的仿函数传入第二个模板参数。unordered_set 默认要求 Key 支持相等比较。如果不满足该条件或是需要自定义相等判断逻辑可以自行实现 Key 相等比较的仿函数传入第三个模板参数。unordered_set 底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第四个参数。一般情况下我们都不需要传后三个模板参数unordered_set 底层是用哈希桶实现增删查平均效率是O(1)迭代器遍历结果不再有序为了跟 set 区分所以取名 unordered_set。此前我们已经学习过 set 容器的使用set 和 unordered_set 功能高度相似差异主要来自底层结构同时带来性能与使用场景上的区别下文只重点讲解二者的差异部分。3.unordered_set和set的使用差异查看文档可以发现unordered_set 同样支持增、删、查接口使用方式和 set 几乎一致基础用法这里就不再赘述与演示。pairiterator,bool insert ( const value_type val ); size_type erase ( const key_type k ); iterator find ( const key_type k );unordered_set 和 set 的第一个差异对 Key 类型的要求不同。set 要求 Key 支持小于比较unordered_set 要求 Key 能够生成哈希整型值并且支持相等比较。想要理解这两点约束需要后续结合哈希表底层原理学习本质上这是哈希表结构带来的要求。unordered_set 和 set 的第二个差异迭代器类型与遍历特性。set 的迭代器是双向迭代器unordered_set 的迭代器是前向迭代器单向迭代器。set 底层为红黑树二叉搜索树中序遍历结果有序因此 set 遍历表现为【有序 自动去重】unordered_set 底层是哈希表遍历结果【无序 自动去重】。unordered_set 和 set 的第三个差异性能表现。绝大多数场景下 unordered_set 增删查改速度更快。红黑树增删查时间复杂度为 O(logN)哈希表增删查平均时间复杂度为 O(1)性能差异可以参考下方测试代码演示。注哈希表仅为平均 O (1)极端哈希冲突场景有序情况下下性能会退化至 O (N)如果业务必须有序优先选择 set不要盲目使用 unordered_set。#includeunordered_set #includeset #includevector #includeiostream #includecstdlib #includectime using namespace std; int test_set2() { const size_t N 1000000; unordered_setint us; setint s; vectorint v; v.reserve(N); srand((unsigned int)time(0)); // 三种测试数据按需切换 for (size_t i 0; i N; i) { //v.push_back(rand()); // 随机数重复值较多 v.push_back(rand() i); // 随机偏移重复值较少 //v.push_back(i); // 有序无重复数据 } // 插入性能测试 clock_t begin1 clock(); for (auto e : v) { s.insert(e); } clock_t end1 clock(); cout set insert time: end1 - begin1 endl; clock_t begin2 clock(); us.reserve(N); // 提前开辟空间避免多次rehash影响测试 for (auto e : v) { us.insert(e); } clock_t end2 clock(); cout unordered_set insert time: end2 - begin2 endl; // 查找性能测试 int m1 0; clock_t begin3 clock(); for (auto e : v) { auto ret s.find(e); if (ret ! s.end()) { m1; } } clock_t end3 clock(); cout set find time: end3 - begin3 - hit count: m1 endl; int m2 0; clock_t begin4 clock(); for (auto e : v) { auto ret us.find(e); if (ret ! us.end()) { m2; } } clock_t end4 clock(); cout unordered_set find time: end4 - begin4 - hit count: m2 endl; cout set 有效元素个数 s.size() endl; cout unordered_set 有效元素个数 us.size() \n endl; // 删除性能测试 clock_t begin5 clock(); for (auto e : v) { s.erase(e); } clock_t end5 clock(); cout set erase time: end5 - begin5 endl; clock_t begin6 clock(); for (auto e : v) { us.erase(e); } clock_t end6 clock(); cout unordered_set erase time: end6 - begin6 \n endl; return 0; } int main() { test_set2(); return 0; }4.unordered_map和map的使用差异unordered_map 和 map 的区别逻辑与 unordered_set 和 set 的区别完全一致。查看文档可以发现unordered_map 同样支持增、删、查接口使用方式和 map 几乎一致基础用法这里就不再赘述与演示。pairiterator,bool insert ( const value_type val ); size_type erase ( const key_type k ); iterator find ( const key_type k ); mapped_type operator[] ( const key_type k );unordered_map 和 map 的第一个差异对 Key 类型的要求不同。map 要求 Key 支持小于比较unordered_map 要求 Key 能够生成哈希整型值并且支持相等比较。想要理解这两点约束需要后续结合哈希表底层原理学习本质上这是哈希表结构带来的要求。unordered_map 和 map 的第二个差异迭代器类型与遍历特性。map 的迭代器是双向迭代器unordered_map 的迭代器是前向迭代器单向迭代器。map 底层为红黑树二叉搜索树中序遍历结果有序因此map 遍历表现为【有序 Key自动去重】unordered_map 底层是哈希表遍历结果【无序 Key自动去重】。unordered_map 和 map 的第三个差异性能表现。绝大多数场景下 unordered_map 增删查改速度更快。红黑树增删查时间复杂度为 O(logN)哈希表增删查平均时间复杂度为 O(1)性能差异可以参考下方测试代码演示。注哈希表仅为平均 O (1)极端哈希冲突场景有序情况下下性能会退化至 O (N)如果业务必须有序优先选择 map不要盲目使用 unordered_map。5.unordered_multimap和unordered_multisetunordered_multimap /unordered_multiset 与 multimap /multiset 功能高度类似容器允许 Key 重复支持 Key 冗余。unordered_multimap /unordered_multiset 和 multimap /multiset 之间的差异同样分为三点对 Key 类型的要求、迭代器与遍历顺序特性、运行性能。6.unordered_xxx的哈希相关接口buckets和hash policy系列接口分别和哈希桶、负载因子相关。从日常开发使用的角度暂时不需要重点关注等后续学习哈希表底层原理之后再来理解这一组接口就会一目了然。7.unordered系列容器unordered 系列容器不支持 lower_bound、upper_bound 区间查找这是工程上非常关键的区别。set 依靠有序性可以高效区间检索哈希表做不到。重要提醒 unordered容器不要盲目无脑使用1. 需要区间查找、有序打印数据 → 只能选 set/map2. 数据极易产生大量哈希冲突时unordered性能会大幅下滑结语那么C unordered_set和unordered_map使用部分的内容就全部讲解完毕啦希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。