C++ 第33题：std::set 元素去重与快速集合交集并集差集运算（set_intersection）

题目

编写程序，读取两组含有重复数字的无序整数列表。分别将其载入 std::set 实现自动去重与升序排序；随后利用 <algorithm> 中的集合算法函数：std::set_intersection（交集）、std::set_union（并集）与 std::set_difference（差集），在 O(M + N) 线性时间内完成两个数学集合的高性能运算。

输入格式：无需外部输入（内置两组测试序列）。

输出格式：依次输出去重后的两集合、交集、并集以及 A-B 差集结果。

数据范围与约定：数学集合运算与线性扫描归并。

思路与算法

1. 集合算法的前提条件
std::set_intersection 等算法要求输入的两个序列必须是已经排序的（Sorted Ranges）。由于 std::set 本身由平衡红黑树驱动，其正向迭代器天然满足升序约束。

2. std::inserter 插入迭代器
接收运算结果时，配合 std::inserter(resultContainer, resultContainer.begin())，能够根据算法输出自动调用容器的 insert 动态接收新元素，无需预先精确计算交并集大小。

3. 双指针线性归并复杂度
不同于无序集合双层遍历的 O(M * N)，在有序序列上求交并集采用双指针单调同向推进，耗时严格受限于 O(M + N)。

完整程序

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <iterator>

void printSet(const std::set<int>& s, const std::string& name) {
    std::cout << name << ": { ";
    for (int x : s) std::cout << x << " ";
    std::cout << "}\n";
}

int main() {
    std::vector<int> rawA = {5, 1, 3, 5, 2, 8, 3};
    std::vector<int> rawB = {3, 8, 4, 9, 8, 2};

    // 1. 利用 std::set 自动去重且自然排成升序
    std::set<int> setA(rawA.begin(), rawA.end());
    std::set<int> setB(rawB.begin(), rawB.end());

    std::cout << "--- 1. 原始集合去重有序化 ---\n";
    printSet(setA, "集合 A");
    printSet(setB, "集合 B");

    // 2. 求交集 A ∩ B
    std::set<int> interSet;
    std::set_intersection(setA.begin(), setA.end(),
                          setB.begin(), setB.end(),
                          std::inserter(interSet, interSet.begin()));

    // 3. 求并集 A ∪ B
    std::set<int> unionSet;
    std::set_union(setA.begin(), setA.end(),
                   setB.begin(), setB.end(),
                   std::inserter(unionSet, unionSet.begin()));

    // 4. 求差集 A - B
    std::set<int> diffSet;
    std::set_difference(setA.begin(), setA.end(),
                        setB.begin(), setB.end(),
                        std::inserter(diffSet, diffSet.begin()));

    std::cout << "\n--- 2. 标准集合代数运算结果 ---\n";
    printSet(interSet, "交集 (A ∩ B)");
    printSet(unionSet, "并集 (A ∪ B)");
    printSet(diffSet, "差集 (A - B)");

    return 0;
}

运行示例

输出：

--- 1. 原始集合去重有序化 ---
集合 A: { 1 2 3 5 8 }
集合 B: { 2 3 4 8 9 }

--- 2. 标准集合代数运算结果 ---
交集 (A ∩ B): { 2 3 8 }
并集 (A ∪ B): { 1 2 3 4 5 8 9 }
差集 (A - B): { 1 5 }