unordered_map 与 unordered_set 的使用前言1. unordered_set 的基本特性与去重无序演示2. unordered_set 类的模板参数剖析3. unordered_set 与 set 的核心差异对比4. unordered_map 与 map 的核心差异对比5. 性能实测代码分析6. 完整源码展示7. 实例演示总结前言在 C STL 中关联式容器是日常开发中不可或缺的利器。此前我们已经学习了基于红黑树的 set 和 map它们能够保证元素有序且支持高效的对数时间复杂度操作。而今天我们要探索的是基于哈希表实现的无序关联式容器unordered_set 与 unordered_map。我们将结合具体的测试代码深入剖析它们的行为特征、核心差异以及性能表现。unordered_set 的参考文档1. unordered_set 的基本特性与去重无序演示首先我们通过一段直观的代码来观察 unordered_set 的基本行为。voidtest_set1(){unordered_setints{3,1,6,7,8,2,1,1,5,6,7,6};unordered_setint::iterator its.begin();while(it!s.end()){cout*it ;it;}coutendl;}⭐ 语法细节与行为机制去重Deduplication从初始化列表 { 3,1,6,7,8,2,1,1,5,6,7,6 } 可以看出其中包含了大量的重复元素如多个 1 和 6。但最终存入 unordered_set 后所有重复值都会被自动过滤只保留一个。无序Unordered通过迭代器遍历输出时元素的顺序并不是按从小到大的升序排列也和初始化的顺序无关而是由底层哈希函数计算出的哈希地址决定的。2. unordered_set 类的模板参数剖析unordered_set 的类模板声明如下templateclassKey,// unordered_set::key_type/value_typeclassHashhashKey,// unordered_set::hasherclassPredequal_toKey,// unordered_set::key_equalclassAllocallocatorKey// unordered_set::allocator_typeclassunordered_set;⭐ 语法细节与行为机制Key底层关键字的类型。Hash第二个模板参数是一个仿函数默认要求 Key 支持转换为整型通过 std::hash。Pred第三个模板参数是用于比较两个 Key 是否相等的仿函数默认使用 std::equal_to。Alloc第四个模板参数是空间配置器。实际开发建议在绝大多数常规应用场景下我们都不需要手动传递后三个模板参数直接使用默认值即可。3. unordered_set 与 set 的核心差异对比虽然 unordered_set 的核心接口如 insert、erase、find与 set 完全一致但二者存在三项本质差异对 Key 的要求不同set 要求 Key 支持小于比较operatorunordered_set 要求 Key 支持转成整型并支持等于比较operator这本质上是哈希表底层存储和冲突解决的要求。迭代器与遍历顺序的差异set 的迭代器是双向迭代器底层红黑树通过中序遍历保证有序去重而 unordered_set 的迭代器是单向迭代器底层哈希表由于哈希映射导致元素存储杂乱遍历结果是无序去重。性能差异红黑树的增删查改效率为O ( log ⁡ N ) O(\log N)O(logN)哈希表的增删查平均效率为O ( 1 ) O(1)O(1)。4. unordered_map 与 map 的核心差异对比与unordered_set类似unordered_map与map也存在对应的特性差异增删查改接口如 insert、erase、find 以及 mapped_type operator[]用法完全一致。map 要求 Key 支持小于比较且遍历结果有序Key 有序去重unordered_map 要求 Key 支持转成整型与等于比较遍历结果无序。在绝大多数场景下unordered_map 的增删查改速度明显更快。5. 性能实测代码分析为了直观感受 set 与 unordered_set 在海量数据下的性能差异我们可以通过 test_set2 进行高强度压测。voidtest_set2(){constsize_t N10000000;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. set 插入性能测试size_t begin1clock();for(autoe:v){s.insert(e);}size_t end1clock();coutset insert:end1-begin1endl;// 2. unordered_set 插入性能测试配合 reservesize_t begin2clock();us.reserve(N);for(autoe:v){us.insert(e);}size_t end2clock();coutunordered_set insert:end2-begin2endl;cout插入数据个数s.size()endl;cout插入数据个数us.size()endlendl;// 3. set 查找性能测试intm10;size_t begin3clock();for(autoe:v){autorets.find(e);if(ret!s.end()){m1;}}size_t end3clock();coutset find:end3-begin3-m1endl;// 4. unordered_set 查找性能测试intm20;size_t begin4clock();for(autoe:v){autoretus.find(e);if(ret!us.end()){m2;}}size_t end4clock();coutunorered_set find:end4-begin4-m2endl;// 5. set 删除性能测试size_t begin5clock();for(autoe:v){s.erase(e);}size_t end5clock();coutset erase:end5-begin5endl;// 6. unordered_set 删除性能测试size_t begin6clock();for(autoe:v){us.erase(e);}size_t end6clock();coutunordered_set erase:end6-begin6endlendl;}疑问为什么在测试 unordered_set 插入性能前需要显式调用 us.reserve(N)这会对性能产生什么影响✅️答unordered_set底层采用哈希表存储。当插入大量数据如 1000 万个元素时如果不提前通过reserve预留足够的桶空间哈希表在元素增加的过程中会频繁触发自动扩容与rehash重新哈希。每一次 rehash 都需要重新计算所有元素的哈希值并重新分配链表节点这会带来巨大的时间开销。提前reserve(N)可以有效避免运行途中的多次动态扩容从而压榨出哈希表O ( 1 ) O(1)O(1)的极致插入性能。6. 完整源码展示以下是包含上述所有测试函数与 main 函数的完整可运行 C 源码#includeiostream#includevector#includeset#includeunordered_set#includecstdlib#includectimeusingnamespacestd;// 测试 1演示 unordered_set 的去重与无序特性voidtest_set1(){// 初始化包含重复元素的集合unordered_setints{3,1,6,7,8,2,1,1,5,6,7,6};unordered_setint::iterator its.begin();couttest_set1 遍历结果无序且自动去重endl;while(it!s.end()){cout*it ;it;}coutendlendl;}// 测试 2海量数据下 set 与 unordered_set 的性能对比voidtest_set2(){constsize_t N10000000;// 1000万数据量unordered_setintus;setints;vectorintv;v.reserve(N);srand(time(0));for(size_t i0;iN;i){//v.push_back(rand()); // 随机值较多重复//v.push_back(rand() i); // 重复值相对少v.push_back(i);// 没有重复有序填充}// 1. 测试 set 插入性能红黑树size_t begin1clock();for(autoe:v){s.insert(e);}size_t end1clock();coutset insert time: end1-begin1 msendl;// 2. 测试 unordered_set 插入性能哈希表预留空间优化size_t begin2clock();us.reserve(N);// 预留哈希桶空间避免频繁扩容for(autoe:v){us.insert(e);}size_t end2clock();coutunordered_set insert time: end2-begin2 msendl;coutset 插入数据个数s.size()endl;coutunordered_set 插入数据个数us.size()endlendl;// 3. 测试 set 查找性能intm10;size_t begin3clock();for(autoe:v){autorets.find(e);if(ret!s.end()){m1;}}size_t end3clock();coutset find time: end3-begin3 ms - found count: m1endl;// 4. 测试 unordered_set 查找性能intm20;size_t begin4clock();for(autoe:v){autoretus.find(e);if(ret!us.end()){m2;}}size_t end4clock();coutunordered_set find time: end4-begin4 ms - found count: m2endlendl;// 5. 测试 set 删除性能size_t begin5clock();for(autoe:v){s.erase(e);}size_t end5clock();coutset erase time: end5-begin5 msendl;// 6. 测试 unordered_set 删除性能size_t begin6clock();for(autoe:v){us.erase(e);}size_t end6clock();coutunordered_set erase time: end6-begin6 msendlendl;}intmain(){// 运行特性演示test_set1();// 运行海量数据性能对比test_set2();return0;}7. 实例演示总结通过本篇博客的学习与实战代码的验证我们可以得出明确的容器选型指南选择 std::set / std::map当你的业务场景明确要求元素保持有序或者需要使用区间查询接口如 lower_bound、upper_bound时。选择 std::unordered_set / std::unordered_map当你的核心诉求是追求极致的查找、插入和删除效率且对元素的顺序没有任何要求时哈希结构的无序容器将带来断层式的性能提升