C++ STL中max_element和minmax_element的行为差异

Question

在C++中max_element,如果有多个元素是最大的,它将返回第一个这样的元素.而minmax_element(C++ 11以上)返回最后一个max元素.

这种行为的标准是否有原因？

来自cplusplus.com

如果多个等效元素具有最大值,则第二个迭代器指向最后一个这样的元素.

比较是使用operator <作为第一个版本,或comp作为第二个版本; 如果没有其他元素没有比它少,则元素是最大的.如果多个元素满足此条件,则迭代器返回指向第一个这样的元素.

Answer 1

Boost 的库文档包括其基本原理

当尝试使用（Cormen、Leiserson、Rivest：“算法简介”，第 9.1 节）中提出的过程设计 minmax_element 时，定义问题就会出现。如果 [first,last) 有 n 个元素，则应该可以仅使用 3n/2 次比较来导出算法，但如果尝试编写一个名为 first_min_first_max_element() 的函数，该函数在 a 中返回 std::min_element 和 std::max_element对，简单的实现不起作用。问题相当微妙地与相等的元素有关：我不得不思考一段时间才能找到一种方法，只对每对执行三次比较并返回第一个最小和第一个最大元素。很长一段时间以来，在最坏的情况下，任何这样做的尝试似乎都会消耗每对四次比较。该实施实现了三个目标。

不可能（甚至不希望）更改 max_element 的含义，但提供一个名为 minmax_element 的函数仍然是有益的，该函数返回一对 min_element 和 max_element。尽管调用 min_element 和 max_element 很容易，但这会执行 2(n-1) 次比较，并且需要对输入进行两次传递。相反，minmax_element 将执行较少的比较并对输入执行一次传递。当迭代器类型不是原始指针，甚至只是 InputIterator 概念的一个模型时，节省的空间可能很大（尽管在这种情况下，必须更改接口，因为返回类型无法复制，因此可以例如返回一个值）。