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

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

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

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

11

Решение

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

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

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

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

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

17

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]