Move Fast

최대, 최소 원소 탐색 알고리즘 (Maximum, Minimum Algorithm)

• max 최대 원소 반환.

  • max_element 최대 원소의 iterator를 반환.

// until C++14
template< class T > 
const T& max( const T& a, const T& b );

template< class T, class Compare >
const T& max( const T& a, const T& b, Compare comp );

// since C++14
template< class T > 
constexpr const T& max( const T& a, const T& b );

template< class T, class Compare >
constexpr const T& max( const T& a, const T& b, Compare comp );

template< class T >
constexpr T max( std::initializer_list<T> ilist );

template< class T, class Compare >
constexpr T max( std::initializer_list<T> ilist, Compare comp );

// since C++11 until C++14
template< class T >
T max( std::initializer_list<T> ilist );

template< class T, class Compare >
T max( std::initializer_list<T> ilist, Compare comp );

// until C++17
template< class ForwardIt > 
ForwardIt max_element( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt max_element( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ForwardIt > 
constexpr ForwardIt max_element( ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt > 
ForwardIt max_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
constexpr ForwardIt max_element( ForwardIt first, ForwardIt last, Compare comp );

template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt max_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                       Compare comp );

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

static bool abs_compare(int a, int b) {
    return (abs(a) < abs(b));
}

int main() {
    cout << "larger of 1 and 9999 is " << max(1, 9999) << endl
         << "larger of 'a', and 'b' is '" << max('a', 'b') << "'" << endl
         << "longest of \"foo\", \"bar\", and \"hello\" is \""
         << max({ "foo", "bar", "hello" },
                [](const string_view s1, const string_view s2) {
                    return s1.size() < s2.size();
                }) << "\"" << endl;

    vector<int> v{ 3, 1, -14, 1, 5, 9 };
    vector<int>::iterator it = max_element(v.begin(), v.end());
    cout << "max element is " << *it << " at " << distance(v.begin(), it) << endl;

    it = max_element(v.begin(), v.end(), abs_compare);
    cout << "max element (absolute) at " << distance(v.begin(), it) << endl;
    cout << "max element (absolute) is " << *it << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
larger of 1 and 9999 is 9999
larger of 'a', and 'b' is 'b'
longest of "foo", "bar", and "hello" is "hello"
max element is 9 at 5
max element (absolute) at 2
max element (absolute) is -14
 */

• min 최소 원소 반환.

  • min_element 최소 원소의 iterator를 반환.

// until C++14
template< class T > 
const T& min( const T& a, const T& b );

template< class T, class Compare >
const T& min( const T& a, const T& b, Compare comp );

// since C++14
template< class T > 
constexpr const T& min( const T& a, const T& b );

template< class T, class Compare >
constexpr const T& min( const T& a, const T& b, Compare comp );

template< class T >
constexpr T min( std::initializer_list<T> ilist );

template< class T, class Compare >
constexpr T min( std::initializer_list<T> ilist, Compare comp );

// since C++11 until C++14
template< class T >
T min( std::initializer_list<T> ilist );

template< class T, class Compare >
T min( std::initializer_list<T> ilist, Compare comp );

// until C++17
template< class ForwardIt > 
ForwardIt min_element( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt min_element( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ForwardIt > 
constexpr ForwardIt min_element( ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt > 
ForwardIt min_element( ExecutionPolicy&& policy,  ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
constexpr ForwardIt min_element( ForwardIt first, ForwardIt last, Compare comp );

template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt min_element( ExecutionPolicy&& policy, 
                       ForwardIt first, ForwardIt last, Compare comp );

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

static bool abs_compare(int a, int b) {
    return (abs(a) < abs(b));
}

int main() {
    cout << "larger of 1 and 9999 is " << min(1, 9999) << endl
         << "larger of 'a', and 'b' is '" << min('a', 'b') << "'" << endl
         << "longest of \"foo\", \"bar\", and \"hello\" is \""
         << min({ "foo", "bar", "hello" },
                [](const string_view s1, const string_view s2) {
                    return s1.size() < s2.size();
                }) << "\"" << endl;

    vector<int> v{ 3, 1, -14, 1, 5, 9 };
    vector<int>::iterator it = min_element(v.begin(), v.end());
    cout << "min element is " << *it << " at " << distance(v.begin(), it) << endl;

    it = min_element(v.begin(), v.end(), abs_compare);
    cout << "min element (absolute) at " << distance(v.begin(), it) << endl;
    cout << "min element (absolute) is " << *it << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
larger of 1 and 9999 is 1
larger of 'a', and 'b' is 'a'
longest of "foo", "bar", and "hello" is "foo"
min element is -14 at 2
min element (absolute) at 1
min element (absolute) is 1
 */

• minmax 주어진 두 값 중 최대, 최소 원소 둘 다 반환. (반환형: pair<자료형, 자료형>)

  • minmax_element 범위 내 최대, 최소 원소의 iterator를 반환. (반환형: pair<반복자, 반복자>)

// since C++11 until C++14
template< class T > 
std::pair<const T&,const T&> minmax( const T& a, const T& b );

template< class T, class Compare >
std::pair<const T&,const T&> minmax( const T& a, const T& b, Compare comp );

template< class T >
std::pair<T,T> minmax( std::initializer_list<T> ilist);

template< class T, class Compare >
std::pair<T,T> minmax( std::initializer_list<T> ilist, Compare comp );

// since C++14
template< class T > 
constexpr std::pair<const T&,const T&> minmax( const T& a, const T& b );

template< class T, class Compare >
constexpr std::pair<const T&,const T&> minmax( const T& a, const T& b, Compare comp );

template< class T >
constexpr std::pair<T,T> minmax( std::initializer_list<T> ilist);

template< class T, class Compare >
constexpr std::pair<T,T> minmax( std::initializer_list<T> ilist, Compare comp );

// since C++11 until C++17
template< class ForwardIt > 
std::pair<ForwardIt,ForwardIt>  minmax_element( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
std::pair<ForwardIt,ForwardIt> 
    minmax_element( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ForwardIt > 
constexpr std::pair<ForwardIt,ForwardIt> 
    minmax_element( ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt > 
std::pair<ForwardIt,ForwardIt> 
    minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
constexpr std::pair<ForwardIt,ForwardIt> 
    minmax_element( ForwardIt first, ForwardIt last, Compare comp );

template< class ExecutionPolicy, class ForwardIt, class Compare >
std::pair<ForwardIt,ForwardIt> 
    minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                    Compare comp );

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

int main() {
    pair<int, int> p = minmax(3, 10);
    cout << "min = " << p.first << ", max = " << p.second << endl;
    
    const vector<int> v{ 3, 9, 1, 4, 2, 5, 9 };
    const auto [min, max] = minmax_element(v.begin(), v.end());
    cout << "min = " << *min << ", max = " << *max << endl;
    
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
min = 3, max = 10
min = 1, max = 9
 */

• clamp 주어진 원소가 주어진 범위를 벗어나면 하한 또는 상한을 반환. (C++17부터 지원)

  • 첫번째 인자가 두번째 인자보다 작으면 두번째 인자를 반환하고, 세번째 인자보다 크면 세번째 인자를 반환.

// since C++17
template<class T>
constexpr const T& clamp( const T& v, const T& lo, const T& hi );

template<class T, class Compare>
constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp );

// ----------------------------------------------------------------------------------
#include <cstdint>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <random>
using namespace std;

int main() {
    mt19937 g(random_device{}());
    uniform_int_distribution<> d(-300, 300);

    cout << " raw   clamped to int8_t   clamped to uint8_t" << endl;
    for(int n = 0; n < 5; ++n) {
        int v = d(g);
        cout << setw(4) << v
             << setw(20) << clamp(v, INT8_MIN, INT8_MAX)
             << setw(21) << clamp(v, 0, UINT8_MAX) << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
 raw   clamped to int8_t   clamped to uint8_t
 173                 127                  173
 248                 127                  248
  61                  61                   61
 250                 127                  250
  30                  30                   30

./a.out
 raw   clamped to int8_t   clamped to uint8_t
-148                -128                    0
-155                -128                    0
  38                  38                   38
-205                -128                    0
  27                  27                   27
  
$ ./a.out
 raw   clamped to int8_t   clamped to uint8_t
  26                  26                   26
 102                 102                  102
 236                 127                  236
 -22                 -22                    0
 -39                 -39                    0
 */

힙 알고리즘 (Heap Algorithm)

• Heap (위키백과)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

• make_heap 범위 내 원소들을 힙 속성을 만족하도록 만듬.

  • push_heap 힙에 원소를 삽입. (컨테이너가 힙 속성을 만족한다고 가정함.)

  • pop_heap 힙에 원소를 제거. (컨테이너가 힙 속성을 만족한다고 가정함.)

// until C++20
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr void make_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void make_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr void push_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void push_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr void pop_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );

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

void print(string msg, vector<int> &v) {
    cout << msg;
    for (auto i : v) cout << i << ' ';
    cout << endl;
}

int main() {
    cout << "Max heap:" << endl;
    vector<int> v { 3, 2, 4, 1, 5, 9 };
    print("initially, v: ", v);

    make_heap(v.begin(), v.end());
    print("after make_heap, v: ", v);

    v.push_back(6);
    print("before push_heap, v: ", v);

    push_heap(v.begin(), v.end());
    print("after push_heap, v: ", v);

    pop_heap(v.begin(), v.end());
    print("after pop_heap, v: ", v);

    auto top = v.back();
    v.pop_back();
    cout << "former top element: " << top << endl;
    print("after removing the former top element, v: ", v);

    cout << endl << "Min heap:" << endl;
    vector<int> v1 { 3, 2, 4, 1, 5, 9 };
    print("initially, v1: ", v1);

    make_heap(v1.begin(), v1.end(), greater<>{});
    print("after make_heap, v1: ", v1);

    v.push_back(6);
    print("before push_heap, v: ", v);

    push_heap(v.begin(), v.end());
    print("after push_heap, v: ", v);

    pop_heap(v1.begin(), v1.end(), greater<>{});
    print("after pop_heap, v1: ", v1);

    auto top1 = v1.back();
    v1.pop_back();
    cout << "former top element: " << top1 << endl;
    print("after removing the former top element, v1: ", v1);

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
before push_heap, v: 9 5 4 1 2 3 6
after push_heap, v: 9 5 6 1 2 3 4
after pop_heap, v: 6 5 4 1 2 3 9
former top element: 9
after removing the former top element, v: 6 5 4 1 2 3

Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
before push_heap, v: 6 5 4 1 2 3 6
after push_heap, v: 6 5 6 1 2 3 4
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5
 */

• sort_heap 힙의 원소들을 정렬.

  • 시간 복잡도: O( 2 * N * log(N) ), 범위의 크기 = N

// until C++20
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr void sort_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr void sort_heap( RandomIt first, RandomIt last, Compare comp );

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

int main() {
    vector<int> v{3, 1, 4, 1, 5, 9};

    make_heap(v.begin(), v.end());

    cout << "heap:\t";
    for (const auto &i : v) cout << i << ' ';
    cout << endl;

    sort_heap(v.begin(), v.end());

    cout << "sorted:\t";
    for (const auto &i : v) cout << i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
heap:	9 5 4 1 1 3
sorted:	1 1 3 4 5 9
 */

• is_heap 힙 속성을 만족하면 true, 그렇지 않으면 false를 반환.

  • is_heap_until 힙 속성을 만족하지 않는 첫번째 원소를 반환.

// since C++11 until C++20
template< class RandomIt >
bool is_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );

// since C++20
template< class RandomIt >
constexpr bool is_heap( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr bool is_heap( RandomIt first, RandomIt last, Compare comp );

template< class RandomIt >
constexpr RandomIt is_heap_until( RandomIt first, RandomIt last );

template< class RandomIt, class Compare >
constexpr RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );

template< class ExecutionPolicy, class RandomIt >
RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

template< class ExecutionPolicy, class RandomIt, class Compare >
RandomIt is_heap_until( ExecutionPolicy&& policy,
                        RandomIt first, RandomIt last, Compare comp );

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

void print(string msg, vector<int> &v) {
    cout << msg;
    for (auto i : v) cout << i << ' ';
    cout << endl;
}

int main() {
    vector<int> v { 3, 1, 4, 1, 5, 9 };
    print("initially, v: ", v);

    if (!is_heap(v.begin(), v.end())) {
        cout << "making heap..." << endl;
        make_heap(v.begin(), v.end());
    }

    print("after make_heap, v: ", v);

    cout << "probably mess up the heap" << endl;
    v.push_back(2);
    v.push_back(6);

    auto heap_end = is_heap_until(v.begin(), v.end());
    print("all of v: ", v);

    cout << "only heap: ";
    for (auto i = v.begin(); i != heap_end; ++i) cout << *i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
initially, v: 3 1 4 1 5 9
making heap...
after make_heap, v: 9 5 4 1 1 3
probably mess up the heap
all of v: 9 5 4 1 1 3 2 6
only heap: 9 5 4 1 1 3 2
 */

집합 연산 (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
 */

병합 알고리즘 (Merging Algorithm)

• 이미 정렬된 상태에서 수행하며, 병합 후에도 정렬된 상태를 유지.

• 비교자 함수를 써서 별도의 비교 연산을 구현 할 수 있음.

• merge 주어진 두 개의 범위를 하나로 합침.

  • 시간 복잡도: O(N1 + N2), 주어진 두 범위의 크기 각각 N1, N2

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

template< class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge( 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 merge( InputIt1 first1, InputIt1 last1,
                          InputIt2 first2, InputIt2 last2, OutputIt d_first );

template< class InputIt1, class InputIt2, class OutputIt, class Compare>
constexpr OutputIt merge( 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 merge( 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 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                  ForwardIt2 first2, ForwardIt2 last2,
                  ForwardIt3 d_first, Compare comp );

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

int main() {
    // fill the vectors with random numbers
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<> dis(0, 9);

    vector<int> v1(10), v2(10);
    generate(v1.begin(), v1.end(), bind(dis, ref(mt)));
    generate(v2.begin(), v2.end(), bind(dis, ref(mt)));

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

    // output v1
    cout << "v1 : ";
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // output v2
    cout << "v2 : ";
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // merge
    cout << "After merging" << endl;
    vector<int> dst;
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dst));

    // output
    cout << "dst: ";
    copy(dst.begin(), dst.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
v1 : 0 1 1 1 3 4 7 7 7 8
v2 : 0 1 2 2 3 4 5 5 8 9
After merging
dst: 0 0 1 1 1 1 2 2 3 3 4 4 5 5 7 7 7 8 8 9
$ ./a.out
v1 : 0 0 2 4 5 6 7 9 9 9
v2 : 0 2 4 4 4 5 5 6 7 7
After merging
dst: 0 0 0 2 2 4 4 4 4 5 5 5 6 6 7 7 7 9 9 9
 */

• inplace_merge 메모리를 추가로 사용하지 않고 주어진 두 범위를 하나로 합침.

  • 시간 복잡도: O(N * log(N)), 합쳐진 범위의 크기 = N

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare>
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt, class Compare>
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last, Compare comp );

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

template<class Iter>
void merge_sort(Iter first, Iter last) {
    if (last - first > 1) {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        inplace_merge(first, middle, last);
    }
}

int main() {
    vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for(auto n : v) cout << n << ' ';
    cout << endl;

    vector<int> v2{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    inplace_merge(v2.begin(), v2.begin() + (v2.end() - v2.begin()) / 2, v2.end());
    for(auto n : v2) cout << n << ' ';
    cout << endl;
    return 0;
}

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