C++中如何使用std::set_intersection_C++计算两个向量交集【备忘】

std::set_intersection要求输入已排序，否则结果不可预测；它按多集语义保留重复元素（取最小出现次数）；无序场景推荐用unordered_set实现O(n+m)交集，注意包含

std::set_intersection 要求输入必须已排序

直接对两个无序 std::vector 调用 std::set_intersection 不会报错，但结果不可预测——它只比较相邻等价元素，不进行查找或哈希。你得到的“交集”大概率为空或残缺。

正确做法是先排序再求交：

• 对两个 std::vector 分别调用 std::sort（注意：会改变原顺序）
• 用 std::set_intersection 写入目标容器，目标容器需预留足够空间或用 std::back_inserter
• 若需保持原向量不变，先拷贝再排序

std::vector a = {3, 1, 4, 1}, b = {2, 1, 3, 5}; std::sort(a.begin(), a.end());  // → {1,1,3,4} std::sort(b.begin(), b.end());  // → {1,2,3,5} std::vector result; result.reserve(std::min(a.size(), b.size())); std::set_intersection(a.begin(), a.end(),                       b.begin(), b.end(),                       std::back_inserter(result)); // result == {1,3}

std::set_intersection 保留重复元素的规则

它不是集合意义上的“去重交集”，而是**多集（multiset）语义**：每个元素在结果中出现的次数，等于它在两个输入中各自出现次数的最小值。

比如 a = {1,1,2,2,2}、b = {1,1,1,2}，交集是 {1,1,2}（1 出现 min(2,3)=2 次，2 出现 min(3,1)=1 次）。

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

• 若你想要数学集合交集（每个值最多一次），需先用 std::set 去重，或对结果去重
• 若输入含重复且你不需要重复，可在调用前用 std::unique + erase 预处理（但注意：仅对已排序序列有效）

用 unordered_set 实现 O(n+m) 无序交集更实用

当原始数据无序、且你只关心“是否存在”而非“出现几次”时，std::set_intersection 的排序开销（O(n log n + m log m)）往往得不偿失。

更常见、更高效的做法是：

• 将较小的向量转为 std::unordered_set
• 遍历较大的向量，用 count() 或 find() 判断是否在集合中
• 插入结果时可顺便去重（unordered_set 自带）

std::vector a = {3, 1, 4, 1}, b = {2, 1, 3, 5}; std::unordered_set set_a(a.begin(), a.end());  // {1,3,4} std::vector result; for (int x : b) {     if (set_a.count(x)) result.push_back(x); } // result == {1,3}（顺序与 b 一致，无重复）

注意：这里没排序，也不要求输入有序，时间复杂度约 O(n + m)，适合大多数实际场景。

编译器和头文件容易漏掉的点

std::set_intersection 在 中，不是 ；而 std::unordered_set 在 中。少引一个就编译失败。

• 使用 std::back_inserter 必须包含
• 若用 std::set 替代 vector 存储输入，它自动有序，可跳过 sort 步骤，但插入代价更高
• 所有迭代器参数必须同类型（比如不能混用 const_iterator 和 iterator，除非明确兼容）

真正卡住人的往往不是算法逻辑，而是这些隐式前提和头文件依赖——写完编译不过，先查这三个头文件齐了没：、、（按需）。