Move Fast

최대, 최소 원소 탐색 알고리즘 (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
 */