Move Fast

집합 연산 (Set Operations on sorted range)

• 정렬된 상태에서 동작.

• 수학의 집합(set) 연산을 제공.

• includes 정렬된 원소들이 다른 정렬된 원소들을 포함하면 true, 그렇지 않으면 false를 반환.

  • set<자료형>을 사용할 경우 자동으로 정렬해주기 때문에 집합 연산을 하는데 용이함.

  • 아래의 코드에서 set이 아닌 vector로 사용할 경우 원소의 순서 및 개수가 유지되기 때문에 false가 3개가 나옴.

// until C++20
template< class InputIt1, class InputIt2 >
bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

template< class InputIt1, class InputIt2, class Compare >
bool includes( InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2, Compare comp );

// since C++20
template< class InputIt1, class InputIt2 >
constexpr bool includes( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2 );

template< class InputIt1, class InputIt2, class Compare >
constexpr bool includes( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
               ForwardIt2 first2, ForwardIt2 last2 );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare >
bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
               ForwardIt2 first2, ForwardIt2 last2, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

template<class Os, class Co> Os& operator<<(Os& os, const Co& v) {
    for (auto i : v) os << i << ' ';
    return os << '\t';
}

int main() {
    const set<char>
        v1 = {'a', 'b', 'c', 'f', 'h', 'x'},
        v2 = {'a', 'b', 'c'},
        v3 = {'a', 'c'},
        v4 = {'a', 'a', 'b'},
        v5 = {'g'},
        v6 = {'a', 'c', 'g'},
        v7 = {'A', 'B', 'C'};

    auto no_case = [](char a, char b) { return tolower(a) < tolower(b); };

    cout
        << v1 << "\nincludes:\n" << boolalpha
        << v2 << ": " << includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << endl
        << v3 << ": " << includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << endl
        << v4 << ": " << includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << endl
        << v5 << ": " << includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << endl
        << v6 << ": " << includes(v1.begin(), v1.end(), v6.begin(), v6.end()) << endl
        << v7 << ": " << includes(v1.begin(), v1.end(), v7.begin(), v7.end(), no_case)
                    << " (case-insensitive)" << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
a b c f h x
includes:
a b c 	: true
a c 	: true
a b 	: true
g 	: false
a c g 	: false
A B C 	: true (case-insensitive)
 */

• set_difference 컨테이너 두 개의 차집합을 구함.

// until C++20
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first );

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

// since C++20
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                                   InputIt2 first2, InputIt2 last2,
                                   OutputIt d_first );

template< class InputIt1, class InputIt2,
          class OutputIt, class Compare >
constexpr OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                                   InputIt2 first2, InputIt2 last2,
                                   OutputIt d_first, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_difference( ExecutionPolicy&& policy,
                           ForwardIt1 first1, ForwardIt1 last1,
                           ForwardIt2 first2, ForwardIt2 last2,
                           ForwardIt3 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_difference( ExecutionPolicy&& policy,
                           ForwardIt1 first1, ForwardIt1 last1,
                           ForwardIt2 first2, ForwardIt2 last2,
                           ForwardIt3 d_first, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

auto print = [](const auto& v, const char* end = "") {
    cout << "{ ";
    for (auto i : v) cout << i << ' ';
    cout << "} " << end;
};

struct Order // a struct with some interesting data
{
    int order_id;
};

ostream& operator<<(ostream& os, const Order& ord) {
    return os << ord.order_id << ',';
}

int main() {
    const vector<int> v1 {1, 2, 5, 5, 5, 9};
    const vector<int> v2 {2, 5, 7};
    vector<int> diff;

    set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(),
                   inserter(diff, diff.begin()));
    print(v1, "ㅡ ");
    print(v2, "= ");
    print(diff, "\n");

    // we want to know which orders "cut" between old and new states:
    vector<Order> old_orders { {1}, {2}, {5}, {9} };
    vector<Order> new_orders { {2}, {5}, {7} };
    vector<Order> cut_orders;

    set_difference(old_orders.begin(), old_orders.end(),
                   new_orders.begin(), new_orders.end(),
                   back_inserter(cut_orders),
                   [](auto& a, auto& b) { return a.order_id < b.order_id; });

    cout << "old orders = "; print(old_orders, "\n");
    cout << "new orders = "; print(new_orders, "\n");
    cout << "cut orders = "; print(cut_orders, "\n");

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
{ 1 2 5 5 5 9 } ㅡ { 2 5 7 } = { 1 5 5 9 }
old orders = { 1, 2, 5, 9, }
new orders = { 2, 5, 7, }
cut orders = { 1, 9, }
 */

• set_interaction 컨테이너 두 개의 교집합을 구함.

// until C++20
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, InputIt2 last2,
                           OutputIt d_first );

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

// since C++20
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_intersection( InputIt1 first1, InputIt1 last1,
                                     InputIt2 first2, InputIt2 last2,
                                     OutputIt d_first );

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

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_intersection( ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,
                             ForwardIt3 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_intersection( ExecutionPolicy&& policy,
                             ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,
                             ForwardIt3 d_first, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> v1{1,2,3,4,5,6,7,8};
    vector<int> v2{        5,  7,   9,10};
    vector<int> v_intersection;

    set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                     back_inserter(v_intersection));

    for(int n : v_intersection)
        cout << n << ' ';
    cout << endl;

    set<char> s1{'a', 'b', 'c', 'd', 'e', 'f'};
    set<char> s2{     'b',      'd', 'e',       'g', 'h', 'i'};
    set<char> s_intersection;

    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
                     inserter(s_intersection, s_intersection.begin()));

    for(char ch : s_intersection)
        cout << ch << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
5 7
b d e
 */

• set_symmetric_difference 컨테이너 두 개의 차이를 구함. (A - B 와 B - A 의 합집합 = A와 B의 합집합 - 교집합)

// until C++20
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1,
                                   InputIt2 first2, InputIt2 last2,
                                   OutputIt d_first );

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

// since C++20
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1,
                                             InputIt2 first2, InputIt2 last2,
                                             OutputIt d_first );

template< class InputIt1, class InputIt2, class OutputIt, class Compare >
constexpr OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1,
                                             InputIt2 first2, InputIt2 last2,
                                             OutputIt d_first, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_symmetric_difference( ExecutionPolicy&& policy,
                                     ForwardIt1 first1, ForwardIt1 last1,
                                     ForwardIt2 first2, ForwardIt2 last2,
                                     ForwardIt3 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_symmetric_difference( ExecutionPolicy&& policy,
                                     ForwardIt1 first1, ForwardIt1 last1,
                                     ForwardIt2 first2, ForwardIt2 last2,
                                     ForwardIt3 d_first, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

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

    vector<int> v_symDifference;

    set_symmetric_difference(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        back_inserter(v_symDifference));

    for(int n : v_symDifference)
        cout << n << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1 2 3 4 6 8 9 10
 */

• set_union 컨테이너 두개의 합집합을 구함.

  • set<자료형> 외에 다른 컨테이너를 사용하면 중복된 원소들까지 합쳐서 구함.

// until C++20
template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_union( InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2,
                    OutputIt d_first );

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

// since C++20
template< class InputIt1, class InputIt2, class OutputIt >
constexpr OutputIt set_union( InputIt1 first1, InputIt1 last1,
                              InputIt2 first2, InputIt2 last2, OutputIt d_first );

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

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_union( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class Compare >
ForwardIt3 set_union( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt2 last2,
                      ForwardIt3 d_first, Compare comp );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    {
        vector<int> v1 = {1, 2, 3, 4, 5};
        vector<int> v2 = {      3, 4, 5, 6, 7};
        vector<int> dest1;

        set_union(v1.begin(), v1.end(),
                  v2.begin(), v2.end(),
                  back_inserter(dest1));

        for (const auto &i : dest1)
            cout << i << ' ';
        cout << endl;
    }
    {
        vector<int> v1 = {1, 2, 3, 4, 5, 5, 5};
        vector<int> v2 = {      3, 4, 5, 6, 7};
        vector<int> dest1;

        set_union(v1.begin(), v1.end(),
                  v2.begin(), v2.end(),
                  back_inserter(dest1));

        for (const auto &i : dest1)
            cout << i << ' ';
        cout << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1 2 3 4 5 6 7
1 2 3 4 5 5 5 6 7
 */