1.部分集合/有序数组操作

C++的set操作其实只是代表有序集合。

对比操作

• set_difference
• set_intersection
• set_union
• set_symmetric_difference
• include

合并操作

• merge
• implace_merge

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

using namespace std;

int main() {
    // must be sorted
    vector<int> a {1,2,3,4,5,6}, b{4,5,6,7,8}, c;
    // random_shuffle(a.begin(), a.end());
    // random_shuffle(b.begin(), b.end());

    set_difference(a.begin(), a.end(), 
                   b.begin(), b.end(), 
                   back_inserter(c));
    cout << "a:\n";
    for (int i : a) cout << i << " ";
    cout << endl;
    cout << "b:\n";
    for (int i : b) cout << i << " ";
    cout << endl;

    cout << "set_difference:\n";
    for (int i : c) cout << i << " ";
    cout << endl;
    c.clear();

    set_intersection(a.begin(), a.end(), 
                   b.begin(), b.end(), 
                   back_inserter(c));
    cout << "set_intersection:\n";
    for (int i : c) cout << i << " ";
    cout << endl;
    c.clear();

    set_union(  a.begin(), a.end(), 
                b.begin(), b.end(), 
                back_inserter(c));
    cout << "set_union:\n";
    for (int i : c) cout << i << " ";
    cout << endl;
    c.clear();

    set_symmetric_difference(a.begin(), a.end(), 
                   b.begin(), b.end(), 
                   back_inserter(c));
    cout << "set_symmetric_difference:\n";
    for (int i : c) cout << i << " ";
    cout << endl;
    c.clear();

// include   	
    bool AincludesB = std::includes(a.begin(), a.end(), b.begin(), b.end());
    bool Aincludes123 = std::includes(a.begin(), a.end(), a.begin(), a.begin()+3);
    cout << boolalpha << "AincludesB: " << AincludesB << ", Aincludes123: " << Aincludes123 <<"\n";

// Merging 2 sets
    // c.resize(a.size()+b.size());
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    cout << "merge:\n";
    for (int i : c) cout << i << " ";
    cout << endl;
    c.clear();

// 数组俩有序的部分进行merge
    vector<int> d = {1,2,4,5, -2,-1,3,12};
    inplace_merge(d.begin(), d.begin()+4, d.end());
    cout << "inplace_merge:\n";
    for (int i : d) cout << i << " ";
    cout << endl;
    c.clear();
}

a:
1 2 3 4 5 6
b:
4 5 6 7 8
set_difference:
1 2 3
set_intersection:
4 5 6
set_union:
1 2 3 4 5 6 7 8
set_symmetric_difference:
1 2 3 7 8
AincludesB: false, Aincludes123: true
merge:
1 2 3 4 4 5 5 6 6 7 8
inplace_merge:
-2 -1 1 2 3 4 5 12

ref:
https://www.fluentcpp.com/2017/01/09/know-your-algorithms-algos-on-sets/

2.更复杂的集合操作

ref:
https://www.fluentcpp.com/2017/02/09/set-aggregate-set-seggregate-higher-level-algorithms-on-sets/