std::minmax( ) 算法

自 C++14 起

// (1)
template< class T >
constexpr std::pair<const T&, const T&> minmax( const T& a, const T& b );

// (2)
template< class T, class Compare >
constexpr std::pair<const T&, const T&> minmax( const T& a, const T& b,
                                                Compare comp );

// (3)
template< class T >
constexpr std::pair<T, T> minmax( std::initializer_list<T> ilist);

// (4)
template< class T, class Compare >
constexpr std::pair<T, T> minmax( std::initializer_list<T> ilist, Compare comp );

自 C++11 起

// (1)
template< class T >
std::pair<const T&, const T&> minmax( const T& a, const T& b );

// (2)
template< class T, class Compare >
std::pair<const T&, const T&> minmax( const T& a, const T& b,
                                      Compare comp );

// (3)
template< class T >
std::pair<T, T> minmax( std::initializer_list<T> ilist);

// (4)
template< class T, class Compare >
std::pair<T, T> minmax( std::initializer_list<T> ilist, Compare comp );

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

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

  • (1) 使用 operator<。
  • (2) 使用给定的比较函数 comp。

• (3 - 4) 返回初始化列表 ilist 中最小和最大的值。

  • (3) 使用 operator<。
  • (4) 使用给定的比较函数 comp。

参数

a b	要比较的值。
ilist	包含要比较值的初始化列表。
cmp	比较函数对象（即满足 Compare 要求的对象），如果 a 小于 b 则返回 true。比较函数的签名应等效于以下内容 bool cmp(const Type1 &a, const Type2 &b); 虽然签名不需要有 const&，但函数不得修改传递给它的对象，并且必须能够接受类型为（可能是 const）Type1 和 Type2 的所有值，无论值类别如何（因此，不允许使用 Type1&，也不允许使用 Type1，除非对于 Type1 移动等效于复制 （自 C++11 起））。 Type1 和 Type2 的类型必须使得 T 类型的对象可以隐式转换为它们两者。

类型要求

• (1, 3):

  T	LessThanComparable

• (3 - 4):

  T	CopyConstructible

返回值

• (1 - 2)

  • 如果 a < b 或 a == b，返回 std::pair<const T&, const T&>(a, b) 的结果
  • 否则，返回 std::pair<const T&, const T&>(b, a)。

• (3 - 4) 一个 pair，其中 ilist 中最小的值作为第一个元素，最大的值作为第二个元素。
  如果多个元素等效于最小值，则返回最左边的那个元素。
  如果多个元素等效于最大值，则返回最右边的那个元素。

复杂度

• (1 - 2) 恰好一次比较。
• (3 - 4) 最多 ilist.size() * 3 / 2 次比较。

异常

(无)

可能的实现

minmax (1)

template<class T>
constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b)
{
    return (b < a) ? std::pair<const T&, const T&>(b, a)
                   : std::pair<const T&, const T&>(a, b);
}

minmax (2)

template<class T, class Compare>
constexpr std::pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp)
{
    return comp(b, a) ? std::pair<const T&, const T&>(b, a)
                      : std::pair<const T&, const T&>(a, b);
}

minmax (3)

template<class T>
constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist)
{
  auto p = std::minmax_element(ilist.begin(), ilist.end());
  return std::pair(*p.first, *p.second);
}

minmax (4)

template<class T, class Compare>
constexpr std::pair<T, T> minmax(std::initializer_list<T> ilist, Compare comp)
{
  auto p = std::minmax_element(ilist.begin(), ilist.end(), comp);
  return std::pair(*p.first, *p.second);
}

备注

未定义行为

对于重载 (1 - 2)，如果其中一个参数是临时变量，则返回的引用在包含对 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 <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v {3, 1, 4, 1, 5, 9, 2, 6};
    std::srand(std::time(0));
    std::pair<int, int> bounds = std::minmax(std::rand() % v.size(),
                                             std::rand() % v.size());

    std::cout << "v[" << bounds.first << "," << bounds.second << "]: ";
    for (int i = bounds.first; i < bounds.second; ++i)
        std::cout << v[i] << ' ';
    std::cout << '\n';
}

可能输出

v[2,7]: 4 1 5 9 2