写这篇之前我先说句实话网上讲 set 和 multiset 的教程不少但大多数都在念 API 文档念完你照样不知道怎么选、怎么用、踩了坑不知道怎么查。我从实际开发的角度把这些年用这两个容器积累下来的经验一次性写透从底层原理到 API 细节从自定义排序到性能选型再到那些文档里不会写、但你会真实踩到的坑。内容偏实战代码都跑过你照着抄就行。1. set和multiset到底解决什么问题——设计初衷与底层原理1.1 一个老问题无序查找太慢了我刚开始写 C 的时候折腾得最多的就是“存一堆数据然后要快速判断某个值在不在里面”。用数组或者 vector 存查找只能一个个挨着比数据量小还好几万个元素一上来每次查找都是 O(n)循环套循环直接卡死。当时我还试过先排序再二分查找但排序本身就要 O(n log n)而且一旦中间新增或删除元素又得重新维护有序性麻烦得很。set 解决的就是这个核心痛点它内部自带排序并且查找、插入、删除都是 O(log n)。你不用自己维护任何有序结构往里面丢数据它自动排好想查一个数在不在直接 find 一下时间复杂度稳定在对数级别。multiset 和 set 的差别只有一个——允不允许重复值set 里每个值最多出现一次multiset 允许出现多次。打个比方吧。数组就像一摞没有整理过的试卷想找一道题得从头翻到尾set 就像按学号整理好的名单册每页一个学号翻起来快得多而且新增一个人也能插到正确的位置不用把整本册子重抄一遍。1.2 红黑树set背后的那个“隐形发动机”set 和 multiset 的底层实现是红黑树在绝大多数标准库实现里比如 libstdc、MSVC STL都是这样。红黑树是一种自平衡的二叉搜索树它的核心思路是每个节点都带一个“红色”或“黑色”的标记通过一组规则限制从根到叶子节点的路径上黑色节点的数量保证整棵树的高度始终维持在 O(log n)从而让查找、插入、删除都稳定在对数级别。为什么不用普通的二叉搜索树因为普通的 BST 在极端情况下会退化成一条链表——想象你按顺序插入 1、2、3、4、5树就变成一条直线查找退化成 O(n)跟数组没什么区别了。红黑树通过旋转和变色操作在每次插入或删除后自动调整树的结构避免这种退化。这一点影响了你在使用时的一个方向set 的操作复杂度是理论保证的 O(log n)不是平均情况而是最坏情况。所以它比哈希表更适合对稳定性有要求的场景不会因为哈希冲突导致某个操作突然变慢。那 multiset 和 set 在底层实现上的区别呢其实就是红黑树的插入逻辑上少了一个“如果值已存在就返回”的判断。对底层节点结构来说set 的每个节点存一个键multiset 的每个节点也存一个键只是允许重复键共存。中序遍历红黑树得到的一定是有序序列这也是“set 天然有序”这句话的来源——迭代器按升序遍历拿到的就是从小到大排列的元素序列。2. 核心API细节与实操要点2.1 构造与初始化别只会默认构造我在代码评审里看到过很多人初始化 set 只写一行setint s;其实它有几种很实用的构造方式能省不少事。#include set #include vector #include iostream int main() { // 1. 默认构造空集合 std::setint s1; // 2. 用迭代器区间构造从 vector 里挑元素出来 std::vectorint vec {5, 3, 9, 3, 1, 7}; std::setint s2(vec.begin(), vec.end()); // 结果是 {1, 3, 5, 7, 9} // 注意3 只保留了一个因为 set 自动去重并排序 // 3. 初始化列表构造C11 起可用 std::setint s3 {4, 2, 8, 2, 6}; // 结果{2, 4, 6, 8} // 4. 拷贝构造与移动构造 std::setint s4(s3); // 深拷贝一份 std::setint s5 std::move(s3); // s3 内部资源被搬走s3 变为空 return 0; }这里有个很实用的点用迭代器区间构造时 set 会顺带去重加排序。如果你有一个 vector 想去重并排序直接塞进 set 再导出来就行。虽然这个操作是 O(n log n)但代码非常简洁日常脚本或小工具里用很合适。2.2 插入元素insert和emplace怎么选insert 是 set 最常用的操作但它有一个容易被人忽略的细节——返回值。std::setint s; auto [it, inserted] s.insert(42); // inserted 是 bool // true 表示插入成功原本没有 42 // false 表示插入失败42 已存在it 指向已有的 42 auto [it2, inserted2] s.insert(42); // inserted2 falseit2 指向同一个元素对 multiset 来说插入永远成功所以返回的是指向新插入元素的迭代器没有 bool 了std::multisetint ms; auto it ms.insert(42); // 直接返回迭代器 auto it2 ms.insert(42); // 也成功ms.size() 2C11 之后有 emplace 系列可以在容器内部直接构造元素避免临时对象的拷贝或移动。对于存储自定义对象、构造成本较高的场景emplace 效率更高struct Student { int id; std::string name; Student(int i, std::string n) : id(i), name(std::move(n)) {} bool operator(const Student other) const { return id other.id; } }; std::setStudent students; students.emplace(1, Alice); // 在容器内部直接构造避免一次临时对象 students.insert(Student(2, Bob)); // 先构造临时对象再拷贝/移动到容器对于 int、double 这类内置类型insert 和 emplace 差别不大用哪个都行。但如果是std::string、自定义类或者结构体优先考虑 emplace少一次拷贝。insert 还有一个带位置提示的重载版本insert(const_iterator hint, const value_type value)如果在插入位置接近 hint 时复杂度可以降到均摊 O(1)。不过这个优化的前提是你对数据分布有把握否则别乱用老老实实走常规插入。2.3 删除元素erase的三种用法erase 是我见过问题最多的 API因为有三种不同的调用方式语义差很多。std::setint s {1, 2, 3, 4, 5}; // 用法 1按值删除返回删除的元素个数 size_t n1 s.erase(3); // 删掉 3n1 1 size_t n2 s.erase(99); // 没这个值n2 0 // 用法 2按迭代器删除返回下一个有效迭代器 auto it s.find(2); if (it ! s.end()) { it s.erase(it); // it 现在指向 4如果还存在的话 } // 用法 3按区间删除 auto beginIt s.lower_bound(2); auto endIt s.upper_bound(4); s.erase(beginIt, endIt); // 删掉 [2, 4] 区间内的元素在 set 里erase(值)返回的是 0 或 1因为 set 没有重复值但在 multiset 里就麻烦了——erase(值)会把所有等于这个值的元素全部删除返回的是删除的总数。我见过不少新人在 multiset 里想“删掉一个等于某个值的元素”结果调erase把所有重复值全删了。后面 5.1 节我会专门讲怎么处理。还用注意一点set 的迭代器不支持it n这种随机访问只能it或--it因为底层是双向链表结构的树节点。别想着s.erase(s.begin() 2)编译直接报错。2.4 查找元素find、count、contains与区间查询查找是 set 最拿手的活。std::setint s {10, 20, 30, 40, 50}; // find找不到返回 end() auto it s.find(30); if (it ! s.end()) { // 找到了*it 30 } // count在 set 里返回 0 或 1在 multiset 里返回实际个数 if (s.count(30)) { // 在 set 里用 count 判断“是否存在”可以这么写 } // C20 起有 contains语义更清晰 if (s.contains(30)) { // 存在 }对 set 来说find和count都是 O(log n)区别只在于返回值不同。C20 的contains是更直观的写法推荐在新项目里用。判断“存不存在”就用contains不要再用count() 0更不要用find() ! end()来判断存在性然后还要解引用那个是“我要拿这个元素”时才做的。真正能体现 set 价值的是区间查询lower_bound和upper_bound。std::setint s {1, 3, 5, 7, 9, 11, 13}; // lower_bound(key)返回第一个 key 的迭代器 auto it1 s.lower_bound(6); // 指向 7 auto it2 s.lower_bound(5); // 指向 5 // upper_bound(key)返回第一个 key 的迭代器 auto it3 s.upper_bound(6); // 指向 7 auto it4 s.upper_bound(5); // 指向 75 本身不包含在内 // 经典用法查询 [5, 11] 闭区间内的所有元素 for (auto it s.lower_bound(5); it ! s.upper_bound(11); it) { std::cout *it ; // 输出 5 7 9 11 }equal_range(key)一次返回一个 pairfirst 是 lower_boundsecond 是 upper_bound。在 multiset 里特别实用因为等值的元素会连续排列在一个区间里std::multisetint ms {1, 2, 2, 2, 3, 4, 4, 5}; auto range ms.equal_range(2); // range.first 指向第一个 2 // range.second 指向 3第一个大于 2 的元素 for (auto it range.first; it ! range.second; it) { std::cout *it ; // 输出 2 2 2 }这个特性在算法题里很常用。比如“统计一个 multiset 里某个值的出现次数、把所有等于某个值的元素统一处理”这类需求equal_range比循环find再erase优雅得多。3. 自定义排序规则让set按照你的逻辑排序3.1 默认排序和它的局限性默认情况下set 用的是std::lessT也就是按照运算符升序排列。所以setint遍历出来是从小到大setstring是字典序。但现实场景里需求千奇百怪。比如学生信息按分数从高到低排列、任务队列按优先级排序、时间戳按倒序排列……这时候默认的升序就不够用了。很多人的第一反应是“我先存进去再 reverse 遍历”但这样很别扭而且rbegin()反向遍历对某些算法不友好。正确做法是直接给 set 指定一个比较器让它从头到尾就按照你想要的顺序组织。3.2 仿函数与lambda实现自定义排序给 set 指定排序规则有几种不同写法我逐个说。第一种用仿函数函数对象这是最传统的方式适合比较逻辑固定、需要复用的情况#include set #include iostream // 降序排列的仿函数 struct Greater { bool operator()(int a, int b) const { return a b; } }; int main() { std::setint, Greater s {5, 1, 4, 2, 3}; for (int x : s) { std::cout x ; // 输出 5 4 3 2 1 } return 0; }其实标准库已经提供了现成的std::greaterint不用自己写std::setint, std::greaterint s {5, 1, 4, 2, 3}; // 遍历结果5 4 3 2 1第二种用 lambda。lambda 本身没有类型名要借助decltype来声明模板参数auto cmp [](int a, int b) { return a b; }; std::setint, decltype(cmp) s(cmp); // 注意构造函数里要传入比较器实例 s.insert(5); s.insert(1); s.insert(4); for (int x : s) { std::cout x ; // 输出 5 4 1 }这里有个容易踩的坑std::setint, decltype(cmp) s;这种写法在 C20 之前可能编译不过因为默认构造的 lambda 没有状态但在某些标准库实现里要求必须显式传入 lambda 对象。稳妥的写法是std::setint, decltype(cmp) s(cmp);把 cmp 传给构造函数。第三种针对自定义类型直接重载operator让类型本身具备比较能力struct Task { int priority; int id; // 按优先级升序优先级相同再按 id 升序 bool operator(const Task other) const { if (priority ! other.priority) return priority other.priority; return id other.id; } }; std::setTask tasks; tasks.insert({3, 1001}); tasks.insert({1, 1002}); tasks.insert({2, 1003}); for (const auto t : tasks) { std::cout t.priority t.id \n; } // 输出 // 1 1002 // 2 1003 // 3 1001重载operator的优点是使用方便任何地方直接声明std::setTask就能用缺点是这个排序规则是“全局绑定”的如果同一个类型在不同场景需要不同排序规则就比较尴尬。这时建议用仿函数或者 lambda同一个类型可以定义多个比较器用在不同的容器里。3.3 自定义类型比较与严格弱序STL 里所有基于比较的容器set、multiset、map、priority_queue 等都要求比较器满足严格弱序strict weak ordering。这个数学概念看着吓人实际上核心就几条同一元素必须满足cmp(a, a)为 false。如果cmp(a, b)为 true那么cmp(b, a)必须为 false。如果cmp(a, b)为 true 且cmp(b, c)为 true那么cmp(a, c)必须为 true。如果两个元素既不满足cmp(a, b)也不满足cmp(b, a)就认为它们“等价”。最典型的错误写法是直接返回a bstruct BadCmp { bool operator()(int a, int b) const { return a b; // 错误不满足严格弱序 } };为什么不能用因为cmp(a, a)返回 true违反了第一条规则。这会导致 set 内部判断元素相等时逻辑混乱轻则重复元素插入失败重则在极端数据下导致插入的位置出现错误红黑树结构被破坏程序出现诡异的崩溃。我调试过这种问题现象极其隐蔽——有时候能跑有时候崩有时候元素数量不对追踪了大半天发现是比较器写错了。判断两个元素等价的正确方式是!cmp(a, b) !cmp(b, a)。红黑树内部查找时就是这么判断的。所以你自己写的operator或者仿函数必须保证“严格小于”的语义不要加等于。还有一点比较器必须是“稳定的”也就是说同一个元素的比较结果不能随时间变化。如果比较器依赖一个会变化的外部状态比如某个全局任务的优先级被修改了就会造成 set 内部结构错乱。确实需要修改排序依据时正确的做法是把旧元素删掉、修改属性、再重新插入。4. 性能分析与容器选型什么时候用set什么时候别用4.1 复杂度与真实开销set 的查找、插入、删除都是 O(log n)这个复杂度听起来不错但实际使用时要考虑常数因子和内存开销。红黑树的每个节点除了存储元素本身还要存储左孩子指针、右孩子指针、父节点指针和颜色标记。64 位系统下光这三个指针就是 24 字节再加颜色、对齐等每个节点的额外开销通常在 40 字节左右。存一个 int4 字节却要付出差不多 40 字节的额外代价空间利用率其实不高。这就是为什么我在比赛中偶尔会听到有人抱怨“set 太耗内存”。如果你只需要“去重判断存在”而不需要有序遍历std::unordered_set在大多数情况下更划算——时间复杂度均摊 O(1)内存结构紧凑一些。但注意 unordered_set 的查找是平均情况最优遇到严重哈希冲突时会退化到 O(n)所以对稳定性要求极高的场景需要谨慎。set 的另一个隐藏成本是节点动态分配。每次 insert 都会新建节点这涉及内存分配器调用。如果你在一个大循环里频繁插入几百万个元素malloc/free 的调用开销会很明显。STL 的缓存机制对这种小对象分配有优化但终究不如 vector 一次性分配一大块连续内存来得快。4.2 set、unordered_set、vector怎么选我直接给一个选型表是我在实际项目里验证过的经验需求推荐容器理由需要有序遍历从小到大/自定义顺序set / multiset底层红黑树天然有序查找/插入/删除频繁且数据量大set / unordered_set都是 O(log n) 或 O(1)需要范围查询比如闭区间 [a, b]setlower_bound/upper_bound 天然支持只需要去重不关心顺序unordered_set均摊 O(1)内存更省数据几乎不变主要是遍历vector sort unique内存连续缓存友好效率最高需要随时取出最大/最小值set 或 priority_queueset 更灵活priority_queue 更轻量需要按下标随机访问元素都不要用直接用 vectorset 不支持随机访问为什么有些场景用 vector 反而更快因为连续内存对 CPU 缓存极度友好。如果数据是静态的、只需排序去重后遍历vector 是最优解。sort加unique两步搞定遍历时缓存命中率高得惊人。几百万个元素排序去重vector 方案可能比 set 方案快一个数量级。4.3 不同场景下的选型参考列举几个我在实际中见过或做过的场景方便你套用第一个任务调度器需要按照优先级从高到低取出任务同时支持随时插入新任务有时还要取消某个任务。set 很合适因为插入和删除都是 O(log n)而且底层有序取最高优先级任务就是*begin()如果比较器让优先级最高的排在最前面。如果用 priority_queue取消任务会很麻烦因为堆不支持随机删除。第二个在线排行榜要维护玩家分数排名支持玩家分数更新、查询前 N 名。set 可以但要注意分数更新时需要先删再插否则会破坏排序。性能上如果玩家很多百万级以上每次更新 O(log n) 可以接受。我个人更推荐用跳表之类的结构但在 STL 范围内 set 是合理选择。第三个自动补全/前缀匹配如果只是词前缀匹配setstring配合 lower_bound 可以找到所有以某个前缀开头的词比如用lower_bound(abc)到upper_bound(abc \xff)或者手动比较前缀。但这个场景如果数据量大且有动态更新更专业的方案是 trie 树。set 适合数据量小、实现简单的场景。第四个贪心算法题经典的“最多能安排多少个会议”这类题目按结束时间排序后不断找下一个最早结束的会议set 可以很好地维护当前可用的会议集合。算法竞赛里常见的“动态中位数”问题用两个 multiset一个存小半部分、一个存大半部分就能解决比手写平衡树省太多事。核心原则是先想清楚你要的操作是什么再选容器。很多人习惯了一上来就用 set其实有些场景用 set 反而是错的。5. 真实开发中的常见问题与避坑指南5.1 erase的经典坑multiset会删光所有重复值这个坑我单独拎出来说因为它太常见了。看这段代码std::multisetint ms {1, 2, 2, 2, 3, 4, 5}; // 你以为删掉了一个 2实际上把 3 个 2 全删了 ms.erase(2); // ms 现在是 {1, 3, 4, 5}multiset::erase(const key_type)的语义就是“删除所有值等于 key 的元素返回删除个数”。如果你只想删掉一个 2必须先用 find 找到迭代器再传迭代器给 erasestd::multisetint ms {1, 2, 2, 2, 3, 4, 5}; auto it ms.find(2); if (it ! ms.end()) { ms.erase(it); // 只删除一个 2 } // ms 现在是 {1, 2, 2, 3, 4, 5}这个行为对 set 没有影响因为 set 里没有重复值erase(值)最多删一个所以很多人在 set 上用的好好的换到 multiset 就翻车。遇到 multiset 相关的 bug先想一想是不是把“删一个”和“删全部”搞混了。5.2 迭代器失效与遍历中删除set 的迭代器失效规则比 vector 友好得多插入一个元素不会导致已有迭代器失效删除一个元素只会让被删元素的迭代器失效其他迭代器完全不受影响。这是因为树节点的内存地址在插入、删除后保持不变迭代器本质上就是指向树节点的指针。所以在遍历中删除元素可以这样写std::setint s {1, 2, 3, 4, 5, 6}; for (auto it s.begin(); it ! s.end();) { if (*it % 2 0) { it s.erase(it); // erase 返回下一个迭代器直接赋值给 it } else { it; } } // s 现在是 {1, 3, 5}在 C11 之前erase返回 void那时候必须这样写for (auto it s.begin(); it ! s.end();) { if (*it % 2 0) { s.erase(it); // 技巧先保存 it再递增再删除旧的 it } else { it; } }现在用 C11 之后的版本直接利用返回值就行代码更清晰。但如果你在写老代码或兼容老编译器it那个技巧还很有用原理是后缀自增会返回一个指向原位置的迭代器同时 it 已经指向下一个节点删除原位置不会影响 it。5.3 不要直接修改元素set 的元素在容器里是作为节点的键存在的红黑树的有序性依赖这些键。如果你拿到一个迭代器后直接修改指向的元素相当于把树的排序规则给破坏了std::setint s {10, 20, 30}; auto it s.begin(); // *it 50; // 错误破坏了红黑树的有序性标准库的做法是set 迭代器的解引用返回值是const T也就是说编译器根本不让你直接改。但 multiset 呢multiset 的迭代器解引用同样返回 const 引用。这不只是标准库的设计选择而是必须如此一旦修改了键值整棵树的结构就不可信了。什么叫“破坏了有序性”具体来说红黑树在构建时每个节点的位置是根据比较器计算出来的。如果你把一个节点从 10 改成 50但它在树里的物理位置还是按照“10”的位置放的那后面查找 50 的时候树会跑到其他路径去找大概率找不到而且遍历时顺序也是错的。正确的修改方式是先删除再插入std::setint s {10, 20, 30}; auto it s.find(10); if (it ! s.end()) { int value *it; s.erase(it); s.insert(50); } // s 现在是 {20, 30, 50}如果你存的是自定义结构体同理——先取出元素修改副本删除旧元素插入新元素。别想着“我改一下内部字段但排序字段不变就行”这个思路理论上可行但实操中很难保证不出错因为迭代器根本不给你 const_cast 之外的方式去改。5.4 比较器不满足严格弱序导致的诡异bug前面 3.3 节讲了严格弱序的数学要求这里我再补充一个真实案例。有一个朋友写过这样的比较器struct Cmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.first b.first; // 只比较 first忽略 second } };他想按 pair 的 first 排序如果 first 相同就认为是“等价”的。这个逻辑本身没问题但问题出在 pair 的默认比较会同时比较 first 和 second而他只比 first导致 first 相同的多个 pair 被 set 视为等价后面的插入会被丢弃。也许这正是他想要的但如果是想“按 first 排序且 first 相同时保留多个元素”这个比较器就不对了——这时候应该用 multiset而不是 set。另一种更隐蔽的错误是比较器结果随着时间变化。比如比较器读取的是一个全局配置的权重值运行中权重被改了导致之前插入的节点和未插入节点之间的相对顺序改变了。红黑树内部并不知道这个变化于是查找可能走错路径甚至出现“元素明明插进去了却 find 不到”的诡异现象。所以使用自定义比较器时记住三点比较器必须严格弱序。比较器必须是确定的同一元素对无论调用多少次结果都一样。比较器不能依赖运行期可变状态。如果确实需要动态权重就别用 set 直接存储“按权重排序的对象”而是存一个带 id 的包装结构比较器基于 id 的属性计算属性更新时先删后插。5.5 内存与性能大规模数据时的隐藏开销set 在数据量大的时候内存开销不容忽视。每个节点额外字段左右孩子、父节点、颜色标记通常要占几十字节。在内存受限的环境或者嵌入式开发里这可能是个问题。如果你存的是大对象比如一个结构体包含多个 string、vector那就更需要注意了。set 的每个节点存储的是对象本身而不是指针。节点内存是按对象大小动态分配的。如果想省内存可以存智能指针struct BigObject { int id; std::string title; std::string content; std::vectorint tags; // ... }; // 直接存 BigObject每个节点都复制一份完整对象 std::setBigObject s1; // 存 shared_ptr节点里只有指针减少复制 std::setstd::shared_ptrBigObject s2;注意setstd::shared_ptrBigObject默认按指针地址比较也就是按 shared_ptr 的地址排序不是按对象内容排序。如果你要按 id 排序得自己写比较器比较两个 shared_ptr 指向的对象的 id。而且这样排序的稳定性跟对象地址有关插入顺序不同可能导致遍历顺序不同所以实际用起来要小心。大多数业务场景下我更推荐直接存对象因为 set 的查找等操作都是基于对象副本进行比较的存指针反而让比较逻辑变复杂。只有对象确实很臃肿、拷贝成本高时才考虑存指针或存索引值。我的几点实操心最后分享一些心得吧。我在算法竞赛里用 set 用得最多的是“动态维护有序集合”类的问题比如找某个值的前驱后继、维护滑动窗口中的中位数。那时候最爽的一点就是不用自己写平衡树。但工作以后写业务代码我反而很少直接用 set 了大部分“需要去重 判断存在”的地方用 unordered_set 就够了只有确实需要“有序遍历”或“范围查询”时才掏出 set。如果你在做开发我建议你在写代码之前先问自己三个问题这个集合需要有序输出吗需要频繁做范围查询吗数据量大概多少想清楚这三个问题容器的选择就不会错。一个小技巧收尾用 multiset 配合 lower_bound 可以在元素动态增删的场景下稳定地找“最接近某个值的元素”这个在维护时间序列数据、安排日程、分配资源这些场景里很实用。代码就一句话auto it ms.lower_bound(target); // 第一个 target 的元素 if (it ! ms.end()) { // *it 就是最接近且不小于 target 的元素 // 如果想看比它小的用 prev(it) }一句话总结我对 set 的态度它不属于那种“什么都能干”的容器但在“动态有序集合”这个垂直领域里目前 STL 里找不出比它更顺手的选择。你把它用明白了很多原本实现起来很麻烦的数据结构问题几行代码就解决了。