Move Fast

Threading Building Blocks

Threading Building Blocks (TBB) is a C++ template library developed by Intel for parallel programming on multi-core processors. Using TBB, a computation is broken down into tasks that can run in parallel. The library manages and schedules threads to execute these tasks.

by Wikipedia

How to use

on MacOS (tested on Catalina)

1. brew install tbb

2. echo | gcc -v -x c++ -E -

   • If there is not /usr/local/include below #include <...> search starts here:

   • Include the path first.

   • Also, check ls -l /usr/local/lib/*tbb*

3. ln -s /usr/local/Cellar/tbb/2020_U3_1/include/tbb /usr/local/include/tbb

4. g++ -g -std=c++17 <FILENAME> -pthread -ltbb

5. ./a.out

There are some useful library files.

It's fast!

I referred to parallel_reduce().

#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <tbb/parallel_reduce.h>
#include <tbb/blocked_range.h>
using namespace std;
using namespace tbb;

class SumFoo {
    float* my_a;
public:
    float my_sum;
    void operator()( const blocked_range<size_t>& r ) {
        float *a = my_a;
        float sum = my_sum;
        size_t end = r.end();
        for( size_t i=r.begin(); i!=end; ++i )
            sum += a[i];
        my_sum = sum;
    }

    SumFoo( SumFoo& x, split ) : my_a(x.my_a), my_sum(0) {}

    void join( const SumFoo& y ) {my_sum+=y.my_sum;}

    SumFoo( float a[] ) :
        my_a(a), my_sum(0)
    {}
};

float SerialSumFoo( float a[], size_t n ) {
    float sum = 0;
    for( size_t i=0; i!=n; ++i )
        sum += a[i];
    return sum;
}

float ParallelSumFoo( float a[], size_t n ) {
    SumFoo sf(a);
    parallel_reduce( blocked_range<size_t>(0,n), sf );
    return sf.my_sum;
}

const size_t MAX_SZ = 10'000'000;
float a[MAX_SZ];
int main() {
    for (int i = 0; i < MAX_SZ; i++) a[i] = 0.1;

    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        float result = SerialSumFoo(a, MAX_SZ);
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        cout << "Serial Sum = " << result << ", took " << ms.count() << " ms" << endl;
    }
    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        float result = ParallelSumFoo(a, MAX_SZ);
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        cout << "Parallel Sum: " << result << ", took " << ms.count() << " ms" << endl;
    }

    return 0;
}

• In addition, we are able to use Parallel STL.

• Before including headers, install pstl from OneDPL.

수치 알고리즘 (Numeric Algorithm)

• iota 주어진 컨테이너를 특정 값에서 순서대로 증가하는 원소들로 채움.

// since C++11 until C++20
template< class ForwardIt, class T >
void iota( ForwardIt first, ForwardIt last, T value );

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

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

int main() {
    list<int> l(10);
    iota(l.begin(), l.end(), -4);

    vector<list<int>::iterator> v(l.size());
    iota(v.begin(), v.end(), l.begin());

    shuffle(v.begin(), v.end(), mt19937{random_device{}()});

    cout << "Contents of the list: ";
    for(auto n: l) cout << n << ' ';
    cout << endl;

    cout << "Contents of the list, shuffled: ";
    for(auto i: v) cout << *i << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
Contents of the list: -4 -3 -2 -1 0 1 2 3 4 5
Contents of the list, shuffled: -4 -2 1 5 3 4 -3 0 2 -1
 */

• accumulate 주어진 값부터 범위 내 원소들을 누적시킴.

  • 비교자 함수를 이용해서 덧셈뿐만 아니라 뺄셈이나 문자열 연산 등을 할 수 있음.

// until C++20
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

// since C++20
template< class InputIt, class T >
constexpr T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
constexpr T accumulate( InputIt first, InputIt last, T init, BinaryOperation op );

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

int main() {
    vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int sum = accumulate(v.begin(), v.end(), 0);
    int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());

    auto dash_fold = [](string a, int b) {
                         return move(a) + '-' + to_string(b);
                     };

    // Start with first element
    string s = accumulate(next(v.begin()), v.end(), to_string(v[0]), dash_fold);

    // Right fold using reverse iterators
    // Start with last element
    string rs = accumulate(next(v.rbegin()), v.rend(), to_string(v.back()), dash_fold);

    cout << "sum: " << sum << endl
         << "product: " << product << endl
         << "dash-separated string: " << s << endl
         << "dash-separated string (right-folded): " << rs << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
sum: 55
product: 3628800
dash-separated string: 1-2-3-4-5-6-7-8-9-10
dash-separated string (right-folded): 10-9-8-7-6-5-4-3-2-1
 */

• inner_product 주어진 값(초기값)에 두 범위의 내적을 더한 결과를 반환.

// until C++20
template< class InputIt1, class InputIt2, class T >
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init );

template<class InputIt1, class InputIt2, class T,
         class BinaryOperation1, class BinaryOperation2> 
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                 BinaryOperation1 op1, BinaryOperation2 op2 );

// since C++20
template< class InputIt1, class InputIt2, class T >
constexpr T inner_product( InputIt1 first1, InputIt1 last1,
                           InputIt2 first2, T init );

template<class InputIt1, class InputIt2, class T,
         class BinaryOperation1, class BinaryOperation2> 
constexpr T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T init,
                           BinaryOperation1 op1, BinaryOperation2 op2 );

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

int main() {
    vector<int> a{0, 1, 2, 3, 4};
    vector<int> b{5, 4, 2, 3, 1};

    int r1 = inner_product(a.begin(), a.end(), b.begin(), 0);
    cout << "Inner product of a and b: " << r1 << endl;

    int r2 = inner_product(a.begin(), a.end(), b.begin(), 0, plus<>(), equal_to<>());
    cout << "Number of pairwise matches between a and b: " <<  r2 << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
Inner product of a and b: 21
Number of pairwise matches between a and b: 2
 */

• adjacent_difference 범위 내 인접한 두 원소의 차이를 계산. 세번째 인자의 마지막 원소는 차이의 합.

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

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt adjacent_difference( InputIt first, InputIt last, 
                              OutputIt d_first, BinaryOperation op );

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

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt adjacent_difference( InputIt first, InputIt last, 
                                        OutputIt d_first, BinaryOperation op );

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

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

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
#include <functional>
#include <iterator>
using namespace std;

int main() {
    // Default implementation - the difference b/w two adjacent items
    vector<int> v = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    adjacent_difference(v.begin(), v.end(), v.begin());

    for (auto n : v) cout << n << ' ';
    cout << endl;

    // Fibonacci
    array<int, 10> a {1};
    adjacent_difference(begin(a), prev(end(a)), next(begin(a)), plus<> {});
    copy(begin(a), end(a), ostream_iterator<int> {cout, " "});
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
2 2 2 2 2 2 2 2 2 2
1 1 2 3 5 8 13 21 34 55
 */

• partial_sum 범위의 부분합을 계산. ex) ret[3] = [0, 3] 범위의 모든 원소들의 합.

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

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                      BinaryOperation op );

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

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                                BinaryOperation op );

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

int main() {
    vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // or vector<int>v(10, 2);

    cout << "The first 10 even numbers are: ";
    partial_sum(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    partial_sum(v.begin(), v.end(), v.begin(), multiplies<int>());
    cout << "The first 10 powers of 2 are: ";
    for (auto n : v) cout << n << " ";
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024
 */

• reduce 주어진 값(초기값)에다가 범위 내 원소들의 합을 더한 결과를 반환.

  • accumulate과 유사하나, 실행 정책(Execution Policy)가 추가되어 병렬 수행이 가능하다는 점에서 차이가 있음.

  • 실행 정책은 C++17 부터 추가된 것으로, 첫번째 인자에 std::execution::par 또는 std::execution::par_unseq 를 주면 쓰레드로 병렬 수행함.

  • 두 정책의 차이는 par은 중간에 다른 쓰레드가 개입되지 않음을 보장하며 데드락이 걸릴 위험이 없음. 반대로 par_unseq는 중간에 CPU가 다른 쓰레드를 실행할 수 있음을 의미.

  • 디폴트는 std::execution::seq 이며, 순차 실행을 의미.

  • 자세한 설명은 여기 참고.

  • 단, intell 에서는 실행 정책을 제공하지 않음.

  • intell 에서는 Threading Building Block (TBB) 라고 병렬 처리를 위한 C++ 라이브러리를 별도로 제공하고 있음.

  • 2018년도부터 TBB 내에 별도의 병렬화된 STL 함수(Parallel STL)들도 제공하는 것으로 확인됨.

// since C++17 until C++20
template<class InputIt>
typename std::iterator_traits<InputIt>::value_type reduce(
    InputIt first, InputIt last);

template<class InputIt, class T>
T reduce(InputIt first, InputIt last, T init);

// since C++20
template<class InputIt>
constexpr typename std::iterator_traits<InputIt>::value_type reduce(
    InputIt first, InputIt last);

template<class InputIt, class T>
constexpr T reduce(InputIt first, InputIt last, T init);

// since C++17
template<class ExecutionPolicy, class ForwardIt>
typename std::iterator_traits<ForwardIt>::value_type reduce(
    ExecutionPolicy&& policy,
    ForwardIt first, ForwardIt last);

template<class ExecutionPolicy, class ForwardIt, class T>
T reduce(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, T init);

template<class InputIt, class T, class BinaryOp>
constexpr T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);

template<class ExecutionPolicy, class ForwardIt, class T, class BinaryOp>
T reduce(ExecutionPolicy&& policy,
         ForwardIt first, ForwardIt last, T init, BinaryOp binary_op);

// only C++17
template<class InputIt, class T, class BinaryOp>
T reduce(InputIt first, InputIt last, T init, BinaryOp binary_op);

// ----------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <execution>
using namespace std;

int main() {
    const vector<double> v(10'000'007, 0.5);

    {
        const auto t1 = chrono::high_resolution_clock::now();
        const double result = accumulate(v.cbegin(), v.cend(), 0.0);
        const auto t2 = chrono::high_resolution_clock::now();
        const chrono::duration<double, milli> ms = t2 - t1;
        cout << fixed << "accumulate result " << result;
        cout << " took " << ms.count() << " ms" << endl;
    }

    {
        const auto t1 = chrono::high_resolution_clock::now();
        const double result = reduce(execution::par, v.cbegin(), v.cend());
        const auto t2 = chrono::high_resolution_clock::now();
        const chrono::duration<double, milli> ms = t2 - t1;
        cout << "reduce result " << result << " took ";
        cout << ms.count() << " ms" << endl;
    }

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
std::accumulate result 5000003.50000 took 12.7365 ms
std::reduce result 5000003.50000 took 5.06423 ms
 */

• exclusive_scan 각 원소는 자신을 제외하고 앞의 원소까지만 누적 연산. ex) ret[3] = [0, 2] 범위에서만 연산을 수행한 결과. (C++17)

  • 초기값이 있으면 그 값을 포함해서 연산함. 즉, ret[0] != 0 이고 ret[0] = 초기값.

• inclusive_scan 각 원소는 자신을 포함해서 누적 연산. ex) ret[3] = [0, 3] 범위에서만 연산을 수행한 결과. (C++17)

  • 초기값이 있으면 그 값을 포함해서 연산함. 즉, ret[0] = 첫번째 원소 + 초기값.

// since C++17 until C++20
template< class InputIt, class OutputIt, class T >
OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init );

template< class InputIt, class OutputIt, 
          class T, class BinaryOperation >
OutputIt exclusive_scan( InputIt first, InputIt last,
                         OutputIt d_first, T init, BinaryOperation binary_op );

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

template< class InputIt, class OutputIt, 
          class T, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   T init, BinaryOperation binary_op );

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

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, T init, BinaryOperation binary_op );

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

int main() {
    vector data = {3, 1, 4, 1, 5, 9, 2, 6};

    cout << "exclusive sum: ";
    exclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "), 0);

    cout << endl << "inclusive sum: ";
    inclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "));

    cout << endl << endl << "exclusive product: ";
    exclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "), 1,
                   multiplies<>{});

    cout << endl << "inclusive product: ";
    inclusive_scan(data.begin(), data.end(),
                   ostream_iterator<int>(cout, " "),
                   multiplies<>{});
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
exclusive sum: 0 3 4 8 9 14 23 25
inclusive sum: 3 4 8 9 14 23 25 31

exclusive product: 1 3 3 12 12 60 540 1080
inclusive product: 3 3 12 12 60 540 1080 6480
 */

• transform_reduce 각 원소들을 변환시킨 후, 축약한 결과를 반환. (C++17 부터 지원)

  • 초기값이 있으면, 초기값을 더해서 최종 결과를 반환.

  • 주어진 범위가 두 개일 경우, inner_product 함수와 동일하게 동작함. 차이점은 transform_reduce 에서는 실행 정책을 인자로 줄 수 있음. reduce 함수와 마찬가지로 실행 정책이 intel CPU 에서는 지원하지 않음.

  • 주어진 범위가 하나일 경우, UnaryOp unary_op 에 넘긴 함수로 각 원소를 변환시킨 후, BinaryOp binary_op 에 넘긴 함수로 모든 원소들을 축약함.

// since C++17 until C++20
template<class InputIt1, class InputIt2, class T>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);

template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class InputIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(InputIt first, InputIt last,
                   T init, BinaryOp binop, UnaryOp unary_op);

// since C++20
template<class InputIt1, class InputIt2, class T>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);

template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                             T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class InputIt, class T, class BinaryOp, class UnaryOp>
constexpr T transform_reduce(InputIt first, InputIt last,
                             T init, BinaryOp binop, UnaryOp unary_op);

// since C++17
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init);

template<class ExecutionPolicy,
         class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);

template<class ExecutionPolicy,class ForwardIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt first, ForwardIt last,
                   T init, BinaryOp binary_op, UnaryOp unary_op);

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

int main() {
    vector<double> xvalues(10007, 1.0), yvalues(10007, 1.0);

    double result = transform_reduce(
        execution::par,
        xvalues.begin(), xvalues.end(),
        yvalues.begin(), 0.0
    );
    cout << result << endl;

    result = transform_reduce(
        execution::par,
        xvalues.begin(), xvalues.end(), 1.0,
        plus<>(), [](double x) { return x * 2.0; }
    );
    cout << result << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
10007
20015 <--- 1.0 + 2.0 * 10007
 */

• transform_exclusive_scan 각 원소들을 주어진 함수로 변환시킨 후, exclusive_scan을 적용. (C++17부터 지원)

• transform_inclusive_scan 각 원소들을 주어진 함수로 변환시킨 후, inclusive_scan을 적용. (C++17부터 지원)

// since C++17 until C++20
template< class InputIt, class OutputIt, class T, 
          class BinaryOperation, class UnaryOperation>
OutputIt transform_exclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, T init,
                                   BinaryOperation binary_op,
                                   UnaryOperation unary_op);

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op,
                                   UnaryOperation unary_op );

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op, UnaryOperation unary_op,
                                   T init );

// since C++20
template< class InputIt, class OutputIt, class T, 
          class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_exclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             T init, BinaryOperation binary_op,
                                             UnaryOperation unary_op);

template< class InputIt, class OutputIt, class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op );

template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op,
                                             T init );

// since C++17
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first, T init,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op );

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation, class T >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first,
                                     BinaryOperation binary_op,
                                     UnaryOperation unary_op,
                                     T init );

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

int main() {
    vector data {3, 1, 4, 1, 5, 9, 2, 6};

    auto times_10 = [](int x) { return x * 10; };

    cout << "10 times exclusive sum: ";
    transform_exclusive_scan(data.begin(), data.end(),
                             ostream_iterator<int>(cout, " "), 0,
                             plus<int>{}, times_10);
    cout << endl;

    cout << "10 times inclusive sum: ";
    transform_inclusive_scan(data.begin(), data.end(),
                             ostream_iterator<int>(cout, " "),
                             plus<int>{}, times_10);
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++17
$ ./a.out
10 times exclusive sum: 0 30 40 80 90 140 230 250
10 times inclusive sum: 30 40 80 90 140 230 250 310
 */

순열 알고리즘 (Permutation Algorithm)

• is_permutation 두 컨테이너의 원소들이 (순서 상관없이) 일치하면 true, 그렇지 않으면 false를 반환.

  • 두번째가 첫번째의 순열이면 true.

// since C++11 until C++20
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, BinaryPredicate p );

// since C++20
template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, BinaryPredicate p );

template< class ForwardIt1, class ForwardIt2 >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, ForwardIt2 last2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                               ForwardIt2 first2, ForwardIt2 last2,
                               BinaryPredicate p );

// since C++14 until C++20
template< class ForwardIt1, class ForwardIt2 >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2 );

template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
bool is_permutation( ForwardIt1 first1, ForwardIt1 last1,
                     ForwardIt2 first2, ForwardIt2 last2,
                     BinaryPredicate p );

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

template<typename Os, typename V>
Os& operator<< (Os& os, V const& v) {
    os << "{ ";
    for (auto const& e : v) os << e << ' ';
    return os << "}";
}

int main() {
    static constexpr auto v1 = {1,2,3,4,5};
    static constexpr auto v2 = {3,5,4,1,2};
    static constexpr auto v3 = {3,5,4,1,1};

    cout << v2 << " is a permutation of " << v1 << ": " << boolalpha
         << is_permutation(v1.begin(), v1.end(), v2.begin()) << endl
         << v3 << " is a permutation of " << v1 << ": " << boolalpha
         << is_permutation(v1.begin(), v1.end(), v3.begin()) << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++14
$ ./a.out
{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false
 */

• next_permutation 주어진 범위 내 원소들을 다음 순서로 섞은 뒤 true 반환, 다음 순서가 없으면 false 반환.

  • 사전순으로 정렬되었다고 가정하고, 다음 순서는 사전순으로 다음에 오는 것을 의미.

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

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

template< class BidirIt, class Compare >
bool next_permutation( BidirIt first, BidirIt last, Compare comp );

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

template< class BidirIt, class Compare >
constexpr bool next_permutation( BidirIt first, BidirIt last, Compare comp );

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

int main() {
    string s = "aba";
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    } while(next_permutation(s.begin(), s.end()));
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
aab
aba
baa
 */

• prev_permutation 주어진 범위 내 원소들을 이전 순서로 섞고 true 반환, 이전 순서가 없으면 false 반환.

  • 이전 순서가 없다는 것은 원소들이 사전순으로 정렬되어 있다는 의미.

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

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

template< class BidirIt, class Compare >
bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

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

template< class BidirIt, class Compare >
constexpr bool prev_permutation( BidirIt first, BidirIt last, Compare comp );

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

int main() {
    string s = "abcd";
    sort(s.begin(), s.end(), greater<char>());
    do {
        cout << s << endl;
    } while(prev_permutation(s.begin(), s.end()));
    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
dcba
dcab
dbca
dbac
dacb
dabc
cdba
cdab
cbda
cbad
cadb
cabd
bdca
bdac
bcda
bcad
badc
bacd
adcb
adbc
acdb
acbd
abdc
abcd
 */

비교 알고리즘 (Comparison Algorithm)

• equal 두 범위 내 원소가 일치하면 true, 그렇지 않으면 false 반환.

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

template< class InputIt1, class InputIt2, class BinaryPredicate >
bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPredicate p );

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

template< class InputIt1, class InputIt2, class BinaryPredicate >
constexpr bool equal( InputIt1 first1, InputIt1 last1, InputIt2 first2,
                      BinaryPredicate p );

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

template< class InputIt1, class InputIt2, class BinaryPredicate >
bool equal( InputIt1 first1, InputIt1 last1, 
            InputIt2 first2, InputIt2 last2,
            BinaryPredicate p );

template< class InputIt1, class InputIt2, class BinaryPredicate >
constexpr bool equal( InputIt1 first1, InputIt1 last1, 
                      InputIt2 first2, InputIt2 last2,
                      BinaryPredicate p );

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

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, 
            ForwardIt2 first2, BinaryPredicate p );

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

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate >
bool equal( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, 
            ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );

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

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

bool is_palindrome(const string& s) {
    return equal(s.begin(), s.begin() + s.size()/2, s.rbegin());
}

void test(const string& s) {
    cout << "\"" << s << "\" "
         << (is_palindrome(s) ? "is" : "is not")
         << " a palindrome" << endl;
}

int main() {
    test("radar");
    test("hello");
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
"radar" is a palindrome
"hello" is not a palindrome
 */

• lexicographical_compare 첫번째 컨테이너가 두번째와 사전순으로 같거나 두번째보다 앞에 오면 true, 그렇지 않으면 false를 반환.

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

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

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

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

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

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

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

int main() {
    vector<char> v1 {'a', 'b', 'c', 'd'};
    vector<char> v2 {'a', 'b', 'c', 'd'};

    mt19937 g{random_device{}()};
    while (!lexicographical_compare(v1.begin(), v1.end(),
                                    v2.begin(), v2.end()))
    {
        for (auto c : v1) cout << c << ' ';
        cout << ">= ";
        for (auto c : v2) cout << c << ' ';
        cout << endl;

        shuffle(v1.begin(), v1.end(), g);
        shuffle(v2.begin(), v2.end(), g);
    }

    for (auto c : v1) cout << c << ' ';
    cout << "< ";
    for (auto c : v2) cout << c << ' ';
    cout << endl;

    return 0;
}

/*
$ g++ test.cpp -std=c++11
$ ./a.out
a b c d >= a b c d
b d c a >= a d b c
c a d b >= a c d b
c a d b >= b a d c
b c a d < c d a b
$ ./a.out
a b c d >= a b c d
a c d b < c d b a
 */