集合算法：set_union、set_intersection、set_difference、set_symmetric_difference
集合操作，说白了就是数学里的并集、交集、差集这些概念。C++ STL 把这套东西搬到了容器上，用四个算法函数搞定。我当年刚接触时觉得这玩意儿不就是数学课上的东西吗？后来在项目里做数据清洗，才发现它有多实用。
先说说前提条件
这四个算法有个共同要求：输入的两个区间必须是有序的。默认按 operator< 升序排列。如果你传进去的是乱序数据，结果就是错的，而且编译器不会给你任何警告。
注意： 我曾经在代码里传了两个无序的 vector，结果 set_union 返回了一堆重复元素。排查了半天才发现是忘记排序了。嗯，从那以后我写集合算法前都会先确认数据是否有序。
set_union：求并集
把两个集合的元素合并到一起，重复的只保留一份。说白了就是「你有我有全都有」。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main() {
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
// result: 1 2 3 4 5 6 7
for (int x : result) std::cout << x << " ";
return 0;
}我个人习惯用 back_inserter 来接收结果，省得手动管理内存。你想想看，如果目标容器空间不够，程序直接崩掉，多冤。
set_intersection：求交集
只保留两个集合都有的元素。这个在项目里用得最多，比如找两个用户群体的共同特征。
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
// result: 3 4 5
小技巧： 如果两个集合都是有序的，set_intersection 的时间复杂度是 O(n+m)，比暴力遍历快得多。我在做日志分析时，经常用这个函数来找出两个时间段内都出现的错误码。
set_difference：求差集
返回在第一个集合中但不在第二个集合中的元素。注意方向：v1 - v2 和 v2 - v1 结果不一样。
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
// result: 1 2我建议你在使用差集时，先想清楚「谁减谁」。曾经有个同事把参数顺序搞反了，结果数据对不上，查了两天才发现是差集方向错了。
set_symmetric_difference：求对称差集
返回两个集合中「你有我没有，我有你没有」的元素。说白了就是并集减去交集。
std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_symmetric_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result));
// result: 1 2 6 7四个算法的关系图
下面这张图可以帮你快速理解它们之间的关系：
自定义比较函数
如果你的元素不是基本类型，或者你想用不同的排序规则，可以传入自定义比较函数。比如按字符串长度排序：
bool compareByLength(const std::string& a, const std::string& b) {
return a.size() < b.size();
}
std::vector<std::string> v1 = {"cat", "dog", "bird"};
std::vector<std::string> v2 = {"fish", "bird", "ant"};
std::vector<std::string> result;
std::set_union(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(result),
compareByLength);
重要提醒： 自定义比较函数必须满足严格弱序（strict weak ordering）的要求。说白了就是：不能出现 a < b 且 b < a 同时成立的情况。我曾经用了一个不满足这个条件的比较函数，结果 set_union 返回的结果里出现了重复元素，调试了很久才发现问题。
性能与注意事项
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| set_union | O(n+m) | O(n+m) | 合并两个有序列表 |
| set_intersection | O(n+m) | O(min(n,m)) | 查找共同元素 |
| set_difference | O(n+m) | O(n) | 找出独有元素 |
| set_symmetric_difference | O(n+m) | O(n+m) | 找出差异元素 |
核心要点：
- 输入区间必须有序，否则结果不可预测
- 目标容器要有足够的空间，建议用 back_inserter
- 自定义比较函数要满足严格弱序
- 这四个算法都是稳定的，不会改变元素的相对顺序
嗯，集合算法就这些内容。我个人觉得，掌握这四个函数的关键在于理解它们背后的数学概念，然后记住「有序」这个前提条件。你在实际项目中用上几次，自然就熟练了。