迹忆客 专注技术分享

本文将为大家讲解几种在 C++ 中如何寻找集合交集的方法。

使用 std::set_intersection 方法在 C++ 中寻找集合交集

std::set_intersection 方法是 C++ 算法库的一部分，它包含在 <algorithm> 头中。set_intersection 算法操作并不局限于 std::set 对象，而是可以处理任何基于范围的对象，例如 std::vector。需要注意的是，两个输入范围在传递给 set_intersection 算法之前必须进行排序。

在下面的例子中，我们声明两个 std::set 变量，并用任意 string 类型的元素初始化它们。set_intersection 函数的前四个参数是对应对象的范围迭代器，第五个参数是存储计算出的交集的范围的开始。在这种情况下，我们声明一个 std::vector 来存放这些元素。

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    set<string> s1 {"array", "vector",
                    "deque", "list",
                    "set", "map",
                    "multimap", "span"};
    set<string> s2(s1);
    s2.insert("stack");
    s2.insert("queue");

    vector<string> s1s2_intsec;

    std::set_intersection(s1.begin(), s1.end(),
                          s2.begin(), s2.end(),
                          std::back_inserter(s1s2_intsec));

    cout << "s1 ∩ s2: ";
    printVectorElements(s1s2_intsec);

    exit(EXIT_SUCCESS);
}

输出：

s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )

尽管 std::set_intersection 存储了用户指定的交集元素，但它不能是与输入范围重叠的范围。另一个需要注意的重要点是指定目标范围，它有足够的空间来存储交叉元素。灵活的方法是使用动态数组 std::vector，并使用 std::back_inserter 方法将元素推送到对象中。如果你指定 vector.begin() 迭代器时没有预留内存作为目的参数，算法可能会抛出一个分段故障。下一个例子演示了 vector 对象上的 set_intersection 方法。

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1v2_intsec;
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_intsec));
    cout << "v1 ∩ v2: ";
    printVectorElements(v1v2_intsec);

    exit(EXIT_SUCCESS);
}

输出：

v1 ∩ v2: ( 1, 2, 7 )

使用 std::set_symmetric_difference 方法在 C++ 中查找集合对称差异

另一个来自 C++ 标准库的算法是 std::set_symmetric_difference，它搜索只在其中一个输入范围内找到的元素。函数参数与 std::set_intersection 方法类似。两种算法都采取排序的范围，并将找到的元素也以排序的方式存储。注意，std::set 容器默认包含排序元素。因此，它可以直接作为输入范围传递。而 std::vector 内容在被 std::set_symmetric_difference 处理之前必须明确地进行排序。

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

using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;

template<typename T>
void printVectorElements(vector<T> &vec)
{
    cout << "{ ";
    for (const auto &item : vec) {
        cout << item << ", ";
    }
    cout << "\b\b }" << endl;
}

int main() {
    vector<int> v1 {9,7,5,1,2};
    vector<int> v2 {4,3,2,1,7,8};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    vector<int> v1v2_symdif;
    std::set_symmetric_difference(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v1v2_symdif));
    cout << "v1 △ v2: ";
    printVectorElements(v1v2_symdif);

    exit(EXIT_SUCCESS);
}

输出：

v1 △ v2: ( 3, 4, 5, 8, 9 )