常用集合算法：set_intersection、set_union、set_difference

集合算法，说白了就是处理两个有序序列的「交、并、差」运算。这三个算法在 STL 里属于 <algorithm> 头文件，使用频率其实挺高的——尤其是当你需要做数据比对、去重合并或者筛选差异的时候。

我个人习惯把它们叫做「三兄弟」，因为它们的接口长得几乎一模一样，只是底层逻辑不同。今天我们就一个一个拆开来看。

1. set_intersection：求交集

交集，就是两个集合中都有的元素。STL 提供的 set_intersection 会遍历两个有序区间，把共同出现的元素拷贝到目标容器中。

先看一个最简单的例子：

#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;

    // 注意：目标容器需要提前分配空间，或者用 back_inserter
    std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(result)
    );

    for (int x : result) {
        std::cout << x << " ";  // 输出：3 4 5
    }
    return 0;
}

这里有个坑，我刚开始用的时候踩过——目标容器必须提前预留空间。如果你直接传 result.begin() 进去，而 result 是空的，那程序会直接崩溃。用 std::back_inserter 是最稳妥的方式，它会自动调用 push_back。

2. set_union：求并集

并集，就是把两个集合合并到一起，重复的元素只保留一份。这个算法在数据合并场景下非常实用。

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

你看，输出结果是 1 2 3 4 5 6 7，重复的 3、4、5 只出现了一次。这个算法内部是怎么处理的呢？它同时遍历两个序列，每次取较小的那个元素放入结果，如果相等就只放一次，然后两个迭代器都前进。

我在项目中遇到过这样一个场景：需要合并两个不同来源的日志 ID 列表，而且要去重。当时直接用 set_union 一行搞定，比手动写循环优雅多了。

3. set_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_difference(
    v1.begin(), v1.end(),
    v2.begin(), v2.end(),
    std::back_inserter(result)
);

// result: 1 2

输出是 1 和 2，因为这两个元素在 v1 中，但不在 v2 中。注意顺序：第一个集合减第二个集合，不是对称差集。

如果你想要「对称差集」（即在 v1 不在 v2，或在 v2 不在 v1 的元素），STL 也提供了 set_symmetric_difference：

std::set_symmetric_difference(
    v1.begin(), v1.end(),
    v2.begin(), v2.end(),
    std::back_inserter(result)
);

// result: 1 2 6 7

嗯，这里要注意：对称差集的结果是两个集合中「独有」的元素，不包含共同部分。

4. 三个算法的对比总结

算法	含义	结果示例（v1={1,2,3,4,5}, v2={3,4,5,6,7}）	典型应用场景
set_intersection	交集	3 4 5	找出共同元素
set_union	并集	1 2 3 4 5 6 7	合并去重
set_difference	差集	1 2	找出新增/删除项
set_symmetric_difference	对称差集	1 2 6 7	找出独有项

5. 避坑指南与性能建议

我曾经在线上环境踩过一个坑：两个 vector 没有排序就直接调了 set_intersection，结果返回了一堆乱码。排查了半天才发现是排序问题。所以我的建议是：调用前务必确认序列已排序，可以用 std::is_sorted 做一次断言检查。

另外，这些算法的时间复杂度都是 O(n+m)，n 和 m 分别是两个序列的长度。因为它们是线性遍历，性能相当不错。但如果你的数据量特别大（比如百万级），可以考虑用 std::execution::par 并行策略——不过前提是你的编译器支持 C++17 的并行算法。

6. 知识体系结构图

下面这张图帮你理清三个算法的关系和使用流程：

这张图展示了从两个有序序列输入，到选择具体算法，再到输出结果的完整流程。你可以把它当作一个快速决策指南——先确认数据有序，再根据业务需求选算法。

7. 实际项目中的组合用法

最后分享一个我在项目中用过的组合技巧：有时候你需要同时知道「新增了哪些、删除了哪些、哪些没变」。这时候可以配合 set_difference 和 set_intersection 一起用：

// 假设 oldList 是旧数据，newList 是新数据
std::vector<int> added;   // 新增的
std::vector<int> removed; // 删除的
std::vector<int> kept;    // 保留的

// 新增的 = 新数据 - 旧数据
std::set_difference(
    newList.begin(), newList.end(),
    oldList.begin(), oldList.end(),
    std::back_inserter(added)
);

// 删除的 = 旧数据 - 新数据
std::set_difference(
    oldList.begin(), oldList.end(),
    newList.begin(), newList.end(),
    std::back_inserter(removed)
);

// 保留的 = 交集
std::set_intersection(
    oldList.begin(), oldList.end(),
    newList.begin(), newList.end(),
    std::back_inserter(kept)
);

这个模式在数据同步、缓存更新、版本对比等场景下非常实用。你想想看，如果用手动循环去实现，至少得写十几行代码，还容易出错。STL 三兄弟一出马，三行搞定。

好了，集合算法就聊到这里。记住一句话：有序是前提，back_inserter 是标配，选对算法是关键。下次遇到集合运算需求，直接掏出这三个工具，准没错。

---