Move Fast

이진 탐색 알고리즘 (Binary Search Algorithm)

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

• 이미 정렬된 상태에서 수행해야 하며, 비교자 함수를 별도로 지정할 수 있음.

• lower_bound 특정 값보다 크거나 같은 원소들 중 가장 작은 값(하한)의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last,
                                 const T& value, Compare comp );

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

struct PriceInfo { double price; };

int main() {
    const vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 8; ++i) {
        // Search for first element x such that i ≤ x
        auto lower = lower_bound(data.begin(), data.end(), i);

        cout << i << " ≤ ";
        lower != data.end()
            ? cout << *lower << " at index " << distance(data.begin(), lower)
            : cout << "[not found]";
        cout << endl;
    }

    vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {102.5}, {107.3} };
    for(double to_find: {102.5, 110.2}) {
        auto prc_info = lower_bound(prices.begin(), prices.end(), to_find,
                                    [](const PriceInfo& info, double value){
                                        return info.price < value;
                                    });
        prc_info != prices.end()
            ? cout << prc_info->price << " at index " << prc_info - prices.begin()
            : cout << to_find << " not found";
        cout << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
0 ≤ 1 at index 0
1 ≤ 1 at index 0
2 ≤ 2 at index 1
3 ≤ 4 at index 2
4 ≤ 4 at index 2
5 ≤ 5 at index 3
6 ≤ 6 at index 5
7 ≤ [not found]
102.5 at index 2
110.2 not found
 */

• upper_bound 특정 값보다 큰 원소들 중 가장 작은 값(상한)의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value,
                       Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value,
                                 Compare comp );

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

struct PriceInfo { double price; };

int main() {
    const vector<int> data = { 1, 2, 4, 5, 5, 6 };
    for (int i = 0; i < 7; ++i) {
        // Search first element that is greater than i
        auto upper = upper_bound(data.begin(), data.end(), i);

        cout << i << " < ";
        upper != data.end()
            ? cout << *upper << " at index " << distance(data.begin(), upper)
            : cout << "not found";
        cout << endl;
    }

    vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {107.3}, {109.8} };
    for(double to_find: {102.5, 110.2}) {
        auto prc_info = upper_bound(prices.begin(), prices.end(), to_find,
                                    [](double value, const PriceInfo& info){
                                        return value < info.price;
                                    });
        prc_info != prices.end()
            ? cout << prc_info->price << " at index " << prc_info - prices.begin()
            : cout << to_find << " not found";
        cout << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
0 < 1 at index 0
1 < 2 at index 1
2 < 4 at index 2
3 < 4 at index 2
4 < 5 at index 3
5 < 6 at index 5
6 < not found
107.3 at index 3
110.2 not found
 */

• binary_search 범위 내 특정 값과 일치하는 원소의 iterator를 반환.

// until C++20
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value,
                              Compare comp );

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

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

    for (auto needle : needles) {
        cout << "Searching for " << needle << endl;
        if (binary_search(haystack.begin(), haystack.end(), needle)) {
            cout << "Found " << needle << endl;
        } else {
            cout << "no dice!" << endl;
        }
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3
 */

• equal_range 범위 내 특정 값과 일치하는 원소들의 부분 범위([lower_bound, upper_bound)) 반환.

// until C++20
template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last,
                                            const T& value );

template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt,ForwardIt> 
    equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );

// since C++20
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt,ForwardIt> 
              equal_range( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt,ForwardIt> 
              equal_range( ForwardIt first, ForwardIt last,
                           const T& value, Compare comp );

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

struct S {
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator< ( const S& s ) const { return number < s.number; }
};

int main() {
    // note: not ordered, only partitioned w.r.t. S defined below
    vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };

    S value = {2, '?'};

    auto p = equal_range(vec.begin(), vec.end(), value);
    for ( auto i = p.first; i != p.second; ++i )
        cout << i->name << ' ';
    cout << endl;

    // heterogeneous comparison:
    struct Comp {
        bool operator() ( const S& s, int i ) const { return s.number < i; }
        bool operator() ( int i, const S& s ) const { return i < s.number; }
    };

    auto p2 = equal_range(vec.begin(),vec.end(), 2, Comp{});
    for ( auto i = p2.first; i != p2.second; ++i )
        cout << i->name << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
B C D
B C D
 */

정렬 알고리즘 (Sorting Algorithm)

• sort 범위 내 원소들을 정렬.

  • 3번째 인자로 비교자 함수를 넘겨서 비교 순서를 정할 수 있음.

  • 오름차순 정렬이 디폴트

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

#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <functional>
using namespace std;

void print(string msg, array<int, 10> &arr) {
    cout << msg;
    for (auto a : arr) cout << a << " ";
    cout << endl;
}

int main() {
    array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

    sort(s.begin(), s.end());
    print("Sort using the default operator<.\n", s);

    sort(s.begin(), s.end(), greater<int>());
    print("Sort using a standard library compare function object.\n", s);

    struct {
        bool operator()(int a, int b) const {
            return a < b;
        }
    } customLess;
    sort(s.begin(), s.end(), customLess);
    print("Sort using a custom function object.\n", s);

    // sort using a lambda expression
    sort(s.begin(), s.end(), [](int a, int b) {
        return a > b;
    });
    print("Sort using a lambda expression.\n", s);

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Sort using the default operator<.
0 1 2 3 4 5 6 7 8 9
Sort using a standard library compare function object.
9 8 7 6 5 4 3 2 1 0
Sort using a custom function object.
0 1 2 3 4 5 6 7 8 9
Sort using a lambda expression.
9 8 7 6 5 4 3 2 1 0
 */

• is_sorted 범위 내 원소들이 정렬된 상태이면 true, 그렇지 않으면 false를 반환.

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

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

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

// since C++11 until C++20
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// since C++20
template< class ForwardIt, class Compare >
constexpr bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                Compare comp );

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

int main() {
    int digits[] = {3, 1, 4, 1, 5};

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: " << boolalpha;
    cout << is_sorted(begin(digits), end(digits)) << endl;

    sort(begin(digits), end(digits));

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: ";
    cout << is_sorted(begin(digits), end(digits)) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true
 */

• is_sorted_until 최초로 정렬되지 않은 범위의 첫번째 원소의 iterator를 반환.

// since C++11 until C++20
template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

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

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last );

// since C++11 until C++20
template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

// since C++20
template< class ForwardIt, class Compare >
constexpr ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Compare >
ForwardIt is_sorted_until( ExecutionPolicy&& policy,
                           ForwardIt first, ForwardIt last, Compare comp );

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

int main() {
    random_device rd;
    mt19937 g(rd());
    const int N = 6;
    int nums[N] = {3, 1, 4, 1, 5, 9};

    const int min_sorted_size = 4;
    int sorted_size = 0;
    do {
        shuffle(nums, nums + N, g);
        int *sorted_end = is_sorted_until(nums, nums + N);
        sorted_size = distance(nums, sorted_end);

        for (auto i : nums) cout << i << ' ';
        cout << " : " << sorted_size << " initial sorted elements" << endl;
    } while (sorted_size < min_sorted_size);

    return 0;
}

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

• partial_sort 범위 내 부분 원소들만 정렬.

  • partial_sort_copy 정렬된 부분 원소들만 복사.

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

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

template< class InputIt, class RandomIt >
RandomIt partial_sort_copy( InputIt first, InputIt last,
                            RandomIt d_first, RandomIt d_last );

template< class InputIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( InputIt first, InputIt last,
                            RandomIt d_first, RandomIt d_last,
                            Compare comp );

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

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

template< class InputIt, class RandomIt >
constexpr RandomIt partial_sort_copy( InputIt first, InputIt last,
                                      RandomIt d_first, RandomIt d_last );

template< class InputIt, class RandomIt, class Compare >
constexpr RandomIt partial_sort_copy( InputIt first, InputIt last,
                                      RandomIt d_first, RandomIt d_last,
                                      Compare comp );

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

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

template< class ExecutionPolicy, class ForwardIt, class RandomIt >
RandomIt partial_sort_copy( ExecutionPolicy&& policy,
                            ForwardIt first, ForwardIt last,
                            RandomIt d_first, RandomIt d_last );

template< class ExecutionPolicy, class ForwardIt, class RandomIt, class Compare >
RandomIt partial_sort_copy( ExecutionPolicy&& policy,
                            ForwardIt first, ForwardIt last,
                            RandomIt d_first, RandomIt d_last,
                            Compare comp );

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

template <class T>
void print(string msg, T &s) {
    cout << msg;
    for (int a : s) cout << a << " ";
    cout << endl;
}

int main() {
    array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print("Before partial_sort(): ", s);
    partial_sort(s.begin(), s.begin() + 3, s.end());
    print("After partial_sort(): ", s);

    vector<int> v0{4, 2, 5, 1, 3};
    vector<int> v1{10, 11, 12};
    vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    cout << endl << "Before partial_sort_copy():" << endl;
    print("v0: ", v0);
    print("v1: ", v1);
    print("v2: ", v2);
    cout << "After partial_sort_copy():" << endl;
    auto it = partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
    print("Writing to the smaller vector in ascending order gives (v1): ", v1);
    if(it == v1.end())
        cout << "The return value is the end iterator" << endl;

    it = partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                           greater<int>());
    print("Writing to the larger vector in descending order gives (v2): ", v2);
    cout << "The return value is the iterator to " << *it << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before partial_sort(): 5 7 4 2 8 6 1 9 0 3
After partial_sort(): 0 1 2 7 8 6 5 9 4 3

Before partial_sort_copy():
v0: 4 2 5 1 3
v1: 10 11 12
v2: 10 11 12 13 14 15 16
After partial_sort_copy():
Writing to the smaller vector in ascending order gives (v1): 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives (v2): 5 4 3 2 1 15 16
The return value is the iterator to 15
 */

• stable_sort 크기가 같은 원소의 상대적 순서를 유지한 상태로 정렬.

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

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

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

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

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

struct Employee {
    int age;
    string name;  // Does not participate in comparisons
};

bool operator<(const Employee & lhs, const Employee & rhs) {
    return lhs.age < rhs.age;
}

int main() {
    vector<Employee> v =
    {
        {108, "Zaphod"},
        {32, "Arthur"},
        {108, "Ford"},
    };

    stable_sort(v.begin(), v.end());
    for (const Employee & e : v)
        cout << e.age << ", " << e.name << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
32, Arthur
108, Zaphod
108, Ford
 */

• nth_element 범위 내 원소들을 오름차순 정렬.

  • n번째 원소를 찾는 것이 목적이므로 원본을 수정하며, 반환형은 void.

  • 두번째 인자인 nth는 정렬 후 위치하는 원소가 되며, 앞의 원소들은 모두 nth보다 작고, 뒤의 원소들은 모두 nth 보다 큼.

  • 다만 비교자 함수를 전달할 경우 오름차순이 아닌 내림차순 정렬을 수행할 수 있음. (다른 비교도 가능)

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

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

// since C++17
template< class ExecutionPolicy, class RandomIt >
void nth_element( ExecutionPolicy&& policy,
                  RandomIt first, RandomIt nth, RandomIt last )

// until C++20
template< class RandomIt, class Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );

// since C++20
template< class RandomIt, class Compare >
constexpr void nth_element( RandomIt first, RandomIt nth, RandomIt last,
                            Compare comp );

// since C++17
template< class ExecutionPolicy, class RandomIt, class Compare >
void nth_element( ExecutionPolicy&& policy, 
                  RandomIt first, RandomIt nth, RandomIt last, Compare comp );

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

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

    nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    cout << "The median is " << v[v.size()/2] << endl;

    nth_element(v.begin(), v.begin()+1, v.end(), greater<int>());
    cout << "The second largest element is " << v[1] << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
The median is 5
The second largest element is 7
 */

파티셔닝 알고리즘 (Partitioning Algorithm)

• partition 범위 내 원소들을 주어진 함수에 의해 두 그룹으로 나눔.

  • partition_copy 두 그룹으로 나뉘어진 원소들을 복사. (원본 유지)

// until C++11
template< class BidirIt, class UnaryPredicate >
BidirIt partition( BidirIt first, BidirIt last, UnaryPredicate p );

// since C++11 until C++20
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate >
std::pair<OutputIt1, OutputIt2>
     partition_copy( InputIt first, InputIt last,
                     OutputIt1 d_first_true, OutputIt2 d_first_false,
                     UnaryPredicate p );

// since C++20
template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate >
constexpr std::pair<OutputIt1, OutputIt2>
               partition_copy( InputIt first, InputIt last,
                               OutputIt1 d_first_true, OutputIt2 d_first_false,
                               UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt partition( ExecutionPolicy&& policy, 
                     ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3,
          class UnaryPredicate >
std::pair<ForwardIt2, ForwardIt3>
     partition_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 d_first_true, ForwardIt3 d_first_false,
                     UnaryPredicate p );

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

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last) {
    if(first == last) return;
    auto pivot = *next(first, distance(first,last)/2);
    ForwardIt middle1 = partition(
            first, last, [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = partition(
            middle1, last, [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
}

int main() {
    vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    cout << "Original vector:\n    ";
    for(int elem : v) cout << elem << ' ';

    auto it = partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});

    cout << endl << "Partitioned vector:\n    ";
    copy(begin(v), it, ostream_iterator<int>(cout, " "));
    cout << " * ";
    copy(it, end(v), ostream_iterator<int>(cout, " "));

    forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    cout << endl << "Unsorted list:\n    ";
    for(int n : fl) cout << n << ' ';
    cout << endl;

    quicksort(begin(fl), end(fl));
    cout << "Sorted using quicksort:\n    ";
    for(int fi : fl) cout << fi << ' ';
    cout << endl;

    cout << "Call partition_copy():" << endl;

    int arr [10] = {1,2,3,4,5,6,7,8,9,10};
    int true_arr [5] = {0};
    int false_arr [5] = {0};

    cout << "Before: ";
    for (int n : arr) cout << n << " ";
    cout << endl;

    partition_copy(begin(arr), end(arr), begin(true_arr), begin(false_arr),
                   [] (int i) {return i > 5;});

    cout << "true_arr: ";
    for (int x : true_arr) cout << x << ' ';
    cout << endl;

    cout << "false_arr: ";
    for (int x : false_arr) cout << x << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Original vector:
    0 1 2 3 4 5 6 7 8 9
Partitioned vector:
    0 8 2 6 4  * 5 3 7 1 9
Unsorted list:
    1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92
Sorted using quicksort:
    -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92
Call partition_copy():
Before: 1 2 3 4 5 6 7 8 9 10
true_arr: 6 7 8 9 10
false_arr: 1 2 3 4 5
 */

• is_partition 두 그룹이 주어진 함수에 의해 나뉘어져 있으면 true, 그렇지 않으면 false 반환.

// since C++11 until C++20
template< class InputIt, class UnaryPredicate >
bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// since C++20
template< class InputIt, class UnaryPredicate >
constexpr bool is_partitioned( InputIt first, InputIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
bool is_partitioned( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                     UnaryPredicate p );

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

int main() {
    array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    auto is_even = [](int i){ return i % 2 == 0; };
    cout.setf(ios_base::boolalpha);
    cout << is_partitioned(v.begin(), v.end(), is_even) << ' ';

    partition(v.begin(), v.end(), is_even);
    cout << is_partitioned(v.begin(), v.end(), is_even) << ' ';

    reverse(v.begin(), v.end());
    cout << is_partitioned(v.cbegin(), v.cend(), is_even) << ' ';
    cout << is_partitioned(v.crbegin(), v.crend(), is_even) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
false true false true
 */

• stable_partition 상대적 순서를 유지한 상태로 두 그룹으로 나눔.

template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class BidirIt, class UnaryPredicate >
BidirIt stable_partition( ExecutionPolicy&& policy, BidirIt first, BidirIt last,
                          UnaryPredicate p );

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

int main() {
    vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
    stable_partition(v.begin(), v.end(), [](int n){return n>0;});
    for (int n : v) cout << n << ' ';
    cout << endl;

    return 0;
}

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

• partition_point 두 그룹으로 나뉜 상태에서 첫번째 파티션이 끝나는 위치의 iterator를 반환.

// since C++11 until C++20
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );

// since C++20
template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt partition_point( ForwardIt first, ForwardIt last,
                                     UnaryPredicate p );

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

int main() {
    array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    auto is_even = [](int i){ return i % 2 == 0; };
    partition(v.begin(), v.end(), is_even);

    auto p = partition_point(v.begin(), v.end(), is_even);

    cout << "Before partition:\n    ";
    copy(v.begin(), p, ostream_iterator<int>(cout, " "));
    cout << endl << "After partition:\n    ";
    copy(p, v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

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

변경 가능 알고리즘 (Modifying Sequence Algorithm)

• copy 원소들을 복사.

  • copy_n 원하는 개수만큼 원소들을 복사

  • copy_if 원소들 중 조건에 일치하는 것들만 복사

  • copy_backward 원소들을 뒤에서부터 복사

// until C++20
template< class InputIt, class OutputIt >
OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class UnaryPredicate >
constexpr OutputIt copy_if( InputIt first, InputIt last,
                            OutputIt d_first, UnaryPredicate pred );

template< class InputIt, class Size, class OutputIt >
constexpr OutputIt copy_n( InputIt first, Size count, OutputIt result );

template< class BidirIt1, class BidirIt2 >
constexpr BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                 ForwardIt2 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate >
ForwardIt2 copy_if( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 d_first, UnaryPredicate pred );

template< class ExecutionPolicy, class ForwardIt1, class Size, class ForwardIt2 >
ForwardIt2 copy_n( ExecutionPolicy&& policy, ForwardIt1 first, Size count,
                   ForwardIt2 result );

// since C++11
template< class InputIt, class OutputIt, class UnaryPredicate >
OutputIt copy_if( InputIt first, InputIt last,
                  OutputIt d_first, UnaryPredicate pred );

template< class InputIt, class Size, class OutputIt >
OutputIt copy_n( InputIt first, Size count, OutputIt result );

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

int main() {
    vector<int> from_vector, to_vector;
    for (int i = 0; i < 10; i++)
        from_vector.push_back(i);

    copy(from_vector.begin(), from_vector.end(), back_inserter(to_vector));
    /* same as
     *    vector<int> to_vector(from_vector.size());
     *    copy(from_vector.begin(), from_vector.end(), to_vector.begin());
     * or
     *    vector<int> to_vector = from_vector;
     */

    cout << "to_vector contains: ";
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "odd numbers in to_vector are: ";
    copy_if(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "),
            [](int x) { return (x % 2) == 1; });
    cout << endl;

    to_vector.clear();
    to_vector.resize(20);
    cout << "4 numbers in to_vector are: ";
    copy_n(from_vector.cbegin(), 4, to_vector.begin());
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "copy_backward() on to_vector: ";
    copy_backward(from_vector.begin(), from_vector.end(), to_vector.end());
    copy(to_vector.begin(), to_vector.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
to_vector contains: 0 1 2 3 4 5 6 7 8 9
odd numbers in to_vector are: 1 3 5 7 9
4 numbers in to_vector are: 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
copy_backward() on to_vector: 0 1 2 3 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9
 */

• move 원소들을 이동시킴.

  • move_backward 원소들을 뒤에서부터 이동시킴.

// since C++11 until C++20
template< class InputIt, class OutputIt >
OutputIt move( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++20
template< class InputIt, class OutputIt >
constexpr OutputIt move( InputIt first, InputIt last, OutputIt d_first );

template< class BidirIt1, class BidirIt2 >
constexpr BidirIt2 move_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 move( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                 ForwardIt2 d_first );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator> // next()
#include <thread>
#include <chrono>
using namespace std;

void fn(int n) {
    this_thread::sleep_for(chrono::seconds(n));
    cout << "thread " << n << " ended" << endl;
}

int main() {
    vector<thread> v;
    list<thread> l1, l2;

    // copy() would not compile, because thread is noncopyable
    for (int i = 1; i < 7; i++)
        v.emplace_back(fn, i);

    cout << "move(): " << endl;
    move(v.begin(), next(v.begin(), 3), back_inserter(l1));
    for (auto& t : l1) t.join();

    cout << endl << "move_backward(): " << endl;
    l2.emplace_back(fn, 0);
    l2.emplace_back(fn, 0);
    l2.resize(5);
    // error because [v.begin(), v.begin() + 3] are empty.
    // move_backward(v.begin(), v.end(), l2.end());
    move_backward(v.begin() + 3, v.end(), l2.end());
    for (auto& t : l2) {
        t.join();
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
move():
thread 1 ended
thread 2 ended
thread 3 ended

move_backward():
thread 0 ended
thread 0 ended
thread 4 ended
thread 5 ended
thread 6 ended
 */

• fill 특정 값으로 원소들을 채움.

  • fill_n 특정 값으로 원하는 개수만큼 원소들을 채움.

// until C++20
template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );

// since C++20
template< class ForwardIt, class T >
constexpr void fill( ForwardIt first, ForwardIt last, const T& value );

template< class OutputIt, class Size, class T >
constexpr OutputIt fill_n( OutputIt first, Size count, const T& value );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
void fill( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
           const T& value );

template< class ExecutionPolicy, class ForwardIt, class Size, class T >
ForwardIt fill_n( ExecutionPolicy&& policy, ForwardIt first, Size count,
                  const T& value );

// until C++11
template< class OutputIt, class Size, class T >
void fill_n( OutputIt first, Size count, const T& value );

// since C++11 until C++20
template< class OutputIt, class Size, class T >
OutputIt fill_n( OutputIt first, Size count, const T& value );

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

int main() {
    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    fill(v.begin(), v.end(), -1);

    for (auto elem : v)
        cout << elem << " ";
    cout << endl;

    fill_n(v.begin(), 5, 0);
    for (auto elem : v)
        cout << elem << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
0 0 0 0 0 -1 -1 -1 -1 -1
 */

• transform 범위 내 각 원소에 대해 주어진 함수를 호출.

// until C++20
template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

// since C++20
template< class InputIt, class OutputIt, class UnaryOperation >
constexpr OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                              UnaryOperation unary_op );

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
constexpr OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                              OutputIt d_first, BinaryOperation binary_op );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryOperation >
ForwardIt2 transform( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 d_first, UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class ForwardIt3, class BinaryOperation >
ForwardIt3 transform( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                      ForwardIt2 first2, ForwardIt3 d_first,
                      BinaryOperation binary_op );

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <functional> // plus<>()
using namespace std;

int main() {
    string s("hello");
    transform(s.begin(), s.end(), s.begin(),
            [](unsigned char c) -> unsigned char { return toupper(c); });

    vector<size_t> ordinals;
    transform(s.begin(), s.end(), back_inserter(ordinals),
            [](unsigned char c) -> size_t { return c; });

    cout << s << ':';
    for (auto ord : ordinals) cout << ' ' << ord;
    cout << endl;
    
    // ordinals[i] = ordinals[i] + ordinals[i]
    transform(ordinals.cbegin(), ordinals.cend(), ordinals.cbegin(),
            ordinals.begin(), plus<>{});

    for (auto ord : ordinals) cout << ord << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
HELLO: 72 69 76 76 79
144 138 152 152 158
 */

• generate 범위 내 원소들을 주어진 함수를 호출한 결과로 채움.

  • generate_n 범위 내 특정 개수만큼 원소들을 주어진 함수를 호출한 결과로 채움.

// until C++20
template< class ForwardIt, class Generator >
void generate( ForwardIt first, ForwardIt last, Generator g );

// since C++20
template< class ForwardIt, class Generator >
constexpr void generate( ForwardIt first, ForwardIt last, Generator g );

template< class OutputIt, class Size, class Generator >
constexpr OutputIt generate_n( OutputIt first, Size count, Generator g );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class Generator >
void generate( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
               Generator g );

template< class ExecutionPolicy, class ForwardIt , class Size, class Generator >
ForwardIt generate_n( ExecutionPolicy&& policy, ForwardIt first,
                      Size count, Generator g );

// until C++11
template< class OutputIt, class Size, class Generator >
void generate_n( OutputIt first, Size count, Generator g );

// since C++11 until C++20
template< class OutputIt, class Size, class Generator >
OutputIt generate_n( OutputIt first, Size count, Generator g );

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

int fn() {
    static int i = 1;
    return i++;
}

int main() {
    vector<int> v(5);
    generate(v.begin(), v.end(), fn);

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    // Initialize with default values 0,1,2,3,4 from a lambda function
    // Equivalent to iota(v.begin(), v.end(), 0);
    generate(v.begin(), v.end(), [n = 0] () mutable { return n++; });

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    generate_n(v.begin(), 2, []() { return -1; });

    cout << "v: ";
    for (auto iv: v)
        cout << iv << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
v: 1 2 3 4 5
v: 0 1 2 3 4
v: -1 -1 2 3 4
 */

• remove 범위 내 특정 값과 일치하는 원소들을 제거.

  • remove_if 조건과 일치하는 원소들을 제거.

  • remove_copy 특정 값과 일치하는 원소들을 복사한 후 제거. (원본은 유지)

  • remove_copy_if 조건과 일치하는 원소들을 복사한 후 제거. (원본은 유지)

  • 원본 컨테이너에서 제거할 원소는 뒤의 원소를 옮김(move)으로써 제거하기 때문에 erase() 등의 멤버 함수를 사용해서 뒤에 남은 부분을 제거할 필요가 있음.

  • 반환값은 옮긴 후 마지막 원소를 참조하는 iterator.

// until C++20
template< class ForwardIt, class T >
ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

template< class InputIt, class OutputIt, class T >
OutputIt remove_copy( InputIt first, InputIt last, OutputIt d_first,
                      const T& value );

template< class InputIt, class OutputIt, class UnaryPredicate >
OutputIt remove_copy_if( InputIt first, InputIt last, OutputIt d_first,
                         UnaryPredicate p );

// since C++20
template< class ForwardIt, class T >
constexpr ForwardIt remove( ForwardIt first, ForwardIt last, const T& value );

template< class ForwardIt, class UnaryPredicate >
constexpr ForwardIt remove_if( ForwardIt first, ForwardIt last,
                               UnaryPredicate p );

template< class InputIt, class OutputIt, class T >
constexpr OutputIt remove_copy( InputIt first, InputIt last, OutputIt d_first,
                                const T& value );

template< class InputIt, class OutputIt, class UnaryPredicate >
constexpr OutputIt remove_copy_if( InputIt first, InputIt last, OutputIt d_first,
                                   UnaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
ForwardIt remove( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  const T& value );

template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                     UnaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 remove_copy( ExecutionPolicy&& policy,
                        ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first, const T& value );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate >
ForwardIt2 remove_copy_if( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, UnaryPredicate p );

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

int main()
{
    string str1 = "Text with some   spaces";
    str1.erase(remove(str1.begin(), str1.end(), ' '), str1.end());
    cout << str1 << endl;

    string str2 = "Text\n with\tsome \t  whitespaces\n\n";
    string str3 = str2;
    str2.erase(remove_if(str2.begin(), str2.end(),
                [](unsigned char x) { return isspace(x); }), str2.end());
    cout << str2 << endl;

    remove(str3.begin(), str3.end(), '\n');
    // after just moving
    cout << str3 << endl;

    str3 = "Text with some   spaces";
    cout << "Before: " << str3 << endl;
    cout << "After remove_copy(): ";
    remove_copy(str3.begin(), str3.end(), ostream_iterator<char>(cout), ' ');
    cout << endl;

    str3 = "Text with some   spaces";
    cout << "Before: " << str3 << endl;
    cout << "After remove_copy_if(): ";
    remove_copy_if(str3.begin(), str3.end(), ostream_iterator<char>(cout),
                   [](unsigned char x) { return isspace(x); });
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Textwithsomespaces
Textwithsomewhitespaces
Text with	some 	  whitespacess


Before: Text with some   spaces
After remove_copy(): Textwithsomespaces
Before: Text with some   spaces
After remove_copy_if(): Textwithsomespaces
 */

• replace 특정 범위 내 원소들을 주어진 원소들로 치환.

  • replace_if 범위 내 조건과 일치하는 원소들을 주어진 원소들로 치환.

  • replace_copy 특정 범위 내 원소들을 복사한 후, 주어진 원소들로 치환. (원본은 유지)

  • replace_copy_if 범위 내 조건과 일치하는 원소들을 복사한 후, 주어진 원소들로 치환. (원본은 유지)

// until C++20
template< class ForwardIt, class T >
void replace( ForwardIt first, ForwardIt last,
              const T& old_value, const T& new_value );

template< class ForwardIt, class UnaryPredicate, class T >
void replace_if( ForwardIt first, ForwardIt last,
                 UnaryPredicate p, const T& new_value );

template< class InputIt, class OutputIt, class T >
OutputIt replace_copy( InputIt first, InputIt last, OutputIt d_first,
                       const T& old_value, const T& new_value );

template< class InputIt, class OutputIt, class UnaryPredicate, class T >
OutputIt replace_copy_if( InputIt first, InputIt last, OutputIt d_first,
                          UnaryPredicate p, const T& new_value );

// since C++20
template< class ForwardIt, class T >
constexpr void replace( ForwardIt first, ForwardIt last,
                        const T& old_value, const T& new_value );

template< class ForwardIt, class UnaryPredicate, class T >
constexpr void replace_if( ForwardIt first, ForwardIt last,
                           UnaryPredicate p, const T& new_value );

template< class InputIt, class OutputIt, class T >
constexpr OutputIt replace_copy( InputIt first, InputIt last, OutputIt d_first,
                                 const T& old_value, const T& new_value );

template< class InputIt, class OutputIt, class UnaryPredicate, class T >
constexpr OutputIt replace_copy_if( InputIt first, InputIt last, OutputIt d_first,
                                    UnaryPredicate p, const T& new_value );

// since C++17
template< class ExecutionPolicy, class ForwardIt, class T >
void replace( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
              const T& old_value, const T& new_value );

template< class ExecutionPolicy, class ForwardIt, class UnaryPredicate, class T >
void replace_if( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                 UnaryPredicate p, const T& new_value );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 replace_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                         ForwardIt2 d_first, const T& old_value, const T& new_value);

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class UnaryPredicate, class T >
ForwardIt2 replace_copy_if( ExecutionPolicy&& policy,
                            ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 d_first, UnaryPredicate p,
                            const T& new_value );

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

void print(array<int, 10> &s, string msg) {
    cout << msg;
    for (int a : s)
        cout << a << " ";
    cout << endl;
}

int main()
{
    array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, "Before: ");

    replace(s.begin(), s.end(), 8, 88);
    print(s, "After replace(): ");

    replace_if(s.begin(), s.end(), bind(less<int>(), placeholders::_1, 5), 55);
    print(s, "After replace_if(): ");

    cout << "After replace_copy(): ";
    replace_copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "), 88, 1);
    cout << endl;

    cout << "After replace_copy_if(): ";
    replace_copy_if(s.begin(), s.end(), ostream_iterator<int>(cout, " "),
                    [](int n){return n > 5;}, 99);
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before: 5 7 4 2 8 6 1 9 0 3
After replace(): 5 7 4 2 88 6 1 9 0 3
After replace_if(): 5 7 55 55 88 6 55 9 55 55
After replace_copy(): 5 7 55 55 5 6 55 9 55 55
After replace_copy_if(): 5 99 99 99 99 99 99 99 99 99
 */

• swap 범위 내 두 원소를 교환.

  • swap_ranges 주어진 두 범위의 원소들을 교환.

  • iter_swap 두 반복자가 참조하는 원소들을 교환.

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <random>
#include <functional>
using namespace std;

template<class ForwardIt>
void selection_sort(ForwardIt begin, ForwardIt end) {
    for (ForwardIt i = begin; i != end; ++i)
        iter_swap(i, min_element(i, end));
}


int main() {
    int a = 5, b = 3;
    cout << "Before swap(): ";
    cout << a << ' ' << b << endl;

    swap(a,b);

    cout << "After swap(): ";
    cout << a << ' ' << b << endl;

    vector<int> v = {1, 2, 3, 4, 5};
    list<int> l = {-1, -2, -3, -4, -5};

    cout << "Call swap_ranges():" << endl;

    swap_ranges(v.begin(), v.begin()+3, l.begin());

    for(int n : v) cout << n << ' ';
    cout << endl;
    for(int n : l) cout << n << ' ';
    cout << endl;

    cout << "Call iter_swap():" << endl;
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dist(-10, 10);
    vector<int> v2;
    generate_n(back_inserter(v2), 20, bind(dist, gen));

    cout << "Before sort: ";
    for(auto e : v2) cout << e << " ";

    selection_sort(v2.begin(), v2.end());

    cout << endl << "After sort: ";
    for(auto e : v2) cout << e << " ";
    cout << endl;
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before swap(): 5 3
After swap(): 3 5
Call swap_ranges():
-1 -2 -3 4 5
1 2 3 -4 -5
Call iter_swap():
Before sort: 8 7 -9 -7 9 0 -8 -8 -2 -9 -4 8 -1 -9 -1 -8 -6 10 -2 -9
After sort: -9 -9 -9 -9 -8 -8 -8 -7 -6 -4 -2 -2 -1 -1 0 7 8 8 9 10
 */

• reverse 범위 내 원소들을 뒤집음.

  • reverse_copy 범위 내 원소들을 뒤집은 상태로 복사함. (원본은 유지)

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

template< class BidirIt, class OutputIt >
OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );

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

template< class BidirIt, class OutputIt >
constexpr OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );

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

template< class ExecutionPolicy, class BidirIt, class ForwardIt >
ForwardIt reverse_copy( ExecutionPolicy&& policy, BidirIt first, BidirIt last,
                        ForwardIt d_first );

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

int main() {
    cout << "Call reverse():" << endl;
    vector<int> v{1,2,3};
    reverse(begin(v), end(v));
    for(auto e : v) cout << e;
    cout << endl;

    int a[] = {4, 5, 6, 7};
    reverse(begin(a), end(a));
    for(auto e : a) cout << e;
    cout << endl;

    cout << "Call reverse_copy():" << endl;
    // lambda
    auto print = [](vector<int> const& v) {
        for (const auto& value : v)
            cout << value << ' ';
        cout << '\t';
    };

    print(v);
    vector<int> destination(3);
    reverse_copy(begin(v), end(v), begin(destination));
    print(destination);

    reverse_copy(rbegin(v), rend(v), begin(destination));
    print(destination);

    cout << endl;
    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
Call reverse():
321
7654
Call reverse_copy():
3 2 1 	1 2 3 	3 2 1
 */

• rotate 범위 내 원소들을 왼쪽으로 회전시킴.

  • rotate_copy 범위 내 원소들을 왼쪽으로 회전시칸 후 복사. (원본은 유지)

// until C++11
template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

// since C++11 until C++20
template< class ForwardIt >
ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

// until C++20
template< class ForwardIt, class OutputIt >
OutputIt rotate_copy( ForwardIt first, ForwardIt n_first,
                      ForwardIt last, OutputIt d_first );

// since C++20
template< class ForwardIt >
constexpr ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

template< class ForwardIt, class OutputIt >
constexpr OutputIt rotate_copy( ForwardIt first, ForwardIt n_first,
                                ForwardIt last, OutputIt d_first );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt rotate( ExecutionPolicy&& policy,  ForwardIt first, ForwardIt n_first,
                  ForwardIt last );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 rotate_copy( ExecutionPolicy&& policy, ForwardIt1 first,
                        ForwardIt1 n_first, ForwardIt1 last, ForwardIt2 d_first );

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

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

int main() {
    vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    print("Before: ", v);

    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);
    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);
    rotate(v.begin(), v.begin() + 1, v.end());
    print("Simple left rotate: ", v);

    rotate(v.rbegin(), v.rbegin() + 3, v.rend());
    print("Simple right rotate: ", v);

    vector<int> v2(v.size());
    auto pivot = find(v.begin(), v.end(), 5);
    rotate_copy(v.begin(), pivot, v.end(), v2.begin());
    print("Call rotate_copy(): ", v2);

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Before: 1 2 3 4 5 6 7 8 9
Simple left rotate: 2 3 4 5 6 7 8 9 1
Simple left rotate: 3 4 5 6 7 8 9 1 2
Simple left rotate: 4 5 6 7 8 9 1 2 3
Simple right rotate: 1 2 3 4 5 6 7 8 9
Call rotate_copy(): 5 6 7 8 9 1 2 3 4
 */

• shift_left, shift_right 범위 내 주어진 횟수만큼 쉬프트 연산 (C++20부터 지원)

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

struct S {
    int value{0};
    bool specified_state{true};

    S(int v = 0) : value{v} {}
    S(S const& rhs) = default;
    S(S&& rhs) { *this = move(rhs); }
    S& operator=(S const& rhs) = default;
    S& operator=(S&& rhs) {
        if (this != &rhs) {
            value = rhs.value;
            specified_state = rhs.specified_state;
            rhs.specified_state = false;
        }
        return *this;
    }
};

ostream& operator<< (ostream& os, vector<S> const& v) {
    for (const auto& s : v)
        s.specified_state ? os << s.value << ' ' : os << "? ";
    return os << '\n';
}

int main() {
    vector<S> v{1,2,3,4,5,6,7};
    cout << v;

    shift_left(v.begin(), v.end(), 3);
    cout << v;

    shift_right(v.begin(), v.end(), 2);
    cout << v;

    return 0;
}

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

• shuffle 무작위로 원소들을 섞음.

// since C++11
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

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

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

    random_device rd;
    mt19937 g(rd());

    shuffle(v.begin(), v.end(), g);

    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

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

• sample 범위 내에서 무작위로 주어진 개수만큼 원소를 샘플링. (C++17 부터 지원)

// since C++17
template< class PopulationIterator, class SampleIterator,
          class Distance, class URBG >
SampleIterator sample( PopulationIterator first, PopulationIterator last,
                       SampleIterator out, Distance n, URBG&& g);

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

int main() {
    string in = "hgfedcba", out;
    sample(in.begin(), in.end(), back_inserter(out), 5,
           mt19937{random_device{}()});
    cout << "five random letters out of " << in;
    cout << " : " << out << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
five random letters out of hgfedcba : gedcb
$ ./a.out
five random letters out of hgfedcba : hgeda
 */

• unique 중복된 원소를 제거한 후 마지막 원소의 iterator 반환.

  • unique_copy 중복된 원소를 제거한 후 복사. (원본 유지)

// until C++20
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );

template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

template< class InputIt, class OutputIt >
OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryPredicate >
OutputIt unique_copy( InputIt first, InputIt last,
                      OutputIt d_first, BinaryPredicate p );

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

template< class ForwardIt, class BinaryPredicate >
constexpr ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

template< class InputIt, class OutputIt >
constexpr OutputIt unique_copy( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryPredicate >
constexpr OutputIt unique_copy( InputIt first, InputIt last,
                                OutputIt d_first, BinaryPredicate p );

// since C++17
template< class ExecutionPolicy, class ForwardIt >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  BinaryPredicate p );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt2 unique_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
ForwardIt2 unique_copy( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                        ForwardIt2 d_first, BinaryPredicate p );

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

int main()  {
    // a vector containing several duplicate elements
    vector<int> v{1,2,1,1,3,3,3,4,5,4};

    // remove consecutive (adjacent) duplicates
    auto last = unique(v.begin(), v.end());
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    for (int i : v) cout << i << " ";
    cout << endl;

    // sort followed by unique, to remove all duplicates
    sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
    last = unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    for (int i : v) cout << i << " ";
    cout << endl;

    string s1 = "The      string    with many       spaces!";
    string s2;
    cout << "before: " << s1 << endl;
    unique_copy(s1.begin(), s1.end(), back_inserter(s2),
                [](char c1, char c2){ return c1 == ' ' && c2 == ' '; });
    cout << "after:  " << s2 << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
1 2 1 3 4 5 4
1 2 3 4 5
before: The      string    with many       spaces!
after:  The string with many spaces!
 */