Why does std::max_element require a ForwardIterator?

Question

The C++ standard library's max_element algorithm requires the iterators passed as inputs to model ForwardIterator.

My understanding is that ForwardIterator refines InputIterator by specifying that you can use a ForwardIterator to iterate over the same range multiple times. Therefore, multi-pass algorithms require ForwardIterators.

However, max_element is not a multi-pass algorithm - it is sufficient to iterate over a range once to determine its maximum element. So why does max_element need the additional capabilities of ForwardIterator?

Answer 1

std::max_element returns an iterator to the maximum element. If you provide a single pass range, that iterator will not be valid any more, since the algorithm has to perform a full pass on the range.

On a single pass range, you cannot keep an usable iterator to a previous value. This is due to a post-condition on ++r given in Table 107 in the standard:

post: any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==.

Basically, a single pass range is a range that "disappears" as you pass through it, and std::max_element needs a range that sticks around in order to return an iterator to (possibly) the middle of it.

One could write an algorithm to compute the maximum that returned the actual maximum value instead of an iterator, but that would require the values to be copyable in order to return it by value. Movable would not be enough as moving would prevent the use of const iterators. And returning by reference would not be an option either, as that would mean the range actually stuck around.