开篇先把 map 和 set 的定位搞清楚再说怎么用干这行这些年我发现一个规律很多 C 初学者学到 STL 的时候vector、string 用得飞起一碰到 map 和 set 就容易卡壳。其实不是这两个容器本身多难而是很多人没想明白它们到底是干什么的。我自己的体会是map 和 set 背后站着同一个底层结构——红黑树这决定了它们的能力和限制。map 负责键值对应这类需求比如用户 ID 映射到用户对象set 负责维护一堆互不相同的元素这类需求比如记录所有出现过的单词。它们解决了同一个核心问题在数据不断增删的过程中还能保持有序、快速查找。这篇文章我不会讲太多语法书上的废话直接把我实际写代码时怎么选、怎么用、踩过哪些坑全部梳理一遍。适合正在学 C STL 的读者也适合已经用了很久但没系统想过为什么的同行。看完你会知道什么时候该用 map什么时候改用 unordered_map什么时候一个 vector 加 sort 反而更香。1. 整体设计思路为什么偏偏是红黑树而不是哈希表或数组1.1 关联容器设计的两个底层约束先理解一个基本事实map 和 set以及它们的 multiset、multimap 版本在绝大多数标准库实现里底层都是红黑树。红黑树是一种自平衡二叉搜索树它能保证在最坏情况下查找、插入、删除都是 O(log n)。这个保证非常重要因为哈希表在极端冲突情况下可能退化到 O(n)而红黑树无论如何都兜得住。但红黑树带来的另一个特性往往被忽略中序遍历是有序的。这意味着你用迭代器从头到尾遍历 map 时键会按升序出现遍历 set 时元素本身按升序出现。这是一个免费的午餐——你不用额外排序就能拿到有序序列。很多场景其实就需要这个性质比如排行榜、区间查询、有序输出这些需求用 map/set 天然就合适。对比一下三个方案方案查找复杂度是否有序遍历典型场景vector sortO(n log n) 排序后 O(log n)排序后有序但插入会打乱静态数据集、一次构建多次查询unordered_map/unordered_set平均 O(1)最坏 O(n)无序只关心快速查找不关心顺序map/set 红黑树O(log n) 稳定始终有序需要动态增删 有序输出的场景你看map/set 的价值不在于快而在于有序 动态平衡。如果你不需要有序priority 给 unordered_map通常比 map 快两到三倍如果你的数据是静态的先 sort 再二分查找也不差。但很多业务场景下数据是不断插入的同时你又需要随时拿到有序视图这时候 map/set 就是最省心的选择。1.2 一套树结构撑起四个容器STL 里围绕红黑树其实有四个门面map、set、multimap、multiset。map 的每个节点存一个 pairkey valueset 的每个节点只存一个 key。multimap 和 multiset 则允许重复键。我刚开始学的时候有个困惑既然 multimap 允许重复键那和 map 有什么区别后来在实际项目里用过一次就明白了。比如统计一段文本中每个单词出现的次数如果用 map每次插入要先检查是否存在存在就 value 1否则插入新键如果用 multimap直接每次 insert 就行最后用 count() 统计个数。不过说实话这种需求用 map 做计数是更优的因为 value 就是用来干这个的。multimap 更适合的是一对多且不需要聚合的场景比如一个部门 ID 对应多个员工。在实际工程里multimap 和 multiset 的使用频率远低于 map 和 set很多项目里直接用 vector 存重复数据再排序效果也不差。所以我的建议是初学者重点吃透 map 和 setmultimap/multiset 了解存在即可等真遇到一对多的时候再深入。2. map 实操拆解每个 API 背后都有值得注意的细节2.1 插入的三种姿势以及 operator[] 的隐藏行为map 最常用的操作就是插入。有三种方式但它们的语义其实不太一样。第一种是insert方法。pairiterator, bool ret m.insert(make_pair(key, value));返回的 bool 表示是否插入成功。如果 key 已经存在插入失败迭代器指向已存在的元素value 不会被覆盖。这个特性在去重写入场景下很好用你不需要先 find 再决定插不插一次 insert 全都告诉你了。第二种是emplace。它的好处是避免构造临时对象。m.emplace(key, value);会直接在节点内存里构造元素而不是先创建一个 pair 再拷贝进去。对 string 这类有堆分配的类型emplace 能省一次拷贝性能上有实打实的提升。我现在写新代码基本默认用 emplace只有需要判断是否插入成功时才配合返回值使用。第三种是operator[]。这个最危险也最容易被新手踩坑。m[key] value;的语义是如果 key 存在返回引用并赋值如果 key 不存在先默认构造一个 value再返回引用。换句话说m[key];这行代码本身单单是访问一个不存在的键就会插入一个默认值进去我举一个实际踩过的例子。在一个消息转发模块里我原本想检查某个 session 是否存在写了if (session_map[user_id].valid())。结果每次检查都往 map 里塞了一个默认的 session 结构内存越来越高排查了半天才发现是 operator[] 在偷摸插入。正确的做法是如果只想查询用find()如果确定要写入再用 operator[]这样它的便捷性才有价值。2.2 查找与删除find、count、erase 的配合使用map 的查找官方接口是find。它返回迭代器如果没找到返回end()。写判断的时候注意if (m.find(key) ! m.end())很多新手会写成if (m.find(key))这是错的因为 find 返回的是迭代器不是指针也不是布尔值。count(key)返回的是 key 出现的次数。map 里每个键最多出现一次所以 count 要么返回 0 要么返回 1。用它判断存在性也完全可行但 count 的语义到底是统计次数find 的语义是定位元素两者在代码可读性上有差异。我个人的习惯是判断是否存在只用 count因为一行写完要拿到元素才用 find。不过要统一风格避免一个项目里两种写法混杂。删除是erase(key)或者erase(iterator)。传键会返回删除的数量要么 0 要么 1传迭代器没有返回值。有一个细节值得注意erase 之后被删元素的迭代器会失效但其他迭代器不受影响。这是红黑树结构带来的好处不像 vector 那样删一个元素后面全部失效。所以你在遍历过程中删除元素可以这样写for (auto it m.begin(); it ! m.end(); ) { if (需要删除(*it)) { it m.erase(it); // C11 之后erase返回下一个迭代器 } else { it; } }这段代码我写的时候特意省略了具体删除条件因为条件因业务而异但这个迭代器在循环里安全删除的骨架是通用的。在 C11 之前erase 是不返回迭代器的必须m.erase(it);这样绕一下。如果你在维护老代码看到it的写法就是这个历史原因。2.3 遍历与修改 value 的注意事项遍历 map 最常见的写法就是范围 forfor (auto [key, value] : m) { // key 是 const 的value 可修改 }这里有个关键点key 永远是 const 的。因为 key 一旦改变红黑树的有序性就崩了。你要是直接auto [key, value]然后尝试给 key 赋值编译都过不了。所以任何需要修改 key 的操作正确姿势是找到旧节点的 valueerase 掉再以新 key insert 进去。修改 value 则随意。map 的 value 只是附属数据修改它不影响树结构。所以你可以放心地在遍历时对 value 做累加、更新不需要任何额外的解锁操作。另外关于遍历顺序我前面提过map 的中序遍历是有序的。在很多时候这个特性可以帮你省掉一个排序步骤。举个例子你需要按分数从低到高输出所有学生直接用 mapdouble, Student分数作为 key插入完遍历就是有序的。当然如果分数会变操作起来就麻烦一些这个权衡要自己做。3. set 的使用要点不只是简单的去重工具3.1 有序集合的三个典型应用场景set 最直观的用途是去重。setint s; s.insert(x);重复插入的 x 会被忽略。但如果你只想要去重unordered_set 通常更快set 的优势在于它有顺序。我实际项目里用 set 的频率不高但一旦用到往往是下面三种场景。第一种是有序集合维护。比如维护一个当前在线用户 ID列表要求随时能够按 ID 顺序输出。set 插入、删除都是 O(log n)每次操作完遍历就是有序的。相比用 vector 存在线用户每次输出时排一遍序set 的时间复杂度更稳定。第二种是区间查找。红黑树天然支持 O(log n) 查找大于等于某个值的最小元素对应 STL 的lower_bound和upper_bound。比如给定一个时间段 [start, end]要快速找到所有落在这个区间内的记录可以在 set 上调用s.lower_bound(start)得到起始迭代器然后遍历到end为止。这个能力 vector 和哈希表都给不了。第三种是充当访问标记集合。在有向图或者树的遍历中需要判断某个节点是否被访问过而且访问完成后不再关心顺序。这种场景用 unordered_set 其实性能更好但如果你同时需要最近访问的节点是哪些之类的有序信息set 就更合适。3.2 自定义类型进 set比较规则怎么写才对set 默认用std::lessKey来比较元素也就是直接调用operator。如果你往 set 里塞自定义类型比如一个二维坐标点 Point却连都没定义编译会报错提示你invalid comparator。解决办法有两种。第一种是给类型重载operatorstruct Point { int x, y; bool operator(const Point other) const { if (x ! other.x) return x other.x; return y other.y; } };这里注意一个陷阱operator必须满足严格弱序strict weak ordering。简单说就是不能出现 a b 和 b a 同时为真的情况也不能出现传递性断裂。很多人写比较函数时没注意这个比如只比较 x 不比较 y那么两个 x 相同但 y 不同的点会互相比较不出来导致 set 认为它们是相等的后插入的被丢弃。这个 bug 特别隐蔽因为编译不报错运行也不崩溃就是结果不对。第二种写法是给 set 传入自定义比较器。比较器可以是一个仿函数函数对象struct PointLess { bool operator()(const Point a, const Point b) const { if (a.x ! b.x) return a.x b.x; return a.y b.y; } }; std::setPoint, PointLess s;或者从 C14 开始比较器可以是泛型 lambdaauto cmp [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }; std::setPoint, decltype(cmp) s(cmp);我个人偏好第二种因为不侵入类型定义尤其当这个类型实际上有业务含义的排序规则而你只想让 set 用一种特殊顺序来组织它的时候。3.3 multiset 和 unordered_set 的选择依据multiset 允许重复元素。但这里我要说一个很多人容易混淆的点multiset 的erase(key)会把所有等于 key 的元素全部删掉不是删一个。如果你只想删一个必须用erase(find(key))。这个坑我在一次调度任务里栽过往 multiset 里插了好几批任务想按优先级逐个处理完再删除结果一个erase(key)把同优先级的一下全清了debug 了半天才意识到。unordered_set 则完全是另一条技术路线。它底层是哈希表查找平均 O(1)但遍历顺序完全无序。所以是否有序这个需求直接决定了你在 set 和 unordered_set 之间怎么选。在很多不需要排序的集合场景下unordered_set 是性能首选但如果你需要lower_bound、upper_bound或者按序遍历那就不能用了得老老实实回去用 set。我在实际项目里的选择标准很简单先问自己遍历时需不需要顺序需要就用 set不需要就用 unordered_set。现代 CPU 上哈希表的 O(1) 查找配合很好的 cache 局部性几乎总能打败红黑树的 O(log n)前提是哈希函数不要写得太烂。4. 从 map/set 延伸到 unordered 容器哈希的自定义与性能权衡4.1 什么情况下需要自定义哈希函数虽然这篇文章的核心是 map 和 set但很多读者在实际开发中会面临map 性能不够想换 unordered_map的抉择所以我在这部分把我对哈希容器的理解也梳理一下。标准库给 unordered_map/unordered_set 提供了内置的哈希函数适用于 int、string、double 这些基础类型。但如果你要把自定义类型作为键比如一个结构体就需要自己提供一个std::hashT的特化。一个典型的自定义类型哈希写法struct ProductKey { int category; int id; bool operator(const ProductKey other) const { return category other.category id other.id; } }; struct ProductKeyHash { size_t operator()(const ProductKey k) const { // 将两个int的哈希组合成一个 return std::hashint{}(k.category) ^ (std::hashint{}(k.id) 1); } }; std::unordered_mapProductKey, ProductInfo, ProductKeyHash products;这里有几个关键点。其一必须同时提供operator和哈希函数因为哈希表先用哈希值定位桶再用精确比较桶内的元素。其二哈希函数要尽量让不同对象产生不同的哈希值否则大量元素挤在同一个桶里哈希表就退化成链表了。上面例子中 1是为了避免两个字段直接异或造成的对称性问题比如 (1,2) 和 (2,1) 如果直接异或会得到同样的哈希值。4.2 均匀性与哈希碰撞的代价我见过很多人自定义哈希时非常随意直接返回一个常量。这样当然能编译运行但所有元素都落在同一个桶里插入和查找退化成 O(n)比 vector 线性查找还要慢因为还有哈希表的开销。均匀性是什么意思呢假设你的键是整数但分布集中在 0 到 1000而哈希表有 1024 个桶那你不加处理直接用键作为哈希值均匀性其实堪忧。标准库的std::hashint通常会对整数做某种位运算让分布更均匀但如果你自己实现就要关注这一点。碰撞的代价在数据量大之前是感知不到的。当哈希表元素超过一定阈值标准库会触发 rehash也就是扩大桶数组并重新分配所有已有元素。这个操作的时间是 O(n)如果恰好发生在一次请求处理中间那一帧的性能就会出现一个锋利的尖峰。所以如果数据集很大且插入频繁可以提前调用reserve预设桶数量减少 rehash 次数。4.3 排序容器 vs 哈希容器 vs 排序数组的取舍这部分的经验总结下来就是一句话没有万能的数据结构只有对场景的数据结构。我遇到过这样一个实际问题一个配置表大概一万条记录读取后不会再动态增删查询非常频繁。最初我用 map 存性能还行后来优化时改成静态数组 sort lower_bound查询耗时降低了一半。为什么因为数组是连续内存cache 友好二分查找比红黑树每次走指针腾挪要快得多。另一个场景是高频插入的同时高频查询数据量还在持续增长。这种用 map 是对的因为平衡树不需要 rehash时间复杂度稳定插入和删除不会带来全量重排的灾难。还有一类场景既需要按顺序输出又需要极快的查找且数据量很大。这种矛盾需求单靠一个容器很难两全我的方案通常是维护一个 unordered_map 保存最新副本同时定期构建一个有序索引比如用 vector 排序。这对业务方来说是最终一致但对于真正要求两者兼备的场景业界往往引入更重的索引结构那就是另一个话题了。普通工程里大多数场景其实没那么极端选一个主用容器就够了。5. 常见问题与排查技巧实录5.1 operator[] 意外插入一个隐藏的内存膨胀源这是 map 使用者最容易踩的坑我前文提过一次但值得单独拿出来再说清楚。症状程序跑了几天后内存持续涨但从代码逻辑上看map 的大小不应该增长。排查方法全局搜索所有[key]的用法逐一确认是否在查询语境中使用了。如果是全部改成find。我自己的经验是新代码里一律用insert或emplace写入用find或count读取。只有一种情况用operator[]——确定这个键务必要有值比如统计计数m[key]这句代码的语义是取当前计数加一如果不存在从零加一这个用法是安全的不会产生无意义的空项。5.2 erase 在循环中的迭代器失效前面给过遍历删除的正确写法这里再补充一个反向的例子。有次我写了一段从 set 里删除元素的代码用的是范围 for 内嵌erasefor (auto x : s) { if (需要删(x)) s.erase(x); }这段代码在大多数编译器上能跑但如果在 erase 之后再继续使用迭代器 x就是未定义行为。范围 for 隐藏了迭代器的细节它内部其实是保存了一个迭代器在递增一旦 erase 之后这个迭代器失效下一次循环的递增就会踩在野指针上。这是一种典型的平时不出问题换了编译器或者开了更高优化级别就崩的代码。正确做法我在 2.2 已经写过就是用传统 for 循环 it s.erase(it)或者s.erase(it)。这两种方式都能保证迭代器安全递进因为 erase 返回的迭代器指向被删元素的下一个元素。5.3 比较器必须满足严格弱序我见过一个非常经典的问题自定义了一个房价数据的排序规则每次比较都返回a.price b.price。这个比较器导致了两个问题第一等值元素之间会互相为真破坏严格弱序第二在红黑树插入时可能让两个明明不同的对象被判定为相等导致数据丢失。严格弱序的三个基本要求是反对称性a b 和 b a 不能同时成立、传递性a b 且 b c 则 a c、等价性a 和 b 互不小于时二者对任何 c 的表现一致。工程上只要记住一点比较器里只用不要用不要用反过来也一样。对于多字段类型像坐标点那种依次比较每个字段不要漏判任何一个字段。5.4 快速查错速查表症状可能原因解决方案m[key]后 map 莫名变大operator[] 插入默认值查询用 find/count遍历删除崩溃迭代器失效it s.erase(it)或erase(it)set 里某些元素丢失比较器漏判字段补全严格弱序比较multiset 删除太多erase(key) 删了全部等值项用erase(find(key))自定义类型无法作为 unordered_map 键缺少哈希函数提供operatorhash特化map 遍历输出不是想要的顺序键类型比较规则不符合预期自定义比较器或换用 vector 排序这张表是我自己日常排错时的手感总结不是语法规范的罗列。真正跑项目的时候很多问题不是出现在 API 不会用而是用错了语义。map 和 set 的问题十有八九都集中在插入、删除、比较这三个环节。结尾这是我用下来的心得最后分享一点个人体会。我最初学习 map 和 set 的时候也只是背了一遍 API后来在一次真实的后端服务性能排查中才深刻理解底层结构决定使用方式这句话。如果你只记住一个东西记住红黑树它让 map/set 在插入、删除、查找上保持 O(log n)并且天然有序。基于这一点你在设计数据结构时就会自然地问自己我需要有序吗需要动态插入删除吗如果两个答案都是是map/set 就是你的默认选择如果有一个答案是否那就去别的容器里找更合适的方案。还有一个小技巧如果你在调试时发现 map 或 set 的行为不符合预期先写一串已知顺序的键值进去遍历打印一遍观察它的输出顺序、去重行为、删除结果通常马上就能定位问题。数据结构的问题用最小样本往往比看半天代码更快。希望这些经验对你也有用。