剑指信奥｜C++ 之 STL 算法 - 集合运算

集合运算

在 C++ STL 中有一类算法称为集合操作，是指对已排序序列进行的集合代数运算。

集合代数发展并描述了集合的基本性质和规律，集合论运算，如并集、交集、补集，以及集合的关系，如等于、包含。

这门学科系统研究如何来表达和进行上述的运算和关系的操作。

Wikipedia

STL 中有着关于序列的交集，并集，差集，对称差集以及包含关系，以下我们逐一讲解这几种函数。

set_intersection

交集运算 set_intersection() 函数是求得由两个已排序序列在指定范围内都存在的元素构成的排序范围。

交集｜Wikipedia

基本的 set_intersection 算法接收 5 个参数：

1. first1
2. last1
3. first2
4. first2
5. d_first

代码示例：

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

using namespace std;

int main() {

    // 初始化 v1, v2, v_intersection
    vector<int> v1 = {3, 5, 7, 9}, v2 = {9, 8, 7, 6}, v_intersection;

    // v1, v2 排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    // 调用 set_intersection
    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_intersection));

    // 输出 v_intersection
    for (auto i = v_intersection.begin(); i < v_intersection.end(); ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    7 9
 */

set_union

函数 set_union 是求得两个序列的并集，参数与交集一致。

并集｜Wikipedia

代码示例：

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

using namespace std;

int main() {

    // 初始化 v1, v2, v_union
    vector<int> v1 = {3, 5, 7, 9}, v2 = {9, 8, 7, 6}, v_union;

    // v1, v2 排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    // 调用 set_union
    set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_union));

    // 输出 v_union
    for (auto i = v_union.begin(); i < v_union.end(); ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    3 5 6 7 8 9 
 */

set_difference

函数 set_difference() 是求得两个序列的差集，参数与上述函数一致。

差集｜Wikipedia

代码示例：

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

using namespace std;

int main() {

    // 初始化 v1, v2, v_difference
    vector<int> v1 = {3, 5, 7, 9}, v2 = {9, 8, 7, 6}, v_difference;

    // v1, v2 排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    // 调用 set_difference
    set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_difference));

    // 输出 v_difference
    for (auto i = v_difference.begin(); i < v_difference.end(); ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    3 5
 */

set_symmetric_difference

函数 set_symmetric_difference() 是求得两个函数的对称差集，这个集合操作的名字不是很好理解，但看图就一目了然了：

对称差集｜Programiz

代码示例：

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

using namespace std;

int main() {

    // 初始化 v1, v2, v_symmetric_difference
    vector<int> v1 = {3, 5, 7, 9}, v2 = {9, 8, 7, 6}, v_symmetric_difference;

    // v1, v2 排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    // 调用 set_symmetric_difference
    set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v_symmetric_difference));

    // 输出 v_symmetric_difference
    for (auto i = v_symmetric_difference.begin(); i < v_symmetric_difference.end(); ++i) {
        cout << *i << " ";
    }

    return 0;
}

/*
 output
    3 5 6 8
 */

includes

函数 includes() 是判读两个集合的包含关系，若集合 1 包含集合 2，则返回 true，否则返回 false。

子集 & 超集｜Wikipedia

基本的 include() 函数接收 4 个参数：

1. first1
2. last1
3. first2
4. last2

代码示例：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cctype>

using namespace std;

int main() {

    // 初始化 v1, v2
    vector<int> v1 = {6, 8}, v2 = {9, 8, 7, 6};

    // v1, v2 排序
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    cout << boolalpha;
    
    // 调用 includes
    cout << "v1 includes v2: " << includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << endl;
    cout << "v2 includes v1: " << includes(v2.begin(), v2.end(), v1.begin(), v1.end()) << endl;

    return 0;
}

/*
 output
    v1 includes v2: false
    v2 includes v1: true
 */

代码分析：

从两个序列的元素不难发现，集合 v2 包含集合 v1，反之是不成立的，输出的结果也验证了这一点。