Move Fast

비교 알고리즘 (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
 */