c++中如何使用std::set_union求并集_c++容器合并算法详解【汇总】

std::set_union 不是对 std::set 求并集的函数，而是对两个已排序迭代器范围执行归并去重操作；它要求输入有序、输出需手动管理空间或使用插入器，返回输出迭代器末位置。

std::set_union 不能求并集，它求的是有序序列的“并集”（实际是合并去重）

很多人第一次看到 std::set_union 名字就默认它能像 Python 的 set.union() 那样直接对两个 std::set 求并集——这是常见误解。它不接受 std::set 容器本身作参数，只接受**已排序的迭代器范围**（比如数组、std::vector 或 std::set::begin()/end()），且输出结果仍是有序、去重的序列，但**不是容器**，只是把结果写入你提供的目标区间。

真正对两个 std::set 求并集，更自然的做法是用 insert 成员函数或 std::set_union + 输出迭代器配合 std::inserter。

用 std::set_union 合并两个 std::set 的正确写法

必须满足：输入范围已排序（std::set 天然满足）、目标容器足够大或使用插入型迭代器、包含头文件 和 。

• std::set_union 不修改原容器，只读取；输出需由你确保空间或用插入器
• 若目标是新 std::set，推荐用 std::inserter，避免手动预分配大小
• 若目标是 std::vector，需提前 resize 至最多 a.size() + b.size()，再用 back_inserter 更安全

std::set a = {1, 2, 4, 5};
std::set b = {2, 3, 5, 6};
std::set result;

std::set_union(a.begin(), a.end(),
                b.begin(), b.end(),
                std::inserter(result, result.begin()));

和 set::insert 直接合并比，有什么区别？

std::set::insert 支持范围插入，语法简洁，底层仍走红黑树插入逻辑；std::set_union 是归并算法（O(m+n) 时间），适合已排序数据流或需要中间处理的场景。

Designer

Microsoft推出的图形设计应用程序

下载

立即学习“C++免费学习笔记（深入）”；

• a.insert(b.begin(), b.end()) 更常用、更直观，适用于大多数“把 b 全部加进 a”的需求
• std::set_union 优势在于：可自定义比较器、可跳过某些元素、可写入任意容器（包括非关联容器）、支持并行化（C++17 起有执行策略重载）
• 若 a 和 b 是 std::vector 且已排序，set_union 比先转 set 再 insert 快得多

容易踩的坑：输出迭代器没初始化或越界

最典型错误是传一个空 std::vector 的 begin() 给 set_union ——它不会自动扩容，导致未定义行为。

• 别用 vec.begin() 当输出目标，除非你刚 vec.resize(n)
• 优先选 std::back_inserter(vec) 或 std::inserter(set, it)
• 注意 set_union 返回的是输出迭代器末位置，可用于检查实际写入长度（但通常不需要）
• 两个输入范围必须严格升序；若用 std::greater 排序，要显式传入相同比较器，否则结果错乱

std::vector a = {1, 3, 5}, b = {2, 4, 5};
std::vector out;
out.reserve(a.size() + b.size()); // 预留空间
std::set_union(a.begin(), a.end(),
                b.begin(), b.end(),
                std::back_inserter(out)); // 安全