C++ STL集合算法全解析：有序区间上的并集、交集与差集-北京尧图网络

每天一个STL知识点今天轮到集合算法。说到“集合算法”很多人第一反应是std::set的几个成员函数其实STL里真正的集合运算是一组泛型算法它们并不属于set类而是藏在algorithm头文件里并且作用对象是任意“已经排好序的范围”。无论你是准备C面试还是项目中正在处理标签、权限、配置这类需要做并集、交集、差集的场景这一块都值得彻底过一遍。我最初接触这套算法时也有个误区以为它只能配合std::set用。后来在一个推荐系统需求里要对两份用户标签列表做合并才发现std::set_union能直接作用在vector上代码比手写循环干净太多。今天这篇文章就把set_union、set_intersection、set_difference、set_symmetric_difference、includes五个函数一次讲透包括参数语义、重复元素规则、输出迭代器细节以及我实际踩过的几个坑。1. 先搞清楚集合算法到底在解决什么问题1.1 没有集合算法时我们是怎么写集合运算的先说没有集合算法时的朴素写法。比如两个vectorint要求“并集且去重”很多人的第一反应是双层循环加findstd::vectorint union_naive(const std::vectorint a, const std::vectorint b) { std::vectorint r a; for (int x : b) { if (std::find(a.begin(), a.end(), x) a.end()) { r.push_back(x); } } std::sort(r.begin(), r.end()); r.erase(std::unique(r.begin(), r.end()), r.end()); return r; }这段代码功能上没错但问题很明显std::find是线性扫描整体复杂度是O(N*M)两份数据规模一大就难受后面还要再sort和unique等于把数据反复搬了好几次。如果面试被问到这里稍微追问“你怎么保证去重”“复杂度是多少”这种写法就不够看了。同样做“交集”手写双指针归并也是一个经典解法但双指针版本必须自己处理越界、相等、推进逻辑边界一多就容易写错std::vectorint intersection_by_hand(const std::vectorint a, const std::vectorint b) { std::vectorint r; size_t i 0, j 0; while (i a.size() j b.size()) { if (a[i] b[j]) i; else if (b[j] a[i]) j; else { r.push_back(a[i]); i; j; } } return r; }所以STL把这一类“对有序区间做集合运算”的操作抽成了公共算法输入输出都用迭代器接口容器无关。这正好是STL设计哲学的核心算法不依赖容器只要求迭代器满足相应条件。1.2 五个函数的基本图谱与“有序”这个硬前提STL集合算法一共有五个函数数学语义输入要求输出std::set_union并集两个有序区间有序合并结果std::set_intersection交集两个有序区间两个区间都有的元素std::set_difference差集A-B两个有序区间只属于第一个区间的元素std::set_symmetric_difference对称差集两个有序区间只属于其中一个区间的元素std::includes判断子集两个有序区间返回bool为什么“有序”是硬前提因为这些算法内部都是双指针线性扫描思路和归并排序的最后一步完全一致。只有两个区间各自有序才能通过比较当前指针指向元素的大小来决定下一步移动哪个指针否则结果毫无正确性可言。复杂度方面标准规定这类算法最多做2 * (N M) - 1次比较其中N和M是两个输入区间长度。这个复杂度是线性的远好于朴素写法的O(N*M)代价只是要求“入参有序”。另外一个很容易被忽略的点集合算法和std::set容器没有绑定关系。vector、deque、array、std::set、std::multiset只要元素有序通通可以传进去。真正绑定关系的是“必须有序”不是“必须是集合容器”。2. 四个主力算法逐个拆解附跑通实例先把一个综合示例完整跑一遍后续小节都基于这份代码解释。这份代码可以原样复制到本地编译执行注意包含algorithm、vector、iterator#include algorithm #include iostream #include iterator #include vector int main() { std::vectorint a{1, 3, 5, 7, 9}; std::vectorint b{2, 3, 5, 8}; std::vectorint uni; std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(uni)); std::vectorint inter; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(inter)); std::vectorint diff; std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(diff)); std::vectorint sym; std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(sym)); for (int x : uni) std::cout x ; std::cout \n; for (int x : inter) std::cout x ; std::cout \n; for (int x : diff) std::cout x ; std::cout \n; for (int x : sym) std::cout x ; std::cout \n; return 0; }运行结果1 2 3 5 7 8 9 3 5 1 7 9 1 2 7 8 9接下来逐个拆解。2.1 set_union并集以及重复元素到底怎么算std::set_union(first1, last1, first2, last2, d_first)把两个有序区间合并成一个有序区间。从实现角度看就是双指针同时扫描两个指针指向的值谁小就先输出谁如果两边元素“等价”按照比较器规则谁也补不大于谁那就只输出第一个区间的元素然后两个指针一起推进。这样设计保证了数学上的集合语义一个元素在并集里只出现一次。观察上面的例子a和b都有3和5但结果里只输出了一份原因就在这个“同时推进”的细节。如果两个区间本身来自std::set那么输出天然有序且无重复。这里要特别强调一个容易误解的点set_union不会对输入做“全局去重”它只负责“合并两个有序区间”去重逻辑是靠“等价时跳过第二个区间的元素”实现的。如果输入本身带有重复结果也会保留某种程度的重复。这个细节我会在第4.4节单独展开。2.2 set_intersection与set_difference交集、差集的分工set_intersection输出同时属于两个区间的元素。实现思路同样是双指针谁小移动谁相等时输出一个然后两边同时前进。例子中a和b共同的元素是3和5所以结果是3 5。set_difference输出“只属于第一个区间”的元素。注意参数顺序决定了结果set_difference(a, b)和set_difference(b, a)完全是两回事。上面例子中set_difference(a,b)的结果是1 7 9而set_difference(b,a)的结果是2 8。实际业务里差集最常见的应用是配置变更对比老配置里有哪些项在新配置里被删掉了就可以用set_difference(老配置, 新配置)筛出来。交集则适合做权限过滤比如用户拥有的权限列表和某个角色模板要求的权限列表取交集就能判断重合范围。2.3 set_symmetric_difference与includes对称差集与子集判断set_symmetric_difference输出“只属于其中一个区间但不同时属于两个区间的元素”也就是set_difference(a,b)和set_difference(b,a)的并集。上面例子中结果是1 2 7 8 9公共的3和5被排除掉了。这个算法非常适合做两个文件的差异对比。比如你要对比两套环境配置想要找出“两边不一致的配置项”对称差集刚好能给出“要么只有A有、要么只有B有”的完整集合。std::includes很多人不熟悉它用来判断第二个区间是不是第一个区间的子集std::vectorint big{1, 2, 3, 4, 5}; std::vectorint small{2, 4}; if (std::includes(big.begin(), big.end(), small.begin(), small.end())) { // small 的所有元素都在 big 中出现 }它和std::find_first_of这类“无序查找”不一样includes要求两个输入都按同一套规则有序然后线性扫描判断。判断权限集合是否满足某个最小权限集就是很典型的用法。3. 真正用起来之前你得搞定输出端这一环3.1 为什么几乎总是和插入迭代器配套出现初学STL的人最容易在输出端翻车set_union这类算法不会帮你开空间它只管把结果写到传入的OutputIt上。你传普通迭代器它就会通过解引用赋值不会自动扩容。所以正确的姿势通常是配一个“插入迭代器”std::back_inserter调用容器的push_backstd::front_inserter调用push_frontstd::inserter(container, position)在指定位置插入。对于std::vector最常用的是back_inserter对std::set就必须用inserter因为set没有push_back成员函数。如果你试图对std::set使用back_inserter编译阶段就会报错这也算是个“编译期帮你拦截错误”的机制。std::setint s1{5, 1, 9}; std::setint s2{3, 9, 7}; std::setint result; std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(result, result.end()));这里inserter(result, result.end())返回的迭代器每次插入时都会把新元素放到容器里并且自动递增输出顺序和算法生成顺序一致。3.2 vector、set、deque输出容器到底怎么选输出容器选vector还是选set取决于你后续对结果的使用方式输出容器常用写法推荐场景注意点std::vectorback_inserter结果需要快速遍历、二分查找、序列化可以预先reserve减少扩容次数std::setinserter结果要频繁做查找、继续保持唯一性自带排序和去重std::dequeback_inserter或front_inserter需要两端操作随机访问性能略弱于vectorstd::listback_inserter需要链表特有操作比如splice遍历开销大一般不做默认选择一个非常实用的性能技巧如果结果要输出到vector先reserve一个足够大的容量再调用算法。std::vectorint a{1, 3, 5, 7, 9}; std::vectorint b{2, 3, 5, 8}; std::vectorint out; out.reserve(a.size() b.size()); std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));并集结果的元素个数最多不超过a.size() b.size()所以用这个值做reserve是安全的。reserve只影响capacity不会改变size因此后续push_back在大多数情况下不会触发重新分配内存性能提升非常明显。如果对vector提前resize也可以直接用普通迭代器作为输出然后用算法返回值截断std::vectorint out(a.size() b.size()); auto end std::set_union(a.begin(), a.end(), b.begin(), b.end(), out.begin()); out.erase(end, out.end());这个写法不需要插入迭代器但你需要清楚结果不会超过预留大小。交集、差集、对称差集的结果规模只会更小所以预留a.size() b.size()永远够用。3.3 自定义类型和比较器operator、lambda与严格弱序当元素不是内置类型时集合算法要求“元素的排序规则是明确的”。你可以给自定义类型重载operator也可以在调用时传一个比较器。我推荐后者因为比较逻辑更显式也能避免污染类型的全局语义。struct User { int id; std::string name; }; std::vectorUser left{{1, a}, {3, c}, {5, e}}; std::vectorUser right{{2, b}, {3, c}, {4, d}}; auto byId [](const User x, const User y) { return x.id y.id; }; std::vectorUser common; std::set_intersection(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(common), byId);这里byId判断两个User是否等价只看id。所以左列表里的User{3, c}和右列表里的User{3, c}被判定为交集元素输出的是左列表中的那个对象。如果两个对象id相同但name不同byId仍然认为它们等价交集只会输出其中一个而不是两个都输出。这是“等价”不等于“相等”的典型体现也是面试中很容易被追问的细节。比较器必须满足严格弱序strict weak ordering基本要求是cmp(x, x)为false如果cmp(a,b)为true那么cmp(b,a)必须为false传递性也要成立。常见反例是写了而不是或者对NaN浮点数做比较。如果你用自定义对象做集合运算建议先写几个std::is_sorted的断言检查输入有序再跑算法能省去很多排查时间。4. 这四类坑我基本都帮你们踩过了4.1 输入未排序最隐蔽也最致命集合算法最坑的一点是输入未排序时不一定报错而是“静静地产出错误结果”。这类问题一旦混入线上逻辑非常难排查因为结果看起来有模有样就是缺几个元素、多几个乱序值。我自己的排查套路是三步第一步先怀疑输入用std::is_sorted验证两个区间是不是真的有序bool ok std::is_sorted(a.begin(), a.end()); bool ok2 std::is_sorted(b.begin(), b.end(), byId);第二步确认数据来源。从std::unordered_map取出的key列表、从文件解析出来的整数、数据库查询返回的列表都不可能天然有序。凡是外部输入我默认它们无序先排序再用。第三步如果两个区间各自有序但结果还是有问题进入下一节说的“比较器不一致”问题。4.2 比较器各玩各的两个范围不是同一套规则第二个高频坑是“两个范围都排好序了但比较器不一致”。比如左区间按id升序排右区间按id降序排或者排序时用byId集合算法时却复制了一份代码改成了byName。这种情况下is_sorted查不出来结果依然错乱。最稳的解法是让“排序比较器、is_sorted检查比较器、集合算法比较器”三处统一使用同一个函数对象struct ById { bool operator()(const User x, const User y) const { return x.id y.id; } }; std::sort(a.begin(), a.end(), ById{}); std::sort(b.begin(), b.end(), ById{}); std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out), ById{});用命名类型而不是两个看起来相同的lambda最大好处是“同一份逻辑天然同步”。lambda虽然好用但如果你在多个地方复制粘贴某次修改只改了一处后面排查起来就非常痛苦。4.3 输出迭代器用错编译报错、结果错乱和性能陷阱输出迭代器用错有三种典型表现编译报错对std::set使用back_inserter报错提示会比较长核心是“没有push_back成员”。看到类似‘push_back’ is not a member of ‘std::setint’立刻把back_inserter换成inserter。结果错乱直接传out.begin()而不是插入迭代器。算法会往已有迭代器位置反复赋值导致越界或者覆盖已有数据。性能陷阱对std::vector用inserter(out, out.begin())每次插入都让后续元素整体搬移复杂度退化成O(N²)数据量稍大就会卡到怀疑人生。一个额外规则输出区间不能和输入区间重叠。标准规定如果输出迭代器指向输入范围内行为是未定义的。有些人想“原地做并集”直接把输出端指向第一个输入区间的开头这是不行的。需要新容器就先开新容器别图省事。4.4 重复元素语义搞反多集合运算的正确姿势重复元素是最让我记忆犹新的一个坑。std::set_union并不是“把两个集合合并成一个不重复集合”这么简单它在两个输入区间包含重复元素时遵循的是多重集合规则并集取每个等价值在两个区间中出现次数的较大者交集取较小者差集取第一个区间次数减第二个区间次数且只取正数部分对称差集取差值的绝对值。看一个std::multiset的例子std::multisetint A{1, 2, 2, 3, 3, 3}; std::multisetint B{2, 2, 3, 3, 4}; std::vectorint u; std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(u)); // u: 1 2 2 3 3 3 4 std::vectorint i; std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(i)); // i: 2 2 3 3 std::vectorint d; std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(d)); // d: 1 3 std::vectorint s; std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(s)); // s: 1 3 4看到没set_union的结果里3出现了三次因为A里有三个3B里有两个3并集取较大者所以是三个。如果你业务上的需求是“两个列表合并且去重”那么必须保证输入本身也没有重复或者把结果插入到std::set里二次去重set_union不会帮你把输入里的重复全部“拍平”。面试里经常拿这个点考察基本功给你两个带重复的有序数组让你求“不重复交集”。正确的思路是先对每个数组做unique或者直接把结果插入std::setint直接调用set_intersection拿到的可能不是“集合意义”上的结果。5. 进阶并行策略、Ranges和算法链上的邻居们5.1 C17执行策略能用但别迷信C17给一批算法增加了执行策略重载集合算法也可以这样写#include execution std::vectorint out; std::set_union(std::execution::par, a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));理论上允许实现并行执行但集合算法本质是“两个有序区间归并”每一步都依赖当前指针位置并行化收益并不像std::sort那么大。我实测过不少数据规模默认串行版本已经很快加了执行策略反而可能引入额外的调度开销。简单结论数据量没到百万级不要给集合算法加并行策略即使到了也要先用性能分析工具确认瓶颈确实在这里。5.2 C20 Ranges投影让map的key运算更清爽C20的Ranges版本给集合算法带来了一个很实用的能力处理std::map时可以直接对key做集合运算不需要再手工提取临时vector。传统写法要先构造两个key列表std::mapint, std::string m1{{1, a}, {2, b}, {3, c}}; std::mapint, std::string m2{{2, b}, {3, d}, {4, e}}; std::vectorint k1, k2; for (auto [k, v] : m1) k1.push_back(k); for (auto [k, v] : m2) k2.push_back(k); std::vectorint shared_keys; std::set_intersection(k1.begin(), k1.end(), k2.begin(), k2.end(), std::back_inserter(shared_keys));C20可以这样#include ranges std::vectorint shared_keys; std::ranges::set_intersection(m1 | std::views::keys, m2 | std::views::keys, std::back_inserter(shared_keys)); // shared_keys: 2 3std::views::keys把map变成只读key视图省掉了临时容器代码也更接近“我要对key做交集”的业务语义。前提是编译器支持C20并开启相应标准选项比如GCC的-stdc20。5.3 和sort、merge、unique的搭配与区别集合算法家族和std::merge、std::unique关系很近需要区分清楚。std::merge合并两个有序区间保留所有元素不去重。std::unique移除“相邻重复”元素通常作用于排序后的区间。std::set_union相当于“合并去重”但它不是先merge再unique实现的而是在归并过程中就处理掉了等价值。如果业务上要求“合并后保留重复项”那就用std::merge如果合并后要去重用std::set_union更直接。还有一个常见操作是“把一个有序区间合并进另一个有序区间并去重”比如两个用户列表合并。直接用set_union一行搞定如果用mergeunique也不是不行但多一次扫描代码也更啰嗦。std::includes和std::lexicographical_compare也容易混淆。includes判断子集关系lexicographical_compare按字典序比较两个区间。前者适合“权限集合是否满足最低要求”这类判断后者适合排序规则下的比较。最后分享一点我的选择偏好我现在写集合运算的代码默认顺序是先确认两个输入已经有序再用reserve和back_inserter输出到vector如果结果要反复查找就改成std::set承接。比较器统一用命名函数对象绝不在两个地方复制粘贴相同的lambda。遇到重复元素相关需求会多问一句“业务上到底要集合语义还是多重集合语义”这个问题想明白了set_union结果里的重复个数再也不会吓到你。STL集合算法只是algorithm里很小的一块但它把有序、比较器、迭代器这三个核心概念串起来了。把这组算法吃透再回头去看std::sort、std::merge、std::unique你会对整个STL的设计意图有更清晰的感觉。

C++ STL集合算法全解析：有序区间上的并集、交集与差集

相关推荐

SpringBoot+Vue医院食堂订餐系统开发实践

代币流通率0.53%真相：穿透销毁幻觉的链上经济审计

宠物猫交易网站模板改造：HTML5+jQuery实现静态页面到询价闭环

更多资讯

PaddleX+YOLOv3实现废水水质目标检测：从数据清洗到模型部署

PDF密码解除技术：原理、工具与实战指南

Gatus 多语言界面配置指南：自定义中文标题、公告与仪表板

ROS2通信接口深度解析：话题、服务、动作与参数实战指南

social-auto-upload 小红书上传运行前提：安装 sau CLI、patchright Chromium 与无头/有头调用方式详解

《道德经》第二章的辩证智慧与现代应用

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？