std::minmax_element

Объявлен в заголовочном файле `<algorithm>`
template< class ForwardIt > std::pair<ForwardIt, ForwardIt> minmax_element( ForwardIt first, ForwardIt last );	(1)	(начиная с C++11) (constexpr начиная с C++17)
template< class ExecutionPolicy, class ForwardIt > std::pair<ForwardIt, ForwardIt> minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(начиная с C++17)
template< class ForwardIt, class Compare > std::pair<ForwardIt, ForwardIt> minmax_element( ForwardIt first, ForwardIt last, Compare comp );	(3)	(начиная с C++11) (constexpr начиная с C++17)
template< class ExecutionPolicy, class ForwardIt, class Compare > std::pair<ForwardIt, ForwardIt> minmax_element( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp );	(4)	(начиная с C++17)

Находит наименьший и наибольший элементы в диапазоне [first, last).

1) Элементы сравниваются с помощью operator<(до C++20)std::less{}(начиная с C++20).

3) Элементы сравниваются с помощью функции сравнения comp.

2,4) То же, что и (1,3), но выполняется в соответствии с policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first, last	-	пара итераторов, определяющих диапазон проверяемых элементов
policy	-	используемая политика выполнения
cmp	-	объект-функция сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const&`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` не допускается, как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа ForwardIt можно было разыменовать и затем неявно преобразовать в каждый из этих типов.
Требования к типам
-`ForwardIt` должен соответствовать требованиям LegacyForwardIterator.

Возвращаемое значение

пара, состоящая из итератора на наименьший элемент в качестве первого элемента и итератора на наибольший элемент в качестве второго. Возвращает std::make_pair(first, first), если диапазон пуст. Если несколько элементов эквивалентны наименьшему элементу, возвращается итератор на первый из них. Если несколько элементов эквивалентны наибольшему элементу, возвращается итератор на последний из них.

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1,2) Не более \(\scriptsize \max(\left\lfloor \frac{3}{2}(N-1) \right\rfloor, 0)\)max(⌊3/2(N-1)⌋,0) сравнений с помощью operator<(до C++20)std::less{}(начиная с C++20).

3,4) Не более \(\scriptsize \max(\left\lfloor \frac{3}{2}(N-1) \right\rfloor, 0)\)max(⌊3/2(N-1)⌋,0) вызовов функции сравнения comp.

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, приводит к исключению и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любого другого ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Возможная реализация

minmax_element
template<class ForwardIt> std::pair<ForwardIt, ForwardIt> minmax_element(ForwardIt first, ForwardIt last) { using value_type = typename std::iterator_traits<ForwardIt>::value_type; return std::minmax_element(first, last, std::less<value_type>()); }
minmax_element
template<class ForwardIt, class Compare> std::pair<ForwardIt, ForwardIt> minmax_element(ForwardIt first, ForwardIt last, Compare comp) { auto min = first, max = first; if (first == last \|\| ++first == last) return {min, max}; if (comp(first, min)) min = first; else max = first; while (++first != last) { auto i = first; if (++first == last) { if (comp(i, min)) min = i; else if (!(comp(i, max))) max = i; break; } else { if (comp(first, i)) { if (comp(first, min)) min = first; if (!(comp(i, max))) max = i; } else { if (comp(i, min)) min = i; if (!(comp(first, max))) max = first; } } } return {min, max}; }

minmax_element

template<class ForwardIt>
std::pair<ForwardIt, ForwardIt>
    minmax_element(ForwardIt first, ForwardIt last)
{
    using value_type = typename std::iterator_traits<ForwardIt>::value_type;
    return std::minmax_element(first, last, std::less<value_type>());
}

minmax_element

template<class ForwardIt, class Compare>
std::pair<ForwardIt, ForwardIt>
    minmax_element(ForwardIt first, ForwardIt last, Compare comp)
{
    auto min = first, max = first;
    
    if (first == last || ++first == last)
        return {min, max};
    
    if (comp(*first, *min))
        min = first;
    else
        max = first;
    
    while (++first != last)
    {
        auto i = first;
        if (++first == last)
        {
            if (comp(*i, *min))
                min = i;
            else if (!(comp(*i, *max)))
                max = i;
            break;
        }
        else
        {
            if (comp(*first, *i))
            {
                if (comp(*first, *min))
                    min = first;
                if (!(comp(*i, *max)))
                    max = i;
            }
            else
            {
                if (comp(*i, *min))
                    min = i;
                if (!(comp(*first, *max)))
                    max = first;
            }
        }
    }
    return {min, max};
}

Примечания

Этот алгоритм отличается от std::make_pair(std::min_element(), std::max_element()) не только эффективностью, но и тем, что он находит последний наибольший элемент, тогда как std::max_element находит первый наибольший элемент.

Пример

#include <algorithm>
#include <iostream>
 
int main()
{
    const auto v = {3, 9, 1, 4, 2, 5, 9};
    const auto [min, max] = std::minmax_element(begin(v), end(v));

    std::cout << "min = " << *min << ", max = " << *max << '\n';
}

Вывод:

min = 1, max = 9

См. также

min_element	возвращает наименьший элемент в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::min_element (C++20)
max_element	возвращает наибольший элемент в диапазоне (шаблон функции и функциональный объект алгоритма)
ranges::max_element (C++20)
ranges::minmax_element (C++20)	возвращает наименьший и наибольший элементы в диапазоне (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/minmax_element