std::ranges::max_element() algorithm

od C++20

Simplified

// (1)
constexpr I max_element( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
    max_element( R&& r, Comp comp = {}, Proj proj = {} );

The type of arguments are generic and have the following constraints:

• I - std::forward_iterator
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• Comp:
  • (1) - std::indirect_strict_weak_order<std::projected<I, Proj>>
  • (2) - std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>>
• Proj - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

Additionally, each overload has the following constraints:

• (1) - std::sortable<I, Comp, Proj>
• (2) - std::sortable<ranges::iterator_t<R>, Comp, Proj>

Detailed

// (1)
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 I max_element( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
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::borrowed_iterator_t<R>
    max_element( R&& r, Comp comp = {}, Proj proj = {} );

• (1) Finds the greatest element in the range [first; last).

• (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first last	The range to find the largest value in.
r	The range to find the largest value in.
comp	Comparison to apply to the projected elements.
proj	Projection to apply to the elements.

Return value

Iterator to the greatest element in the range [first; last).

If several elements in the range are equivalent to the greatest element, returns the iterator to the first such element.

Returns first if the range is empty.

Complexity

Given N as std::distance(first, last):

Exactly max(N - 1, 0) comparisons.

Exceptions

(none)

Possible implementation

max_element(1) and max_element(2)

struct max_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 I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        if (first == last)
            return last;

        auto largest = first;
        ++first;
        for (; first != last; ++first)
            if (std::invoke(comp, std::invoke(proj, *largest), std::invoke(proj, *first)))
                largest = first;
        return largest;
    }

    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::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 max_element_fn max_element;

Examples

Main.cpp

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {3, 1, -14, 1, 5, 9};

    namespace ranges = std::ranges;
    auto result = ranges::max_element(v.begin(), v.end());
    std::cout << "max element at: " << ranges::distance(v.begin(), result) << '\n';

    auto abs_compare = [](int a, int b) { return (std::abs(a) < std::abs(b)); };
    result = ranges::max_element(v, abs_compare);
    std::cout << "max element (absolute) at: " << ranges::distance(v.begin(), result) << '\n';
}

Output

max element at: 5
max element (absolute) at: 2