Почему для std::max_element требуется ForwardIterator?

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

Насколько я понимаю, ForwardIterator уточняет InputIterator, указывая, что вы можете использовать ForwardIterator для повторения одного и того же диапазона несколько раз. Следовательно, многопроходные алгоритмы требуют ForwardIterators.

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


c++ max iterator stl stl-algorithm
person HighCommander4    schedule 17.09.2012    source источник

Ответы (1)


arrow_upward
19
arrow_downward

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

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

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

По сути, диапазон одного прохода — это диапазон, который «исчезает» при прохождении через него, и std::max_element нужен диапазон, который остается, чтобы вернуть итератор (возможно) в его середину.

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

person R. Martinho Fernandes    schedule 17.09.2012
comment
Значит, нельзя разыменовывать InputIterator несколько раз? Или нельзя разыменовывать InputIterator после того, как его копия была увеличена? - person HighCommander4; 17.09.2012