Move Fast

수치 알고리즘 (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
 */

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

• max 최대 원소 반환.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

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

• min 최소 원소 반환.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return 0;
}

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

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