C++ std::set_union与set_difference _ 集合交并补运算【详解】-C++-PHP中文网

std::set_union输出重复元素是因为它仅归并已排序且无重复的输入，若输入含重复或未排序，结果不可预测；务必先对vector排序并unique+erase，再调用。

c++ std::set_union与set_difference _ 集合交并补运算【详解】

std::set_union 为什么输出结果里有重复元素？

它根本不会去重——std::set_union 只负责合并两个**已排序、无重复**的输入范围，按序归并，遇到相等元素只取一次。如果你传入的容器本身含重复项（比如 std::vector 未去重也未排序），或没提前排序，结果就不可预测，甚至出现重复。

实操建议：

务必确保两个输入范围都已升序排列，且内部无重复（std::set 或 std::vector + std::sort + std::unique）
目标容器需预留足够空间，或用 std::back_inserter；直接写到固定大小数组里容易越界
别指望它“自动当 set 用”：它不检查输入合法性，也不做任何预处理

std::vector<int> a = {1,2,2,3}, b = {2,3,4}; // 含重复！未排序！
std::vector<int> out;
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));
// out 可能是 {1,2,2,3,4} —— 不符合数学并集语义</int></int>

std::set_difference 返回空结果？检查这三个地方

std::set_difference 要求第一个范围是“被减数”，第二个是“减数”，且二者都必须升序。常见空结果原因不是逻辑错，而是输入状态不对。

重点排查：

输入是否真的升序？std::vector 忘了 std::sort 就会逐字节比对，小值在后会导致跳过大量元素
两个范围是否有交集？若 b 完全不包含于 a，结果就是 a 全部保留；但若 a 全在 b 里，结果为空 —— 这是正确行为，不是 bug
迭代器类型是否匹配？比如用 std::set::const_iterator 和 std::vector::iterator 混用，编译可能过，运行行为未定义

std::set<int> a = {1,3,5}, b = {2,4};
std::vector<int> out;
std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));
// out = {1,3,5} —— 正确，因为 b 与 a 无交集</int></int>

用 vector 做输入时，排序+去重的最小安全组合

想拿 std::vector 当集合用，不能只靠 std::sort。标准库所有 set_* 算法都假设输入“严格升序且唯一”，而 std::sort 只管顺序，不管重复。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

可靠写法（C++11 起）：

std::sort(v.begin(), v.end()) → 排好序，重复元素相邻
auto last = std::unique(v.begin(), v.end()) → 移动重复项到末尾，返回新逻辑尾迭代器
v.erase(last, v.end()) → 真正删掉重复元素

漏掉 erase，v 尾部仍存脏数据；只用 unique 不 erase，后续 set_difference 会把那些“看似重复实则残留”的值当成有效元素参与计算。

性能陷阱：反复调用 set_union 处理动态集合？

每次调用 std::set_union 都是 O(m+n) 时间，但如果要持续增删再重算并集，不如直接用 std::set 或 std::unordered_set 维护状态。前者插入 O(log n)，并集可遍历合并；后者平均 O(1)，但不支持有序操作。

权衡点：

输入静态、只算一次 → 用 std::set_union + vector 最轻量
输入频繁变动、需多次求不同组合的并/差 → 改用 std::set 成员函数（如 insert、erase）+ 手动遍历，避免反复排序
不关心顺序、只判存在性 → std::unordered_set 的 insert/erase 更快，但没有现成的 set_difference 等价物，得自己循环 find