c++中如何使用set_intersection_c++求两个集合交集的方法【详解】-C++-PHP中文网

std::set_intersection 是定义在中的泛型算法，要求两输入范围已排序（升序或统一自定义序），不依赖 std::set；需传入迭代器、预留输出空间或用 std::back_inserter，返回输出迭代器末尾。

c++中如何使用set_intersection_c++求两个集合交集的方法【详解】

std::set_intersection 不是函数名，而是里的算法

很多人搜 set_intersection_c++，以为是个独立函数或类成员，其实它是 std::set_intersection —— 一个定义在头文件中的泛型算法，**不依赖 std::set，也不要求输入是 set**。它只对两个**已排序的范围**做交集操作。

常见错误现象：no matching function for call to 'set_intersection'，往往是因为没传迭代器、没排序、或输出容器没预留空间。

必须传入两个升序范围（如 vector 排好序的，或 set::begin()/set::end()）
第三个参数是输出迭代器，不会自动扩容，得提前分配空间或用 std::back_inserter
返回的是输出迭代器的末尾位置，不是交集大小

用 vector + sort + set_intersection 求交集（最常用）

这是最灵活的方式：输入可以是任意容器（甚至数组），只要先排好序。适合数据量不大、不频繁查询的场景。

std::vector<int> a = {1, 2, 4, 5, 6};
std::vector<int> b = {2, 3, 5, 7};
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());

std::vector<int> result;
result.reserve(std::min(a.size(), b.size())); // 预留上限空间
std::set_intersection(a.begin(), a.end(),
                      b.begin(), b.end(),
                      std::back_inserter(result));</int></int></int>

注意：std::back_inserter(result) 自动调用 push_back，比手动用 result.begin() 安全；但若用后者，必须确保 result 足够大（比如 resize 到 a.size()）。

直接用 set::begin()/end() 调用 set_intersection

std::set 本身有序，所以可以直接传迭代器，无需额外排序。但要注意：输出容器类型仍需支持插入，且结果仍是普通容器（不是 set）。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

std::set<int> s1 = {1, 2, 4, 5};
std::set<int> s2 = {2, 3, 5, 6};
std::vector<int> result;
std::set_intersection(s1.begin(), s1.end(),
                      s2.begin(), s2.end(),
                      std::back_inserter(result)); // result = {2, 5}</int></int></int>

性能影响：虽然 set 迭代器是有序的，但 std::set_intersection 是线性扫描（O(m+n)），不是二分查找。如果只查一次交集，这样写没问题；如果高频查询，不如用 unordered_set 的哈希查找（但那就不能用 set_intersection 了）。

自定义比较规则（比如降序交集或忽略大小写）

std::set_intersection 第五个参数可传自定义谓词。但注意：**两个输入范围必须按同一规则排序**，否则行为未定义。

降序交集：两个 vector 都用 std::greater() 排序，然后传相同谓词
字符串忽略大小写：需自定义 compare_nocase，且输入容器必须已按该规则排好序
错误示范：一个升序一个降序，或谓词和实际排序顺序不一致 → 结果错乱

示例（降序）：

std::vector<int> a = {5, 4, 2, 1};
std::vector<int> b = {6, 5, 3, 2};
std::sort(a.begin(), a.end(), std::greater<int>());
std::sort(b.begin(), b.end(), std::greater<int>());
std::vector<int> result;
std::set_intersection(a.begin(), a.end(),
                      b.begin(), b.end(),
                      std::back_inserter(result),
                      std::greater<int>()); // result = {5, 2}</int></int></int></int></int></int>

最容易被忽略的一点：算法本身不验证输入是否真有序。调试时如果交集为空或漏元素，第一反应不该是改逻辑，而是检查排序和谓词是否真正匹配。