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

Question

在 C++ max_element 中，如果有多个元素是最大值，则返回第一个这样的元素。而 minmax_element(C++11 及更高版本)返回最后一个最大元素。

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

来自 cplusplus.com

If more than one equivalent element has the largest value, the second iterator points to the last of such elements.

The comparisons are performed using either operator< for the first version, or comp for the second; An element is the largest if no other element does not compare less than it. If more than one element fulfills this condition, the iterator returned points to the first of such elements.

Answer 1

Boost 的库文档包括 rationale

The definition problem surfaces when one tries to design a minmax_element, using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction to Algorithms", section 9.1). It should be possible to derive an algorithm using only 3n/2 comparisons if [first,last) has n elements, but if one tries to write a function called first_min_first_max_element() which returns both std::min_element and std::max_element in a pair, the trivial implementation does not work. The problem, rather subtly, is about equal elements: I had to think for a while to find a way to perform only three comparisons per pair and return the first min and first max elements. For a long time, it seemed any attempts at doing so would consume four comparisons per pair in the worst case. This implementation achieves three.

It is not possible (or even desirable) to change the meaning of max_element, but it is still beneficial to provide a function called minmax_element, which returns a pair of min_element and max_element. Although it is easy enough to call min_element and max_element, this performs 2(n-1) comparisons, and necessitates two passes over the input. In contrast, minmax_element will perform the fewer comparisons and perform a single pass over the input. The savings can be significant when the iterator type is not a raw pointer, or even is just a model of the InputIterator concept (although in that case the interface would have to be changed, as the return type could not be copied, so one could e.g. return a value).