C++ STL 容器 set 的交集并集操作

C++ STL 容器 set 的基本介绍

在 C++ 的标准模板库（STL）中，set 是一种关联容器，它存储的元素是唯一的，并且会按照特定的顺序自动排序。默认情况下，set 中的元素会按照升序排列。set 容器的底层通常实现为红黑树，这使得它在插入、删除和查找操作上具有对数级别的时间复杂度，即平均情况下为 $O(\log n)$，其中 n 是 set 中元素的个数。

下面是一个简单创建和使用 set 的示例代码：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 插入元素
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(2);

    // 遍历 set
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 查找元素
    if (mySet.find(2) != mySet.end()) {
        std::cout << "2 存在于 set 中" << std::endl;
    }

    // 删除元素
    mySet.erase(1);
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，我们首先创建了一个 std::set<int> 类型的 mySet。接着使用 insert 方法插入了几个元素，由于 set 会自动排序，所以输出时元素是按升序排列的。然后使用 find 方法查找元素是否存在，最后使用 erase 方法删除元素。

交集操作

原理

两个 set 的交集是指既存在于第一个 set 又存在于第二个 set 中的所有元素的集合。对于 set 容器，由于其内部元素是有序的，我们可以利用这一特性高效地计算交集。

我们可以使用两个迭代器分别遍历两个 set。当两个迭代器指向的元素相等时，这个元素就是交集中的元素，将其加入结果集中。如果第一个 set 中的元素小于第二个 set 中的元素，那么第一个 set 的迭代器向前移动；反之，如果第一个 set 中的元素大于第二个 set 中的元素，第二个 set 的迭代器向前移动。

代码实现

#include <iostream>
#include <set>
#include <algorithm>

std::set<int> intersection(const std::set<int>& set1, const std::set<int>& set2) {
    std::set<int> result;
    auto it1 = set1.begin();
    auto it2 = set2.begin();

    while (it1 != set1.end() && it2 != set2.end()) {
        if (*it1 < *it2) {
            ++it1;
        } else if (*it1 > *it2) {
            ++it2;
        } else {
            result.insert(*it1);
            ++it1;
            ++it2;
        }
    }
    return result;
}

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};

    std::set<int> result = intersection(set1, set2);

    std::cout << "交集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，我们定义了一个 intersection 函数，它接受两个 set 作为参数，并返回它们的交集。在函数内部，我们使用两个迭代器 it1 和 it2 分别遍历 set1 和 set2。通过比较迭代器指向的元素，我们决定是移动 it1、it2 还是将元素插入到结果 set 中。

复杂度分析

这种实现方式的时间复杂度为 $O(m + n)$，其中 m 和 n 分别是两个 set 的大小。这是因为在最坏情况下，我们需要遍历完两个 set 中的所有元素。空间复杂度为 $O(\min(m, n))$，因为结果集的大小最大不会超过较小的那个 set 的大小。

并集操作

原理

两个 set 的并集是指包含这两个 set 中所有不同元素的集合。同样，利用 set 元素有序的特性，我们可以高效地计算并集。

我们使用两个迭代器分别遍历两个 set。比较两个迭代器指向的元素，将较小的元素加入结果集，并移动指向较小元素的迭代器。如果两个元素相等，将其中一个加入结果集，并同时移动两个迭代器。当其中一个 set 遍历完后，将另一个 set 中剩余的元素全部加入结果集。

代码实现

#include <iostream>
#include <set>
#include <algorithm>

std::set<int> unionSet(const std::set<int>& set1, const std::set<int>& set2) {
    std::set<int> result;
    auto it1 = set1.begin();
    auto it2 = set2.begin();

    while (it1 != set1.end() && it2 != set2.end()) {
        if (*it1 < *it2) {
            result.insert(*it1);
            ++it1;
        } else if (*it1 > *it2) {
            result.insert(*it2);
            ++it2;
        } else {
            result.insert(*it1);
            ++it1;
            ++it2;
        }
    }

    while (it1 != set1.end()) {
        result.insert(*it1);
        ++it1;
    }

    while (it2 != set2.end()) {
        result.insert(*it2);
        ++it2;
    }

    return result;
}

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};

    std::set<int> result = unionSet(set1, set2);

    std::cout << "并集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，unionSet 函数计算并返回两个 set 的并集。首先，在 while 循环中，我们处理两个 set 都未遍历完的情况。之后，通过两个单独的 while 循环，将剩余未遍历完的 set 中的元素加入结果集。

复杂度分析

这种实现方式的时间复杂度也是 $O(m + n)$，其中 m 和 n 分别是两个 set 的大小。因为在最坏情况下，我们需要遍历完两个 set 中的所有元素。空间复杂度为 $O(m + n)$，因为结果集的大小最大为两个 set 大小之和。

使用 STL 算法进行交集和并集操作

使用 std::set_intersection

std::set_intersection 是 C++ STL 提供的一个算法，用于计算两个有序范围的交集。它的原型如下：

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2,
                          OutputIt d_first);

first1 和 last1 定义了第一个有序范围，first2 和 last2 定义了第二个有序范围，d_first 是存放交集结果的起始位置。

示例代码如下：

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

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_intersection(set1.begin(), set1.end(),
                          set2.begin(), set2.end(),
                          std::back_inserter(result));

    std::cout << "交集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们使用 std::set_intersection 来计算 set1 和 set2 的交集，并将结果存储在一个 std::vector 中。std::back_inserter 是一个插入迭代器，它会在 result 向量的末尾插入元素。

使用 std::set_union

std::set_union 用于计算两个有序范围的并集，其原型为：

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   OutputIt d_first);

同样，first1、last1、first2、last2 定义了两个有序范围，d_first 是存放并集结果的起始位置。

示例代码如下：

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

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};
    std::vector<int> result;

    std::set_union(set1.begin(), set1.end(),
                   set2.begin(), set2.end(),
                   std::back_inserter(result));

    std::cout << "并集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，std::set_union 计算了 set1 和 set2 的并集，并将结果存储在 result 向量中。

复杂度分析

std::set_intersection 和 std::set_union 的时间复杂度都为 $O(m + n)$，其中 m 和 n 分别是两个输入范围的大小。空间复杂度取决于输出范围，在上述示例中，由于我们使用 std::back_inserter，空间复杂度为 $O(m + n)$，因为结果向量的大小最大为两个 set 大小之和。

自定义比较函数的情况

交集操作

有时候，我们可能需要使用自定义的比较函数来创建 set。例如，我们想要创建一个按降序排列的 set。在计算交集时，同样需要考虑这个自定义的比较函数。

#include <iostream>
#include <set>
#include <algorithm>

struct CompareDescending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

std::set<int, CompareDescending> intersection(const std::set<int, CompareDescending>& set1,
                                             const std::set<int, CompareDescending>& set2) {
    std::set<int, CompareDescending> result;
    auto it1 = set1.begin();
    auto it2 = set2.begin();

    while (it1 != set1.end() && it2 != set2.end()) {
        if (CompareDescending()(*it1, *it2)) {
            ++it1;
        } else if (CompareDescending()(*it2, *it1)) {
            ++it2;
        } else {
            result.insert(*it1);
            ++it1;
            ++it2;
        }
    }
    return result;
}

int main() {
    std::set<int, CompareDescending> set1 = {5, 4, 3, 2, 1};
    std::set<int, CompareDescending> set2 = {7, 6, 5, 4, 3};

    std::set<int, CompareDescending> result = intersection(set1, set2);

    std::cout << "交集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，我们定义了一个 CompareDescending 结构体作为自定义比较函数，它使得 set 按降序排列。在 intersection 函数中，我们使用这个自定义比较函数来计算交集。

并集操作

对于并集操作，同样需要考虑自定义比较函数。

#include <iostream>
#include <set>
#include <algorithm>

struct CompareDescending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

std::set<int, CompareDescending> unionSet(const std::set<int, CompareDescending>& set1,
                                          const std::set<int, CompareDescending>& set2) {
    std::set<int, CompareDescending> result;
    auto it1 = set1.begin();
    auto it2 = set2.begin();

    while (it1 != set1.end() && it2 != set2.end()) {
        if (CompareDescending()(*it1, *it2)) {
            result.insert(*it1);
            ++it1;
        } else if (CompareDescending()(*it2, *it1)) {
            result.insert(*it2);
            ++it2;
        } else {
            result.insert(*it1);
            ++it1;
            ++it2;
        }
    }

    while (it1 != set1.end()) {
        result.insert(*it1);
        ++it1;
    }

    while (it2 != set2.end()) {
        result.insert(*it2);
        ++it2;
    }

    return result;
}

int main() {
    std::set<int, CompareDescending> set1 = {5, 4, 3, 2, 1};
    std::set<int, CompareDescending> set2 = {7, 6, 5, 4, 3};

    std::set<int, CompareDescending> result = unionSet(set1, set2);

    std::cout << "并集为: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个代码示例中，unionSet 函数使用自定义的 CompareDescending 比较函数来计算两个降序排列的 set 的并集。

与其他容器的结合使用

与 vector 结合

有时候，我们可能从一个 vector 中获取数据，并将其插入到 set 中，然后进行交集或并集操作。例如：

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

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {3, 4, 5, 6, 7};

    std::set<int> set1(vec1.begin(), vec1.end());
    std::set<int> set2(vec2.begin(), vec2.end());

    std::set<int> intersectionResult;
    std::set_intersection(set1.begin(), set1.end(),
                          set2.begin(), set2.end(),
                          std::inserter(intersectionResult, intersectionResult.begin()));

    std::cout << "交集为: ";
    for (int num : intersectionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::set<int> unionResult;
    std::set_union(set1.begin(), set1.end(),
                   set2.begin(), set2.end(),
                   std::inserter(unionResult, unionResult.begin()));

    std::cout << "并集为: ";
    for (int num : unionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们首先将 vector 中的元素插入到 set 中，然后使用 std::set_intersection 和 std::set_union 来计算交集和并集。

与 map 结合

虽然 map 是一种键值对的关联容器，但我们可以提取其键（key）并将其放入 set 中进行交集和并集操作。例如：

#include <iostream>
#include <set>
#include <map>
#include <algorithm>

int main() {
    std::map<int, std::string> map1 = {{1, "one"}, {2, "two"}, {3, "three"}};
    std::map<int, std::string> map2 = {{3, "three"}, {4, "four"}, {5, "five"}};

    std::set<int> set1;
    for (const auto& pair : map1) {
        set1.insert(pair.first);
    }

    std::set<int> set2;
    for (const auto& pair : map2) {
        set2.insert(pair.first);
    }

    std::set<int> intersectionResult;
    std::set_intersection(set1.begin(), set1.end(),
                          set2.begin(), set2.end(),
                          std::inserter(intersectionResult, intersectionResult.begin()));

    std::cout << "交集的键为: ";
    for (int num : intersectionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::set<int> unionResult;
    std::set_union(set1.begin(), set1.end(),
                   set2.begin(), set2.end(),
                   std::inserter(unionResult, unionResult.begin()));

    std::cout << "并集的键为: ";
    for (int num : unionResult) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们从两个 map 中提取键并放入 set 中，然后计算这些键的交集和并集。

实际应用场景

数据去重与筛选

在数据处理中，经常需要对数据进行去重。例如，从多个数据源获取到一些数据，这些数据可能有重复。我们可以将数据放入 set 中，然后利用 set 的唯一性自动去重。之后，如果我们想要获取两个数据源中共同的数据，就可以使用交集操作；如果想要获取所有数据，就可以使用并集操作。

集合运算在图算法中的应用

在图算法中，例如求两个节点集合的公共邻居节点（交集操作），或者求所有邻居节点（并集操作）。假设图是用邻接表表示，每个节点的邻居节点可以存储在 set 中，通过对这些 set 进行交集和并集操作，可以方便地实现相关算法。

文本处理

在文本处理中，我们可能需要统计不同文本文件中出现的共同单词（交集），或者所有出现过的单词（并集）。可以将每个文件中的单词放入一个 set 中，然后进行相应的集合运算。

通过深入理解 set 容器的交集和并集操作，我们能够更加灵活高效地处理各种数据集合相关的问题，无论是在日常编程还是复杂的算法实现中。