看到标题里“STL”这三个字母眼尖的朋友可能第一反应是3D打印的STL模型文件。先别急着点返回今天聊的是C里的STLStandard Template Library而且聚焦到一个很多人用过std::set、却未必真正玩明白的主题——集合算法。这套算法能让你用两三行代码完成并集、交集、差集、对称差集和子集判断关键是不挑容器vector、array、deque都能用前提只有一个数据必须是有序的。这套东西适合谁正在刷面试题的C选手、写业务逻辑时经常跟列表/集合打交道的开发、以及所有想从“会用的std::vector”升级到“会用算法库”的人。说句实话我见过不少同事面试时被问到set_union怎么用第一反应是“这不是std::set的成员函数吗”这就是对集合算法最大的误解也是我今天想先掰扯清楚的事。1. 集合算法不是“std::set专属”它接受的是“有序区间”在STL的算法库里以set_开头的这组函数被统称为集合算法它们的名字确实容易让人误会成“std::set专用工具”。但打开头文件algorithm看一下签名就会明白所有集合算法的参数都是迭代器区间而不是容器类型。templateclass InputIt1, class InputIt2, class OutputIt OutputIt set_union(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);这段签名说明一切它接收两个“排好序”的范围把运算结果写到一个输出迭代器上。换句话说std::set只是众多合法输入中的一种一个被排好序的std::vector完全可以用一个std::array、一个std::deque、甚至一个裸数组都没问题。算法内部只看迭代器不关心元素住在哪个容器里。1.1 算法只是“有序序列的数学运算工具”从数学概念上看集合算法做的事情非常朴素把两个有序序列当作数据集合然后执行并集、交集、差集这些运算。这里的核心前提是“有序序列”为什么非要有序因为集合算法的时间复杂度目标是一个线性扫描也就是O(N1 N2)。要做到这一点必须借助序列的升序特性用类似归并排序的“双指针”思路一遍走过两个区间就能完成比较和选取。如果输入无序理论上也不是完全没法算但代价会变成两两比较的O(N1 * N2)甚至在处理重复元素时连“哪个元素属于哪个集合”都难以界定。所以标准库选择了“有序输入线性复杂度”这条最优雅的路线把排序的责任交给调用者。1.2 “有序”的具体要求严格弱序“有序”不是一个模糊的形容词而是指元素满足**严格弱序strict weak ordering**关系。默认情况下算法使用operator来比较两个元素要求两个输入区间各自按升序排列且两个区间必须使用同一套比较规则。一个容易被忽略的细节是当算法判断两个元素是否“相等”时它并不会调用operator而是看!(a b) !(b a)是否成立。如果a和b互不小于对方算法就认为两者在这个集合运算中“等价”。这意味着自定义类型的比较逻辑会直接影响运算结果我在第4节会专门讲这个坑。1.3 面对重复元素集合算法实际上按“多重集”语义工作数学课上学的集合不允许重复元素比如{1, 2} ∪ {2, 3}结果就是{1, 2, 3}。但STL的集合算法没有这么理想化它默认输入可能包含重复元素并按多重集multiset的方式处理重复项。举个具体例子[1, 2, 2, 3]和[2, 2, 2, 4]做并集结果不是[1, 2, 3, 4]而是[1, 2, 2, 2, 3, 4]。原因是重复元素2在第一个区间出现2次、第二个区间出现3次并集取最大次数max(2, 3) 3所以输出3个2。不同的算法对重复计数规则不同刚接触时很容易在这上面翻车下一节逐个过一遍就清晰了。2. 五个核心算法逐个拆解语义、签名与可运行示例STL集合算法一共有五个set_union、set_intersection、set_difference、set_symmetric_difference和includes。前四个都有输出迭代器最后一个专门做子集判断。我按使用频率从高到低逐个讲每个都给出签名、语义、重复元素规则和一个能直接编译的示例。2.1 set_union并集注意重复元素“取最大数量”#include algorithm #include iostream #include iterator #include vector int main() { std::vectorint a{1, 2, 2, 3}; std::vectorint b{2, 2, 2, 4}; std::vectorint out; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); for (int x : out) std::cout x ; // 输出1 2 2 2 3 4 }返回值是写入的尾后迭代器如果传入back_inserter这个返回值基本用不上。重复元素规则如果某个等价元素在[first1, last1)中出现k1次在[first2, last2)中出现k2次则输出max(k1, k2)份。这个语义保证了结果依然是升序且每个元素的保留数量恰好能“覆盖”两个输入中较大的需求。2.2 set_intersection交集最常被问的“共同好友”交集的使用场景非常直观两个列表求“同时存在”的元素。签名和set_union基本一致只是输出规则变成等价元素出现次数取min(k1, k2)。std::vectorint a{1, 2, 2, 3}; std::vectorint b{2, 2, 2, 4}; std::vectorint out; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // out: {2, 2}注意输出里有两个2因为第一个区间只有两个2交集不能输出比这更多。这个算法在面试中经常被拿来手写标准库帮我们省掉了双指针循环的功夫。2.3 set_difference差集“我多出来的是什么”set_difference(first1, last1, first2, last2, out)表示计算[first1, last1)中不在[first2, last2)里的元素。实际开发中这个函数特别适合算“新增了哪些数据”。重复元素规则是同一等价元素在第一个区间出现k1次、第二个区间出现k2次时输出max(0, k1 - k2)份。std::vectorint a{1, 2, 2, 2, 3, 4}; std::vectorint b{2, 2, 5}; std::vectorint out; std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // out: {1, 2, 3, 4} // 2 在第一区间出现 3 次第二区间 2 次差集保留 1 次顺序上有个容易记反的点set_difference的语义是“第一个区间相对第二个区间的差”而不是“第二个相对第一个”。写代码前最好确认一下到底想算“新增”还是“删除”这两个方向正好相反。2.4 set_symmetric_difference对称差集“分道扬镳的部分”对称差集计算的是“只属于其中一个集合”的元素思路就是并集去掉交集。体现在重复元素数量上就是取|k1 - k2|份。std::vectorint a{1, 2, 2, 3}; std::vectorint b{2, 2, 2, 4}; std::vectorint out; std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out)); // out: {1, 2, 3, 4} // 2 出现 |2 - 3| 1 次这个算法在对比两份配置、找出两边各自独有的配置项时很实用。它的实现本质上是先算差集再加差集但标准库的线性实现比“两次set_difference再合并”更省事。2.5 includes子集判断一个容易忽略的实用工具includes是这五个算法里唯一没有输出迭代器、返回值是bool的。它判断[first1, last1)是否完整包含[first2, last2)中的所有等价元素包括重复数量也要满足。std::vectorint big{1, 2, 3, 4, 5}; std::vectorint small{2, 3, 4}; bool ok std::includes(big.begin(), big.end(), small.begin(), small.end()); // ok: true这个算法非常适合做“权限集合是否满足要求”这类判断。比如用户拥有的权限ID已经排好序某个功能需要权限ID集合{2, 4, 7}直接用includes一次判断不用自己写循环。为了方便对比我把五个算法的重复元素处理规则整理成了表格算法重复元素输出规则典型用途set_unionmax(k1, k2)合并两个有序列表并保留足够多重复项set_intersectionmin(k1, k2)求列表交集、共同元素set_differencemax(0, k1 - k2)计算第一个区间“多出来”的元素set_symmetric_differenceabs(k1 - k2)求两边“各自独有”的元素includes要求 k1 k2 恒成立判断子集关系3. 真实项目里集合算法最常出现的四个场景掌握API只是第一步真正有价值的是知道在哪些地方能想起用它。我在业务代码里见过太多次“自己手写两重循环”的实现其实标准库一行就能替代。下面列几个我实际遇到过的场景。3.1 配置/数据同步用差集算出新增与删除假设你有一份服务端下发的全量配置ID列表还有一份本地已经应用过的配置ID列表两边都按ID升序排好了。现在要做增量同步逻辑很清晰std::vectorint serverIds{1, 2, 3, 4, 5, 8}; std::vectorint localIds{1, 3, 5}; std::vectorint toAdd; std::vectorint toRemove; std::set_difference(serverIds.begin(), serverIds.end(), localIds.begin(), localIds.end(), std::back_inserter(toAdd)); // {2, 4, 8} std::set_difference(localIds.begin(), localIds.end(), serverIds.begin(), serverIds.end(), std::back_inserter(toRemove)); // 空注意第二个差集的方向反过来了计算的是本地有但服务端已经不存在、需要删除的配置。这种写法比我最早用std::find_if逐个扫要清晰得多而且复杂度从O(N * M)直接降到O(N M)。3.2 标签系统与权限判断交集与includes组合做内容推荐或者标签聚合时经常需要判断“用户关注标签”和“内容所需标签”是否有重叠以及是否完全覆盖。用集合算法描述非常自然std::vectorint userTags{2, 5, 7, 9}; std::vectorint contentTags{2, 5}; bool covers std::includes(userTags.begin(), userTags.end(), contentTags.begin(), contentTags.end()); // true用户标签完全覆盖内容所需标签 std::vectorint common; std::set_intersection(userTags.begin(), userTags.end(), contentTags.begin(), contentTags.end(), std::back_inserter(common)); // common: {2, 5}如果两个集合是std::set还可以考虑用std::set::merge做节点迁移但那只能是把一个set的元素移到另一个set里和这里“生成新序列”的语义不一样。查重叠、查覆盖set_intersection和includes才是正解。3.3 合并有序列表set_union 帮你顺手完成去重有些场景里两个列表各自有序但存在大量重复项你想把它们合并成一个有序且重复数量合理的新列表。直接push_back之后再sort unique当然也行但set_union可以在合并过程中就把重复元素数量控制在max(k1, k2)的语义下。std::vectorint a{1, 3, 3, 5, 7}; std::vectorint b{1, 2, 3, 5, 5, 9}; std::vectorint merged; merged.reserve(a.size() b.size()); std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(merged)); // merged: {1, 2, 3, 3, 5, 5, 7, 9}如果业务语义是“只要一份不要任何重复”那还是sort unique更直接或者把数据放进std::set再遍历。关键是想清楚到底要“数学集合去重”还是“多重集的取多数语义”别混用。3.4 集合算法的复杂度红利为什么比手写循环省心很多面试者会手写集合相交代码默认方法就是for (int x : a) for (int y : b) if (x y) ...这个写法在a和b都是10万级数据时会慢到怀疑人生。标准库集合算法的复杂度被严格限制在线性级别对于set_union这类算法标准保证的最多比较次数是2 * (N1 N2) - 1实际实现通常更低。这意味着数据量越大用标准库算法的相对收益越明显。另一个隐含的好处是接口语义正。手写循环很容易把“相等”判断写成而标准库用comp判断等价也和“有序序列”的前提保持一致。无论从运行效率还是从正确性角度都比手写循环更可靠。4. 常见坑与排查思路为什么结果总是“不对劲”集合算法看着简单实际踩坑的人不少。我在代码评审里看到过好几类问题这里把最常见的几类连同排查思路一起列出来。4.1 输入没排序最常见的未定义行为集合算法要求输入区间已经按升序排列但标准库不会帮你检查。一旦你传了一个未排序的vector进去代码不会报错只会悄悄给出错误结果——甚至在某些编译器实现下连结果都可能不稳定因为未定义行为本身就意味着没有任何承诺。排查思路很简单在使用算法前补一个快速的自检或直接排序。如果数据需要在多个集合算法间复用建议排序一次后保存排序结果不要在每次调用前重复排序。std::sort(beginA, endA); std::sort(beginB, endB);提示如果你的数据本身来自std::set或std::map它们的迭代器天然有序可以放心直接传。4.2 排序规则不一致两个比较器打架这是比“未排序”更隐蔽的坑。两个输入区间分别有序还不够它们必须按照完全相同的比较规则有序。比如a按整数的绝对值排序b按整数的自然大小排序两者传给set_intersection后等价性判断会乱套结果没有任何意义。更常见的是自定义类型的“多重排序”问题。一个User结构体里既有id又有name如果两个vector分别按不同字段排序再用同一个comp做集合运算结果一定不对。排查时先确认两个区间各自的排序依据再确认传给算法的comp和它们一致。4.3 输出迭代器与输入重叠back_inserter也救不了你标准明确规定输出区间不能和两个输入区间存在重叠否则行为未定义。有人天真地想“把并集结果直接写回a”std::vectorint a{1, 2, 3}; std::vectorint b{3, 4, 5}; std::set_union(a.begin(), a.end(), b.begin(), b.end(), a.begin());这是一个非常危险的写法。虽然并集结果长度恰好可以覆盖a但算法在扫描a的同时在改写a前面的元素可能还没被读取就被覆盖结果完全不可预期。正确的做法是输出到临时vector确认无误后再swap或assign回原容器。4.4 内存分配与reserve让back_inserter更省心很多新手拿到集合算法后喜欢直接配back_inserter这没有任何问题但频繁的push_back会反复触发扩容。输出大小的上界是已知的完全可以提前reserve甚至用一个容量为“理论最大值”的vector直接接收算法的输出。以并集为例最大输出元素数为a.size() b.size()。我常用的高性能写法是std::vectorint out; out.reserve(a.size() b.size()); std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));如果不想在reserve后还承担back_inserter的开销可以用固定容量的预分配方案std::vectorint tmp(a.size() b.size()); auto end std::set_union(a.begin(), a.end(), b.begin(), b.end(), tmp.begin()); tmp.erase(end, tmp.end());这里end是算法返回的尾后迭代器erase之后剩下就是真正的并集内容。这个技巧在性能敏感代码里很有价值可以少一次潜在扩容。4.5 自定义类型的“相等”陷阱误以为两个对象相等用集合算法处理自定义类型时最容易被旧习惯带偏。很多人以为交集就是把operator为真的元素挑出来实际上标准库在集合算法里根本不碰operator它的“等价”完全由比较器定义。struct User { int id; std::string name; bool operator(const User other) const { return id other.id; } };如果两个User对象id相同但name不同a b和b a都为false算法就会认为它们是等价元素交集会保留其中一个。这在大多数业务场景里是正确的因为id才是业务主键。但如果你希望“只有id和name完全相同才算同一个用户”就必须在比较器里同时比较两个字段否则结果和你想象中的“精确匹配”会差很远。排查这类问题先问自己我的比较器定义的等价关系是否符合业务里的唯一性规则5. C20之后ranges版本给集合算法带来什么C20的std::ranges命名空间对集合算法做了重构用法更现代同时补上了投影projection这种非常实用的能力。如果你在写新代码非常建议直接上手ranges版本。5.1 ranges::set_intersection 与投影消除比较器样板传统版本里如果要对结构体按某个字段做集合运算需要写一个自定义比较器并把它传给算法。ranges版本的投影参数可以直接指定“按哪个字段比较”省掉一整段样板代码。#include algorithm #include ranges #include vector #include iterator struct Item { int id; std::string name; }; std::vectorItem v1{{1, a}, {3, c}, {5, e}}; std::vectorItem v2{{3, c}, {5, e}, {7, g}}; std::vectorItem common; std::ranges::set_intersection( v1, v2, std::back_inserter(common), std::ranges::less{}, Item::id, Item::id ); // common: { {3, c}, {5, e} }这里前两个参数直接传容器本身不再拆begin/endstd::ranges::less{}是比较器两个Item::id分别是两个输入范围的投影算法比较时自动只关注id字段。潜在前提是v1和v2都已经按id升序排列这一点和传统版本一样。5.2 返回值与经典版本的差异经典集合算法通常只返回一个输出迭代器但ranges版本返回一个结果对象包含三个迭代器/哨兵in1、in2和out。这个改变让调用方可以知道“算法在两个输入区间分别读到了哪里、输出写到了哪里”在链式组合算法时很有用。auto res std::ranges::set_union(v1, v2, std::back_inserter(out)); // res.in1、res.in2、res.out实际项目中大多数时候不需要关注这个返回值但如果你要继续在剩余区间上做其他算法操作这个结构体就派上用场了。5.3 视图组合的现实限制ranges生态带来的一个隐含诱惑是“能不能用视图直接操作避免分配临时vector”。很遗憾ranges版本的set_union、set_intersection等算法并没有对应的“视图工厂”它们仍然要求输出到一个迭代器上。你可以把views::filter、views::transform等视图作为输入传给这些算法但结果还是要物化到容器或消费者迭代器里。auto filteredA v1 | std::views::filter([](const Item it) { return it.id 1; }); std::vectorItem out; std::ranges::set_intersection(filteredA, v2, std::back_inserter(out), std::ranges::less{}, Item::id, Item::id);这样至少省掉了生成过滤临时vector的开销但也仅限于输入侧。如果你的首要目标是完全不分配内存还是得自己评估数据量再做取舍。提示使用ranges版本需要编译器支持C20标准GCC 10、Clang 13、MSVC 2019 16.10都问题不大编译时别忘了加-stdc20。我在实际项目里最得意的一次改造是把一段两百多行的“找出新增配置ID”手写逻辑替换成两个set_difference调用加上几行reserve。代码从两百行缩到二十行逻辑一眼能看懂性能还因为线性复杂度变快了。从那以后我养成了一个习惯凡是涉及两个有序列表的“共有、差异、合并”操作先想想集合算法而不是着急写循环。今天这五个工具如果你能自己在编译器里各跑一遍示例并故意制造“未排序”或“比较器不一致”的错误观察输出会比看十遍文档都管用。