Move Fast

파티셔닝 알고리즘 (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
 */