C++ STL set与map实战笔记：从红黑树到哈希表的选择与坑

1. 为什么要单独把set和map拎出来学从一次写糟的ID列表说起前段时间我帮一个项目组做代码评审发现有人用vector存了十几万条用户ID每次判断“这个ID是否存在”都直接std::find扫一遍。功能倒是没错接口也全绿可数据一涨单次查询就从几毫秒飙到几十毫秒几个服务一叠加直接拖垮响应。我建议他把存储改成std::set改动只有四五行但同样的查询直接降到了微秒级。这正是我打算认真写一篇set和map使用笔记的原因这两种容器不单单是STL里的两个类模板它们背后代表的是一种“排序加快速查找”的思维方式很多人在算法题里会用一到真实项目里反而想不起来用。这也回答了“为什么值得学”set解决的是“集合”问题——维护一组不重复的元素并支持快速的插入、删除和查找map解决的是“映射”问题——从键到值的索引关系比如用户名到用户信息、订单号到订单对象。两者都基于有序二叉树的思路实现标准库通常用红黑树在元素量较大的时候单次操作的时间复杂度是O(log n)比线性扫描稳定得多。1.1 set到底在什么时候派上用场举个例子后台服务要维护一批在线用户的ID用户上线就加进去下线就移除同时要频繁判断某个ID是否在线。如果你用vector每次查在不在都要从头扫到尾如果用set插入、删除、查找都是对数复杂度而且元素天然不重复不用自己写去重逻辑。另一个典型场景是“求两个集合的交集、并集、差集”。set内部元素是有序的你可以用std::set_intersection、std::set_union这些算法直接操作得到的结果本身就是有序的。如果是vector你得先排序、再去重、再写双指针逻辑代码量至少翻一倍。1.2 map解决的则是一类更常见的问题几乎所有业务系统里都有“通过某个key找到对应的value”的需求配置文件里的键值对、请求参数到处理对象的映射、缓存系统里的键到值的关联。std::map用二叉树组织键所以查找、插入、删除也都是O(log n)它还保证了键的有序性比如你想按ID从小到大输出直接遍历map就是有序的不用额外排序。注意这里提到的set和map是标准库里的有序版本对应头文件set和map。它们和unordered版本的对比我会在第四部分专门说先别急着在每一处都用哈希表。1.3 这篇内容适合谁以及你能得到什么如果你刚学完C的基本语法对类、模板、迭代器这些概念有了大致印象但还没写过什么正经项目那这篇笔记刚好可以当一份“开箱即用”的速查手册如果你已经工作了一两年但平时主要写业务逻辑对STL的掌握停留在vector和遍历这篇也会帮你补上这块短板。读完你至少能回答这些问题set和map怎么初始化、怎么插入、怎么查找、怎么删除什么时候用map而不是unordered_mapinsert和emplace有什么区别为什么不能直接修改set里存的元素遍历map有哪几种姿势各自有什么坑。下面就从代码角度一个个过。2. set实战从初始化到自定义排序完整操作笔记2.1 初始化与插入重点看insert的返回值先来最基础的用法。包含头文件set之后声明一个空集合#include set #include iostream std::setint s;也可以直接用初始化列表注意重复元素会被自动丢弃std::setint s {5, 3, 8, 3, 1}; // 最终集合里的元素是: 1, 3, 5, 8这里有两个细节值得展开。第一set天然去重所以如果你有一个“元素不能重复”的需求与其每次插入前自己find一遍不如直接用set把去重责任交给容器本身。第二插入接口insert的返回值是个std::pairiterator, bool很多初学者不知道这个返回值很有用auto res s.insert(4); if (res.second) { std::cout 插入成功元素位置已经放置好。\n; } else { std::cout 插入失败元素已存在。\n; }res.first是插入元素或已存在元素的迭代器res.second告诉你这次操作是否真的新增了一个元素。这个返回值在你写“判断并加入”的业务逻辑时非常顺手省掉一次独立的find调用。如果你不想在set里看到重复元素却又不确定元素在不在这个返回值的语义就是标准答案先查再插入其实是不必要的insert自己就能告诉你结果。2.2 查找与判断存在find和count怎么选判断元素在不在集合里有两种常见写法if (s.find(8) ! s.end()) { // 找到 } if (s.count(8) 0) { // 找到 }两种写法在普通std::set里都可以时间复杂度都是O(log n)。区别在于语义find返回的是迭代器你拿到之后可能还想进一步使用count返回的是元素个数在set里只会是0或1更适合“只关心在不在”的场景。真正需要小心的是multiset和multimap它们允许重复键count可能返回大于1的值。那种情况下如果你用count判断是否存在会得到一个“存在但不知道有几个”的模糊答案需要用equal_range来精确控制。那find找不到会怎样返回end()和所有STL容器一致。所以标准习惯是先find、再判断是否等于end()然后访问。2.3 删除和清空erase的几种写法删除也有两种主要姿势。按值删除s.erase(3); // 直接把值为3的元素删掉返回值是删除的元素个数按迭代器删除auto it s.find(5); if (it ! s.end()) { s.erase(it); }按值删除适合“我不管位置就要删这个元素”的场景按迭代器删除适合“我在遍历过程中想删掉当前这个元素”的场景。这里有个老生常谈的坑如果要在遍历时删除元素不能无脑用范围for循环因为删除会导致迭代器失效。正确写法是用迭代器循环for (auto it s.begin(); it ! s.end();) { if (*it % 2 0) { it s.erase(it); } else { it; } }关联容器的erase在C11之后会返回指向下一个元素的迭代器所以it s.erase(it)是安全且简洁的。C20里可以直接用std::erase_if(s, 谓词)不过手写这个循环依然能在很多老标准下工作属于值得掌握的底子。清空整个集合用clear()这个没什么好说。2.4 自定义排序默认比较规则不满足需求时默认情况下setint从小到大排列。如果希望从大到小可以用std::greaterstd::setint, std::greaterint descending_set {1, 2, 3}; // 遍历结果是 3, 2, 1真正麻烦的是自定义类型。比如你有一个Person结构体希望按年龄排序struct Person { std::string name; int age; }; struct PersonComp { bool operator()(const Person a, const Person b) const { if (a.age ! b.age) return a.age b.age; return a.name b.name; } }; std::setPerson, PersonComp people; people.insert({Alice, 30}); people.insert({Bob, 25});自定义比较器必须满足“严格弱序”的要求对于同一个元素a b和b a不能同时为真比较关系要有传递性。如果你写了一个不严格的比较器表现就是底层树结构错乱甚至出现找不到已插入元素等诡异问题。另外你也可以给operator做成员重载效果类似但比较器的方式更灵活尤其适合“同一个类型在不同set里希望用不同规则排序”的场合。3. map实战键值操作、遍历方式与常见使用模式拆解3.1 声明、插入和初始化的几种写法std::map是键值对容器头文件map。一个最常用的声明std::mapstd::string, int scores;插入有三种常见姿势差别值得说清楚。scores[alice] 90; // 方式一operator[]赋值 scores.insert({bob, 85}); // 方式二insert 初始化列表 scores.emplace(carol, 88); // 方式三emplace直接构造这三种方式在“键已存在”时的行为不一样operator[]会直接覆盖旧值赋值动作无论如何都会发生insert如果发现键已存在不会覆盖旧值插入直接失败emplace和insert的语义类似也是“存在就不动”但构造方式更高效后面我会专门讲。所以如果你要“有则覆盖、无则新增”用operator[]如果你要“无则插入、有则跳过”用insert或emplace。不少新手把operator[]当万能工具结果在“不能覆盖配置”的需求里写出了悄悄覆盖的bug。声明带初始值也很简单std::mapstd::string, int scores { {alice, 90}, {bob, 85} };3.2 operator[]与at的区别一个写入一个读取这是map最容易踩坑的地方。operator[]的完整语义是如果键不存在就插入一个默认构造的值然后返回这个值的引用。这意味着哪怕是只读操作只要你用了[]也会往map里塞一个元素。int val scores[dave]; // dave 不存在时会插入一个 dave - 0这在计数器场景里是好用的因为你可以直接写for (const auto word : words) { word_count[word]; // 第一次遇到某个词时它会先插入0再自增到1 }但在纯粹的“读取配置项”“查询映射关系”场景里这会产生副作用你查一次容器就多一条空记录后续遍历时还会看到一堆本来不存在的键。如果你只想读取要么用find要么用atint value scores.at(alice); // 键不存在时抛 std::out_of_range auto it scores.find(dave); if (it ! scores.end()) { int value it-second; }我自己的习惯是写操作优先operator[]和emplace读操作一律用find绝对不用[]做“只读”。3.3 查找、判断键是否存在以及遍历方式判断键存在其实和set一样可以用find或count。注意map的count返回值同样只会是0或1multimap除外if (scores.find(bob) ! scores.end()) { // 存在 } if (scores.count(bob) 0) { // 存在 }遍历有几种写法。传统的迭代器for (auto it scores.begin(); it ! scores.end(); it) { std::cout it-first - it-second \n; }it-first是键it-second是值。范围for配合const auto可以避免拷贝for (const auto pair : scores) { std::cout pair.first - pair.second \n; }C17之后强烈推荐结构化绑定for (const auto [key, value] : scores) { std::cout key - value \n; }这里有个容易被误导的点const auto [key, value]只是把pair里的first和second通过引用绑定出来key在循环里本质还是const因为map的键不允许修改。你如果想在循环里改value可以直接用auto [key, value]但改了之后存储位置的引用是起作用的写起来比it-second xxx简洁很多。3.4 有序map的常见使用模式按顺序依赖std::map自带排序这带来一个隐性好用点遍历顺序恰好就是键的升序。比如你要按订单号从小到大汇总金额数据自然就是有序的不用再手动排序。反过来如果你关心的是“最新插入的优先”那你应该考虑unordered_map再加一个独立列表或者干脆换个容器因为map不会保留插入顺序。另一种常见模式是“以map的值作为计数器”配合operator[]能写得很舒服std::mapstd::string, int fruits; fruits[apple]; fruits[banana]; fruits[apple];这段代码跑完apple计数为2banana为1。每个operator[]调用都会先确认键是否存在不存在就插入默认值再返回引用所以自增操作在“第一次遇到某个键”时也能正常工作。这个写法短小且边界行为明确很适合做词频统计一类的事。4. 从红黑树到哈希表set/map与unordered变体的正确选型逻辑4.1 有序版本的底层结构为什么复杂度是O(logn)很多人只知道std::set和std::map的时间复杂度是O(log n)但不理解这个复杂度从哪里来。标准库实际实现通常基于红黑树这是一种自平衡二叉搜索树。它保证树的高度严格受控所以在最坏情况下查找、插入、删除也都不会退化成O(n)。红黑树和普通二叉搜索树的关键区别在于“平衡”。二叉搜索树在插入有序数据时会退化成链表比如连续插入1,2,3,4,5普通BST会变成一条右斜链查找复杂度瞬间变成O(n)。红黑树通过节点颜色约束和旋转操作让任意节点左右子树高度差保持在一个可控范围内从而稳定地提供O(log n)。使用set/map时你不需要关心这些细节但需要记住一个结论有序容器的代价是每次操作都要做元素间的比较。比较int非常快但比较一个长字符串或复杂结构体可能就不便宜了这是后面哈希版本能胜出的机会。4.2 unordered版本平均O(1)的代价是什么如果你只需要“键到值的映射”完全不在乎遍历顺序那unordered_map通常是更优选择#include unordered_map std::unordered_mapstd::string, int hash_map;它的底层是哈希表平均情况下插入、查找、删除都是O(1)。哈希表的原理是通过哈希函数把键映射到一个桶的编号直接在桶里找元素。桶里有冲突时用链表或红黑树解决但哈希函数分布得足够均匀时冲突很少。不过“平均O(1)”不代表没有代价哈希函数对自定义类型不是自动生效的你要自己提供哈希规则桶数量不够时会发生rehash也就是重新分配内存并重新计算所有元素的桶位置这是O(n)操作偶尔一次会让耗时产生明显尖刺遍历顺序完全不确定你不该依赖它输出任何有序结果。一个真实例子如果键是int值是一个大型结构体并且你会频繁按键做存在性判断那么unordered_map的常数时间在数据量达到几十万、上百万时非常可观但如果你的业务里有“按时间范围列出某类数据”的需求map自带排序反而能帮你避免一次sort。4.3 选型判断和自定义哈希的注意点我给自己总结的选型表分享给你需求特征推荐容器需要按键有序遍历、范围查询std::set/std::map只关心查找和插入速度不关心顺序std::unordered_set/std::unordered_map需要自动去重set或unordered_set允许重复键multiset/multimap知道大概数据规模想减少rehashunordered_map::reserve自定义类型放进unordered_set/unordered_map时必须提供哈希函数和相等判断。一个常见写法是用std::hash组合成员struct Point { int x, y; }; struct PointHash { std::size_t operator()(const Point p) const { return std::hashint{}(p.x) ^ (std::hashint{}(p.y) 1); } }; struct PointEqual { bool operator()(const Point a, const Point b) const { return a.x b.x a.y b.y; } }; std::unordered_setPoint, PointHash, PointEqual points;这段代码要写对必须同时提供两点一是PointHash告诉容器“怎么算哈希”二是PointEqual告诉容器“两个键何时视为相等”。缺一个都编不过。如果你忘写了PointHash编译器会尝试用std::hashPoint但它通常没有为自定义类型定义于是报错——这也是很多初学者卡壳的地方。5. 我在使用set和map时踩过的坑迭代器失效、键不可改与性能陷阱5.1 迭代器失效的真相有序容器与无序容器大不同迭代器失效是C容器家族里最容易出问题的话题但很多人把所有容器混为一谈。实际上set/map和vector完全不同vector的插入/删除可能让所有迭代器失效但set/map的插入不会让任何已有迭代器失效删除也只会让“指向被删除元素”的那个迭代器失效。这意味着你可以放心地在持有迭代器的情况下继续插入新元素auto it s.find(5); s.insert(100); // it仍然有效但在删除时就需要注意写法。一个常见错误是for (auto it m.begin(); it ! m.end(); it) { if (条件) { m.erase(it); // 错误erase之后it已经失效继续是未定义行为 } }正确写法前面已经提过删除后把返回值赋回给it或者用it技巧for (auto it m.begin(); it ! m.end(); ) { if (条件) { it m.erase(it); } else { it; } }到了unordered_map情况更复杂rehash可能导致所有迭代器失效而reserve可以提前分配足够的桶数减少rehash次数是性能优化里值得养成的一个习惯。5.2 键不可修改或者说不能“偷偷”改键如果你试图遍历一个set并修改它的元素你会遇到编译错误std::setint s {1, 2, 3}; for (auto v : s) { v v * 10; // 编译报错cannot assign to const }因为set的迭代器指向的是const元素。map的first也是constsecond可以改。这个设计不是故意刁难而是为了保证底层树的排序不变性。如果允许你修改set里的元素底层红黑树仍然是按旧位置的顺序排列的查找逻辑就会完全错乱轻则查不到元素重则程序崩溃。所以正确的“修改键”姿势是先擦除旧键再插入新键。别想着用const_cast去绕过检查那是给自己埋雷。5.3 operator[]隐式插入带来的性能与正确性陷阱这部分我想多强调一次。很多人写map读操作时会顺手用[]取默认值结果在代码里埋了一个“读一次就多一条数据”的坑。你看到这个错误是因为有一个配置文件功能int timeout config[timeout];如果config是std::mapstd::string, int而配置里没有timeout这个键那么这行代码会插入timeout - 0。更麻烦的是如果后面又有人用insert想补默认值他会发现键已经存在插入失败行为完全不符合预期。排查这种问题的思路是凡是“只读”场景一律先find再判断迭代器是否等于end()。如果追求简洁也可以用at()让异常机制代替隐式逻辑。5.4 erase的返回值在不同C版本下的差异在C98时代std::map::erase(iterator)返回void你要在循环里删除当前元素得用“先自增再删除”的技巧std::mapint, int::iterator it m.begin(); while (it ! m.end()) { if (满足条件) { m.erase(it); } else { it; } }C11之后erase返回下一个迭代器于是可以更直观地写it m.erase(it)。如果你在维护老代码看到erase(it)这种写法不要觉得奇怪那很可能是为了兼容老标准如果你自己写新代码用返回迭代器的写法会更清晰也更安全。6. 从“会用”到“用好”代码习惯与典型场景建议6.1 优先使用emplace而不是insertemplace是C11引入的接口区别在于它直接把参数转发给元素的构造函数在容器内部完成构造而不是先构造一个临时对象再拷贝或移动进去。以map为例scores.emplace(carol, 88);上面的调用如果使用insert实际流程大概是构造一个临时pairconst string, int再拷贝进map内部节点。而emplace直接在节点里用carol和88构造pair少了一次临时对象和一次拷贝。字符串短时差别不大字符串很长或结构体很大的时候这个性能差距就能体现出来。注意emplace和insert的语义一样键已存在时不会覆盖。所以“覆盖更新”还是要用operator[]。这里有一个容易被忽略的细节emplace失败时传入的参数可能已经被移动或消耗掉了如果你用的是std::string右值需要确认后续是否还要使用原字符串。6.2 在算法题和业务代码里的典型用法两数之和是算法题里最经典的map通常用unordered_map例子。给定一个整数数组返回两个下标使得它们对应的数之和等于目标值。常规双重循环是O(n^2)用哈希表可以做到O(n)#include vector #include unordered_map std::vectorint twoSum(const std::vectorint nums, int target) { std::unordered_mapint, int seen; for (int i 0; i static_castint(nums.size()); i) { int complement target - nums[i]; auto it seen.find(complement); if (it ! seen.end()) { return {it-second, i}; } seen[nums[i]] i; } return {}; }每次循环先检查target - nums[i]在不在哈希表里不在就把当前元素登记进去。这里用unordered_map是因为我们完全不需要排序只追求查找速度。业务代码里更常见的是“根据ID读取对象”的缓存场景std::unordered_mapint, UserInfo user_cache; if (auto it user_cache.find(user_id); it ! user_cache.end()) { return it-second; }C17的if (auto it ...; 条件)语法让“查找并判断”变得很紧凑变量it在整个if块内可用代码边界也更清楚。6.3 set和map之间的协同你能用它们解决更复杂的问题一个我经常用的组合是“set里存pair模拟优先级或者区间覆盖”。比如维护一批区间要求每次找“包含某个点且左端点最小的区间”可以把区间放进setpairint,int利用lower_bound快速定位候选区间。这时set提供的不是简单的去重而是一种“始终有序”的容器基础。另一个组合是“map的value再放一个set”。例如在社交系统里统计每个用户关注的标签std::mapstd::string, std::setstd::string user_tags; user_tags[alice].insert(coding); user_tags[alice].insert(music);这样每个键对应的值本身也是有序集合可以快速判断“alice是否关注了coding”也可以直接遍历她关注的所有标签。这种容器套容器的方式能省掉大量手动维护索引的逻辑。使用这套东西时我一直坚持几个原则第一先问自己“我到底需不需要有序”需要就选map/set不需要就选unordered系列第二读操作坚决不用operator[]第三自定义类型要么提供严格的比较规则要么提供可用的哈希规则不要指望编译器和标准库能猜到你的意图。这些习惯看上去很简单但我见过太多bug就藏在“顺手”二字里。把基础容器的语义吃透写复杂代码的时候会省下很多和编译器搏斗的时间。