c++中如何使用std::set_intersection查找公共元素_c++集合交集【实例】

穿越時空 2026-01-21 00:00:00 次阅读

std::set_intersection要求输入区间已升序排序且目标容器需预分配空间或使用插入迭代器，否则结果未定义；它基于归并思想，不自动排序、不处理重复，适用于已序序列如std::set，对vector等需先sort。

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

它不是“自动对两个容器求交集”的万能函数，而是基于归并思想的算法——只接受 已升序排列 的迭代器范围。如果传入未排序的 std::vector 或 std::list，结果不可预测，甚至可能崩溃。

常见错误现象：std::set_intersection 返回空结果，或输出乱序、重复、越界值
正确做法：先确保两个输入序列都已用 std::sort 排好序（升序），且无重复（虽非强制，但语义上更符合“集合”）
注意：std::set 和 std::multiset 本身有序，可直接用其 begin()/end()

目标容器必须预留足够空间或使用插入迭代器

该算法不负责内存分配，它只是把交集元素逐个写入目标迭代器。若目标是 std::vector，必须提前调用 reserve() 或 resize()；否则写入会越界。

安全推荐：用 std::back_inserter 配合空容器，让元素自动 push_back
性能考虑：若已知最大交集大小（如 std::min(a.size(), b.size())），预分配可避免多次内存重分配
别用普通指针或未初始化的 raw array 迭代器作为输出，容易踩内存坑

完整可用示例：两个 vector 求交集

#include 
#include 
#include 
#include 

int main() {
    std::vector a = {1, 3, 4, 6, 7};
    std::vector b = {2, 3, 4, 5, 7, 8};

    // 注意：a 和 b 必须已排序（本例满足）
    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)
    );

    for (int x : result) {
        std::cout << x << " "; // 输出：3 4 7
    }
    return 0;
}

与 std::set 直接求交的对比差异

如果你的数据天然来自 std::set，可以直接用其迭代器，省去排序步骤；但要注意 std::set_intersection 不处理重复元素逻辑——它按底层序列行为工作，而 std::set 本身无重复。

std::set s1 = {1,2,2,3} 实际存的是 {1,2,3}，所以交集结果也自然去重
但若用 std::vector 存 {1,2,2,3} 并排序后参与 set_intersection，结果仍为 {1,2,2,3} ∩ ... —— 即保留重复，取决于输入是否含重
真正想模拟数学集合交集？先用 std::unique + erase 去重，再调用 set_intersection