首页 > 营销学院 > 技术知识

c++中如何求两个集合的交集_c++ set_intersection用法

std::set_intersection要求两输入区间均已升序排列，仅接受迭代器范围而非容器本身；对vector需先sort，对set可直接用begin()/end()；输出须用独立容器配合back_inserter或手动resize截断，且自定义比较器必须一致。

set_intersection 要求输入是已排序区间

std::set_intersection 不接受 std::set 对象直接传入，它只操作**迭代器范围**，且明确要求两个输入范围都已升序排列。如果你拿 std::vector 或原始数组调用它，必须先确保它们有序；若用 std::set，虽然其内部有序，但你仍需传入 begin()/end() 迭代器，不能传容器本身。

常见错误是把无序 std::vector 直接送进去，结果输出为空或乱序片段——这不是函数 bug，而是前提不满足。

对 std::set：可直接用 s1.begin(), s1.end(), s2.begin(), s2.end()
对 std::vector：务必先调用 std::sort，否则行为未定义
输出容器（如 std::vector）需预留足够空间，或用 std::back_inserter

输出目标必须能接收插入，且不能和输入重叠

输出迭代器指向的目标容器不能是任一输入容器的子区间，也不能与输入迭代器指向的内存重叠——否则结果未定义。最安全做法是用独立容器 + std::back_inserter。

例如，不能写成 set_intersection(a.begin(), a.end(), b.begin(), b.end(), a.begin())，即使 a 足够大也不行；也不能用 std::array 的原生指针而没确认长度。

推荐：用 std::vector result; set_intersection(..., std::back_inserter(result))
手动分配空间：需先调用 result.resize(std::min(a.size(), b.size()))，再用 result.begin()，最后用 result.erase(it, result.end()) 截断
输出类型必须和输入元素类型一致或可隐式转换

自定义比较函数要两边一致

如果集合按降序排列，或用了自定义比较（比如 std::set>），那么 set_intersection 的第五个参数必须传入**完全相同的比较器**，否则逻辑错乱。

例如，两个 std::set<:string std::less>> 可以直接用默认版本；但若其中一个是 std::greater，就必须显式传入对应函数对象。

默认调用：set_intersection(a.begin(), a.end(), b.begin(), b.end(), out)
自定义比较：set_intersection(a.begin(), a.end(), b.begin(), b.end(), out, std::greater{})
lambda 也可，但注意生命周期：不能捕获局部变量并用于多线程场景

完整可用示例（含 vector 和 set 两种情况）

#include 
#include 
#include 
#include 

int main() {
    // 情况1：两个 std::set（天然有序）
    std::set s1 = {1, 3, 5, 7, 9};
    std::set s2 = {3, 4, 5, 6, 7};
    std::vector v_result;
    std::set_intersection(s1.begin(), s1.end(),
                          s2.begin(), s2.end(),
                          std::back_inserter(v_result));
    // v_result == {3, 5, 7}

    // 情况2：两个 vector（需先排序）
    std::vector v1 = {5, 1, 7, 3};
    std::vector v2 = {7, 4, 3, 6};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    std::vector v2_result;
    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v2_result));
    // v2_result == {3, 7}
}

注意：std::set_intersection 返回的是输出迭代器末位置，不返回交集大小；如果需要，得自己算 std::distance 或依赖 back_inserter 后容器的 size()。实际项目中，除非性能极端敏感，否则优先用 back_inserter —— 它省去容量预估，也避免越界风险。

# go # ai # c++ # ios # stream # 排列 # 隐式转换 # less # String # Array # sort # 局部变量 # int # Lambda # 指针 # 线程 # 多线程 # 对象 # bug # 自定义 # 迭代 # 升序 # 也不 # 可直接 # 的是 # 如果你 # 两种 # 也可 # 用了