c++中如何使用set_union_c++合并两个有序集合的方法【实例】

std::set_union 是 中的泛型算法，用于合并两个已排序区间，要求输入升序、输出预留空间或使用插入迭代器，时间复杂度 O(m+n)，返回尾后迭代器以确定实际结果长度。

标准库没有 set_union_c++ 这个函数，你实际想用的是 std::set_union —— 它是 中的泛型算法，用于合并两个**已排序的区间**（不一定是 std::set），结果写入目标容器，且保持有序、去重（类似数学并集）。

std::set_union 的基本用法和参数要求

它不操作 std::set 对象本身，而是接受两个左闭右开的迭代器范围（如 vec1.begin(), vec1.end()），要求输入范围**升序排列**，输出目标也需有足够空间或使用插入迭代器。

• 头文件必须包含 和 （如果用 std::back_inserter）
• 两个输入序列必须已排序，否则行为未定义（常见表现：结果重复、漏元素、甚至崩溃）
• 输出容器不会自动扩容；若用普通迭代器（如 out.begin()），需提前预留空间（resize 或 reserve 后 resize）
• 支持自定义比较器，例如降序合并需传入 std::greater{}

std::vector a = {1, 2, 4, 5};
std::vector b = {2, 3, 5, 6};
std::vector out;
out.resize(a.size() + b.size()); // 预留最坏情况空间
auto it = std::set_union(a.begin(), a.end(),
                         b.begin(), b.end(),
                         out.begin());
out.resize(it - out.begin()); // 调整为实际大小
// out 现在是 {1, 2, 3, 4, 5, 6}

合并 std::set 时的常见错误写法

直接把 std::set 的 begin()/end() 传给 std::set_union 没问题（因为 std::set 迭代器天然有序），但输出不能直接写回原 std::set —— 它不支持随机访问迭代器，也不能用 begin() 作为输出起点。

• ❌ 错误：std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), s1.begin()) —— s1.begin() 是 const 迭代器，且 std::set 不支持赋值式写入
• ✅ 正确做法：输出到 std::vector 或 std::deque，再用该结果构造新 std

  

  ::set，或用 std::inserter

std::set s1 = {1, 2, 4};
std::set s2 = {2, 3, 5};
std::set result;
std::set_union(s1.begin(), s1.end(),
                s2.begin(), s2.end(),
                std::inserter(result, result.end()));

性能与底层逻辑：为什么不是“集合合并”而是“有序区间合并”

std::set_union 时间复杂度是 O(m + n)，本质是双指针归并：逐个比较两序列首元素，取较小者推进，相等只取一次。它不关心数据结构，只依赖“已排序”这一前提。

• 对 std::vector 排好序后调用，比反复插入 std::set 快得多（后者是 O((m+n) log(m+n))）
• 若原始数据来自 std::set，且你只需要并集结果（不要求仍是 std::set），转成 vector 再 set_union 更高效
• 注意：std::set_union 不处理重复值跨区间出现多次的问题——只要输入各自有序且无内部重复（如 std::set），结果就严格去重；但如果输入是 vector 且含重复（如 {1,1,2}），它仍会按顺序合并，可能保留重复（取决于相邻是否相等）

容易被忽略的边界情况

空输入、全相同、一个完全包含另一个，这些都合法，std::set_union 能正确处理，但输出迭代器位置容易误判。

• 返回值是输出区间的**尾后迭代器**，必须用它来确定实际写入长度；仅靠输入 size 相加估算会出错
• 如果输出用 std::back_inserter，无需 resize，但要注意目标容器类型（std::vector 的 push_back 可能触发多次 realloc）
• 使用自定义类型时，比较器必须和排序时一致，否则结果不可预测

std::vector x, y, z;
// ... x 和 y 已排序
std::set_union(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(z));
// z 现在就是正确并集，无需 resize 或调整

真正要小心的不是语法，而是「输入是否真有序」和「输出迭代器是否有效」——这两个点一旦出错，结果静默错误，很难调试。