Почему std:: max_element требует ForwardIterator?

Алгоритм стандартной библиотеки С++ max_element требует, чтобы итераторы передавались как входы в модель ForwardIterator.

Я понимаю, что ForwardIterator уточняет InputIterator, указав, что вы можете использовать ForwardIterator для повторного итерации одного и того же диапазона несколько раз. Поэтому для многопроходных алгоритмов требуется ForwardIterator s.

Однако max_element не является многопроходным алгоритмом - достаточно выполнить итерацию по диапазону один раз, чтобы определить его максимальный элемент. Итак, почему max_element нужны дополнительные возможности ForwardIterator?

Ответ 1

std::max_element возвращает итератор в максимальный элемент. Если вы предоставите один диапазон прохода, этот итератор больше не будет действителен, так как алгоритм должен выполнить полный проход в диапазоне.

В одном диапазоне прохождения вы не сможете сохранить полезный итератор с предыдущим значением. Это связано с пост-условием на ++r, приведенным в таблице 107 в стандарте:

post: любые копии предыдущего значения r больше не требуются, чтобы быть различимыми или находиться в домене ==.

В принципе, диапазон одного прохода - это диапазон, который "исчезает" при прохождении через него, а std::max_element нужен диапазон, который торчит вокруг, чтобы вернуть итератор (возможно) в середину.

Можно написать алгоритм для вычисления максимума, который вернул фактическое максимальное значение вместо итератора, но для этого потребовалось бы скопировать значения, чтобы вернуть их по значению. Movable не будет достаточно, так как перемещение предотвратит использование константных итераторов. И возврат по ссылке тоже не был бы вариантом, так как это означало, что диапазон фактически застрял.