C++ set_intersection求交集 _ algorithm库集合操作【实战】

先来一个最核心的认知：set_intersection 之所以要求输入区间必须有序，是因为它本质上就是双指针归并的变体——不排序、不查重、不建哈希表，只做一件事：线性扫描比对。两个输入范围按同一规则升序排列后，算法逐位比较，发现 range1[i] < range2[j] 就跳过前者，大于则跳过后者，相等才写入结果。如果输入没排序，结果要么漏掉交集元素，严重时直接越界崩溃。

为什么 set_intersection 要求输入必须是已排序区间？

常见的翻车现场：set_intersection 返回空结果，但肉眼可见两容器明明有相同值；或者程序在 debug 模式下直接触发断言失败（比如 MSVC 的 “iterator not dereferencable”）。别慌，debug 方向很明确：

• 使用前务必确认：两个输入容器都已用 std::sort 排好序，或者本身就是 std::set/std::multiset（它们天然有序）。
• 绝对不要对 std::vector 直接调用 set_intersection 而不先 std::sort。
• 注意比较谓词一致性：排序和 set_intersection 必须用相同的 Compare（比如都用 std::greater() 降序，不能一个升序一个降序）。

set_intersection 的输出迭代器必须能容纳足够空间

这个坑尤其隐蔽——它不会自动扩容目标容器，只是把交集元素逐个写入你提供的输出迭代器所指向的位置。用 std::back_inserter 当然没问题，但若用普通指针或 vector.begin()，就必须提前确保目标容器 size ≥ 预期交集大小，否则越界写入（UB）。

典型症状：程序崩溃、输出结果错乱、后续变量被意外覆盖（尤其用原生数组或固定大小 vector 时）。

• 安全做法：用 std::vector + std::back_inserter(result)。
• 想预分配空间？先估算上限（比如取 min(size1, size2)），再用 result.resize(upper_bound)，最后用 result.begin() 传入，并记录实际写入长度（set_intersection 返回的是结束迭代器）。
• 别忘了：返回值是输出区间的“尾后迭代器”，不是元素个数；要算长度得用 std::distance 或减法（仅对随机访问迭代器）。

处理重复元素：用 set 还是 multiset？

set_intersection 本身不区分集合语义还是多重集合语义——它只忠实执行“归并交集”逻辑。所以输入如果是 std::multiset，相同值出现多次时，交集会保留“最小频次”对应的次数（即 A 有 3 个 5，B 有 2 个 5 → 结果含 2 个 5）。而 std::set 天然去重，每个值最多一次，交集也至多一个。

• 需要保留重复交集？选 std::multiset 或排序后的 std::vector（含重复）。
• 只要唯一值？用 std::set 最省心，且自带排序。
• 注意：std::vector 即使排好序，也不自动去重；若原始数据含重，交集也会反映该重复逻辑。

性能和兼容性：为什么不用 std::unordered_set 求交？

set_intersection 是 O(n + m) 时间复杂度，常数极小，缓存友好。而用 unordered_set 做交集（遍历一个，查另一个）虽平均 O(n)，但哈希冲突、内存分散、构造哈希表开销大，实际往往更慢，尤其数据量不大（<1000）。更重要的是：标准库没有提供基于哈希的交集算法，你得手写循环+find，还要自己管理内存和去重逻辑。

• 场景优先级：已排序数据 → 无条件选 set_intersection。
• 原始数据未排序且量大 → 先排序再交，通常仍快于建哈希表。
• 真要哈希交集？用 std::unordered_set 构造 + std::copy_if + count，但记得去重输出（如果需要集合语义）。
• 别指望 set_intersection 支持任意容器：它要求前向迭代器以上，且输入必须有序；list 不行（除非先转 vector 或用 sort 成员函数）。

最容易被忽略的一点：set_intersection 对“相等”的定义完全依赖你传入的 Compare，而不是 operator==。比如用 [](int a, int b) { return a % 10 < b % 10; } 排序，那么交集也是按个位数相等来判断的——这和直觉可能不符。