std::ranges::minmax, std::ranges::minmax_result

Определён в заголовке `<algorithm>`
Сигнатура вызова
template< class T, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<const T*, Proj>> Comp = ranges::less > constexpr ranges::minmax_result<const T&> minmax( const T& a, const T& b, Comp comp = {}, Proj proj = {} );	(1)	(с C++20)
template< std::copyable T, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<const T*, Proj>> Comp = ranges::less > constexpr ranges::minmax_result<T> minmax( std::initializer_list<T> r, Comp comp = {}, Proj proj = {} );	(2)	(с C++20)
template< ranges::input_range R, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > requires std::indirectly_copyable_storable<ranges::iterator_t<R>, ranges::range_value_t<R>*> constexpr ranges::minmax_result<ranges::range_value_t<R>> minmax( R&& r, Comp comp = {}, Proj proj = {} );	(3)	(с C++20)
Вспомогательные типы
template< class T > using minmax_result = ranges::min_max_result<T>;	(4)	(с C++20)

Возвращает наименьшее и наибольшее из заданных спроецированных значений.

1) Возвращает ссылки на меньшее и большее из a и b.

2) Возвращает наименьшее и наибольшее значения из списка инициализаторов r.

3) Возвращает наименьшее и наибольшее значения из диапазона r.

Для перегрузок (2,3) поведение не определено, если диапазон пуст (что определяется с помощью ranges::distance(r)).

Функциональные объекты, описанные на этой странице, являются функциональными объектами алгоритмов (неформально называемыми niebloids), то есть:

При вызове любого из них нельзя указать явный список аргументов шаблона.
Ни один из них не виден для поиска с учётом аргументов.
Если любой из них найден с помощью обычного неквалифицированного поиска как имя слева от оператора вызова функции, поиск с учётом аргументов подавляется.

Параметры

a, b	-	значения для сравнения
r	-	непустой диапазон значений для сравнения
comp	-	сравнение, применяемое к спроецированным элементам
proj	-	проекция, применяемая к элементам

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

1) {b, a}, если согласно соответствующему спроецированному значению b меньше, чем a; в противном случае возвращает {a, b}.

2,3) {s, l}, где s и l — соответственно наименьшее и наибольшее значения в r согласно их спроецированным значениям. Если несколько значений эквивалентны наименьшему и наибольшему, возвращает самое левое наименьшее значение и самое правое наибольшее значение.

Сложность

1) Ровно одно сравнение и два применения проекции.

2,3) Не более 3 / 2 * ranges::distance(r) сравнений и вдвое больше применений проекции.

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

struct minmax_fn
{
    template<class T, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = ranges::less>
    constexpr ranges::minmax_result<const T&>
         operator()(const T& a, const T& b, Comp comp = {}, Proj proj = {}) const
    {
        if (std::invoke(comp, std::invoke(proj, b), std::invoke(proj, a)))
            return {b, a};
      
        return {a, b};
    }

    template<std::copyable T, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<const T*, Proj>> Comp = ranges::less>
    constexpr ranges::minmax_result<T>
        operator()(std::initializer_list<T> r, Comp comp = {}, Proj proj = {}) const
    {
        auto result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
        return {*result.min, *result.max};
    }

    template<ranges::input_range R, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
    requires std::indirectly_copyable_storable<ranges::iterator_t<R>,
                                               ranges::range_value_t<R>*>
    constexpr ranges::minmax_result<ranges::range_value_t<R>>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        auto first = ranges::begin(r);
        const auto last = ranges::end(r);

        auto min = static_cast<range_value_t<R>>(*first), max = min;
        while (++first != last) {
            auto x = static_cast<range_value_t<R>>(*first);
            if (++first == last) {
                if (std::invoke(comp, std::invoke(proj, x), std::invoke(proj, min)))
                    min = x;
                else if (!std::invoke(comp, std::invoke(proj, x), std::invoke(proj, max)))
                    max = x;

                break;
            }

            if (std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, x))) {
                if (std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, min)))
                    min = *first;
                if (!std::invoke(comp, std::invoke(proj, x), std::invoke(proj, max)))
                    max = x;
            } else {
                if (std::invoke(comp, std::invoke(proj, x), std::invoke(proj, min)))
                    min = x;
                if (!std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, max)))
                    max = *first;
            }
        }

        return {min, max};
    }
};

inline constexpr minmax_fn minmax;

Примечания

Для перегрузки (1), если один из параметров является временным объектом, возвращаемая ссылка становится висячей в конце полного выражения, содержащего вызов minmax:

int n = 1;
auto p = std::ranges::minmax(n, n + 1);
int m = p.min; // ok
int x = p.max; // undefined behavior
 
// Note that structured bindings have the same issue
auto [mm, xx] = std::ranges::minmax(n, n + 1);
xx; // undefined behavior

Пример

#include <algorithm>
#include <array>
#include <iostream>
#include <random>

int main()
{
    namespace ranges = std::ranges;

    constexpr std::array v{3, 1, 4, 1, 5, 9, 2, 6, 5};

    std::random_device rd;
    std::mt19937_64 generator(rd());
    std::uniform_int_distribution<> distribution(0, ranges::distance(v)); // [0..9]

    // auto bounds = ranges::minmax(distribution(generator), distribution(generator));
    // UB: dangling references: bounds.min and bounds.max have the type `const int&`.

    const int x1 = distribution(generator);
    const int x2 = distribution(generator);
    auto bounds = ranges::minmax(x1, x2); // OK: got references to lvalues x1 and x2

    std::cout << "v[" << bounds.min << ":" << bounds.max << "]: ";
    for (int i = bounds.min; i < bounds.max; ++i)
        std::cout << v[i] << ' ';
    std::cout << '\n';

    auto [min, max] = ranges::minmax(v);
    std::cout << "smallest: " << min << ", " << "largest: " << max << '\n';
}

Возможный вывод:

v[3:9]: 1 5 9 2 6 5 
smallest: 1, largest: 9

См. также

ranges::min (C++20)	возвращает меньшее из заданных значений (функциональный объект алгоритма)
ranges::max (C++20)	возвращает большее из заданных значений (функциональный объект алгоритма)
ranges::minmax_element (C++20)	возвращает наименьший и наибольший элементы диапазона (функциональный объект алгоритма)
ranges::clamp (C++20)	ограничивает значение заданными границами (функциональный объект алгоритма)
minmax (C++11)	возвращает меньшее и большее из двух элементов (шаблон функции)

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