std::ranges::minmax() 算法

自 C++20 起

简化

// (1)
constexpr ranges::minmax_result<const T&>
    minmax( const T& a, const T& b, Comp comp = {}, Proj proj = {} );

// (2)
constexpr ranges::minmax_result<T>
    minmax( std::initializer_list<T> r, Comp comp = {}, Proj proj = {} );

// (3)
constexpr ranges::minmax_result<ranges::range_value_t<R>>
    minmax( R&& r, Comp comp = {}, Proj proj = {} );

参数类型是泛型的，并具有以下约束

• T - （无）
• Proj - (无)
• R - ranges::input_range
• Comp:
  • (1 - 2) - std::indirect_strict_weak_order<std::projected<const T*, Proj>>
  • (3) - std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>>

Proj 和 Comp 模板参数对于所有重载都具有以下默认类型：std::identity、ranges::less。

此外，每个重载都有以下约束

• (3) - std::indirectly_copyable_storable<ranges::iterator_t<R>, ranges::range_value_t<R>*>

详细

// (1)
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 = {} );

// (2)
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 = {} );

// (3)
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 = {} );

辅助类型定义如下：

template< class T >
using minmax_result = ranges::min_max_result<T>;

返回给定投影值中的最小和最大值。

• (1) 返回 a 和 b 中较小和较大的引用。

• (2) 返回初始化列表 r 中值的最小和最大值。

• (3) 返回范围 r 中值的最小和最大值。

本页描述的函数类实体是niebloids。

参数

a b	要比较的值。
r	一个非空的值范围，用于比较。
comp	应用于投影元素的比较。
proj	应用于元素的投影。

返回值

• (1)

  • 如果根据投影值 a 小于 b，则为 { b, a }。
  • 否则为 { a, b }。

• (2 - 3) { s, l }，其中 s 和 l 分别是 r 中根据其投影值得到的最小和最大值。
  如果多个值与最小和最大值等效，则返回最左边的最小值和最右边的最大值。

  未定义行为

  如果范围为空（由 ranges::distance(r) 确定），则行为未定义。

复杂度

• (1) 恰好一次比较和两次投影应用。
• (2 - 3) 最多 3 / 2 * ranges::distance(r) 次比较和两倍的投影。

异常

(无)

可能的实现

minmax(1) 和 minmax(2)

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 result = ranges::minmax_element(r, std::ref(comp), std::ref(proj));
        return {std::move(*result.min), std::move(*result.max)};
    }
};

inline constexpr minmax_fn minmax;

备注

未定义行为

对于重载 (1)，如果其中一个参数是临时变量，则返回的引用在包含对 minmax 的调用的完整表达式结束时将成为悬空引用。

int n = 1;
auto p = std::minmax(n, n + 1);
int m = p.first; // ok
int x = p.second; // undefined behavior

// Note that structured bindings have the same issue
auto [mm, xx] = std::minmax(n, n + 1);
xx; // undefined behavior

示例

Main.cpp

#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