std::ranges::minmax_element, std::ranges::minmax_element_result

Определено в заголовке `<algorithm>`
Подпись вызова
template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<I, Proj>> Comp = ranges::less > constexpr minmax_element_result<I> minmax_element( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(с C++20)
template< ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr minmax_element_result<ranges::borrowed_iterator_t<R>> minmax_element( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(с C++20)
Вспомогательные типы
template< class I > using minmax_element_result = ranges::min_max_result<I>;	(3)	(с C++20)

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

2) То же, что и (1), но использует r в качестве исходного диапазона, как если бы ranges::begin(r) использовался как first и ranges::end(r) как last.

Функциональные сущности, описанные на этой странице, являются niebloids, то есть:

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

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

Параметры

first, last	-	пара итератор-граничник, определяющая диапазон для проверки
r	-	диапазон для проверки
comp	-	сравнение для применения к спроектированным элементам
proj	-	проекция для применения к элементам.

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

Объект, состоящий из итератора на наименьший элемент в качестве первого элемента и итератора на наибольший элемент в качестве второго. Возвращает {first, first} если диапазон пустой. Если несколько элементов эквивалентны наименьшему элементу, возвращается итератор на первый такой элемент. Если несколько элементов эквивалентны наибольшему элементу, возвращается итератор на последний такой элемент.

Сложность

Максимально max(floor((3 / 2) * (N − 1)), 0) применений сравнения и вдвое больше применений проекции, где N = ranges::distance(first, last).

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

struct minmax_element_fn
{
  template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
           std::indirect_strict_weak_order<std::projected<I, Proj>> Comp = ranges::less>
  constexpr ranges::minmax_element_result<I>
      operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
  {
    auto min = first, max = first;
 
    if (first == last || ++first == last) {
      return {min, max};
    }
 
    if (std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, *min))) {
      min = first;
    } else {
      max = first;
    }
 
    while (++first != last) {
      auto i = first;
      if (++first == last) {
        if (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *min))) {
          min = i;
        }
        else if (!(std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *max)))) {
          max = i;
        }
        break;
      } else {
        if (std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, *i))) {
          if (std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, *min))) {
            min = first;
          }
          if (!(std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *max)))) {
            max = i;
          }
        } else {
          if (std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *min))) {
            min = i;
          }
          if (!(std::invoke(comp, std::invoke(proj, *first), std::invoke(proj, *max)))) {
            max = first;
          }
        }
      }
    }
    return {min, max};
  }
 
  template<ranges::forward_range R, class Proj = std::identity,
           std::indirect_strict_weak_order<
               std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
  constexpr ranges::minmax_element_result<ranges::borrowed_iterator_t<R>>
      operator()(R&& r, Comp comp = {}, Proj proj = {}) const
  {
    return (*this)(ranges::begin(r), ranges::end(r), std::ref(comp), std::ref(proj));
  }
};
 
inline constexpr minmax_element_fn minmax_element;

Пример

#include <algorithm>
#include <iostream>
#include <iterator>
namespace rng = std::ranges;
 
int main()
{
    const auto v = {3, 9, 1, 4, 1, 2, 5, 9};
    const auto [min, max] = rng::minmax_element(v);
    std::cout
        << "min = " << *min << ", at [" << rng::distance(v.begin(), min) << "]\n"
        << "max = " << *max << ", at [" << rng::distance(v.begin(), max) << "]\n";
}

Вывод:

min = 1, at [2]
max = 9, at [7]

См. также

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

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