C++ 中 set_union：不是“把两个集合加起来”那么简单

刚学 STL 算法时，看到 set_union 这个名字，我下意识以为它就是“把两个 set 合并成一个新 set”——就像往咖啡里加奶，一倒就完事。结果第一次用，传了两个 vector，还手动排了序，结果输出里一堆重复数字，调试半小时才发现：它不检查输入是否真的“是集合”，也不自动去重，更不关心你传的是不是 set 容器。

set_union 的名字里带 “set”，但它的行为和 std::set 容器本身几乎无关。它只是一个基于有序范围的归并算法，核心契约只有两条：
✅ 输入区间必须已升序排列；
✅ 输出区间不会自动去重——它只保留“在任一输入中出现过”的元素，但若某元素在 A 和 B 里各出现一次，它只写一次；若在 A 里出现两次（比如 [1,1,2]），而 B 是 [1,3]，那输出是 [1,1,2,3]——它按值归并，不按集合语义去重。

这才是新手踩坑最多的地方：以为用了 set_union 就安全了，结果数据没预处理，或者误以为它能替代 std::set 的插入逻辑。

实际怎么用？先看一个不翻车的最小闭环

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> a = {1, 3, 5, 7};
    std::vector<int> b = {2, 3, 6, 7, 9};

    std::vector<int> out;
    out.resize(a.size() + b.size()); // 预分配足够空间

    auto it = std::set_union(a.begin(), a.end(),
                             b.begin(), b.end(),
                             out.begin());

    out.erase(it, out.end()); // 关键！截掉未使用的尾部
    for (int x : out) std::cout << x << " "; // 输出：1 2 3 5 6 7 9
}

注意三个实操细节：

• 必须预分配输出容器空间，否则 set_union 会越界写入；
• 返回的是输出区间的“新末尾迭代器”，不是 void，别丢了；
• 手动 erase 截断，不然 out 里堆着垃圾值。

这三步漏一步，程序就可能静默出错，或者输出乱码。

为什么非得排序？它到底在做什么？

set_union 的底层逻辑非常朴素：双指针归并。
它像两个同学一起翻两本按页码排好的电话簿，A 指向当前最小未处理号码，B 同理。比较两者：

• 若相等，只记一次，两个指针都进一格；
• 若 A 小，记 A，A 指针进一格；
• 若 B 小，记 B，B 指针进一格。

全程不查哈希、不建红黑树、不调 find——它只依赖“顺序可比较”这一件事。所以哪怕你用 list 存有序数据，只要提供随机访问迭代器（不行，得转成 vector 或用 inserter），它照样能跑。

这也解释了为什么它不接受无序容器：没有顺序，双指针就失去意义。

和 std::set 的 insert 或 merge 有什么区别？

有人会问：我直接 set<int> s; s.insert(a.begin(),a.end()); s.insert(b.begin(),b.end()); 不更简单？

确实更简单，但代价不同：

• set::insert 是 O(N log N)，每次插入都做树平衡；
• set_union 是 O(N + M)，纯线性扫描，前提是你已经排好序；
• 如果你的数据本来就是排序后产生的（比如日志按时间戳落盘、搜索结果已按相关性排序），那 set_union 就是零成本归并——它不重新排序，只归并。

再进一步：C++17 引入了 std::set::merge，它能把另一个 set 的节点“挪”过来，避免复制。但那是容器专属操作，而 set_union 是泛型算法，能跨容器类型工作——vector 和 array 能混用，甚至能和 C 数组配合（只要传对指针）。

一个真实场景：合并两个时间窗口事件流

假设你在写监控系统，A 模块每秒上报 CPU 使用率（已按时间戳升序），B 模块上报内存使用率（也已升序）。你想生成一份“所有指标变化点”的联合时间线，且同一毫秒只记一次（避免重复打点）。

这时 set_union 就是天然选择：

• 输入是两个 vector<timestamp>，天然有序；
• 输出是去重后的时间点序列；
• 不需要构造任何 set 对象，内存零额外开销；
• 可以直接用 back_inserter 接收结果，不用预估大小：

std::vector<int> timeline;
std::set_union(a.begin(), a.end(),
                b.begin(), b.end(),
                std::back_inserter(timeline));

比手写归并循环干净，比塞进 set 节省至少一个数量级的常数开销。

最后提醒一句：它不负责“集合语义”

如果你真需要数学意义上的并集（即输入本身可能含重复，但输出必须严格去重），set_union 不够用。它只保证：每个值在输出中出现的次数，等于它在两个输入中各自出现次数的最大值。
想严格去重？要么提前用 std::unique 清洗输入，要么用 std::set 插入，或者自己写个 unordered_set 缓存判重——但那就脱离 set_union 的设计初衷了。

理解它的边界，反而能用得更稳。

set_union 不是万能钥匙，但当你手上有两把排好序的锁，它就是最快打开第三把门的那根铁丝。