Почему InputIterators один проход?
От
24.2.3. Итераторы ввода [input.iterators]
3) […] Алгоритмы на входных итераторах никогда не должны пытаться пройти
через один и тот же итератор дважды. Это должны быть однопроходные алгоритмы. […]
Это IMO ограничивает некоторые довольно простые оптимизации (например, проход через контейнер один раз, чтобы увидеть, сколько элементов в нем есть) — увы, мотивация выходит за рамки вопроса.
Почему это требование?
Решение
Входные итераторы используются для итерации по диапазонам, которые не имеют материальной реализации (т. Е. Их элементы фактически не существуют где-то в памяти), например, байты из сетевого потока или последовательность случайных чисел из / dev / random. Рассмотрим последний пример: как только вы используете первое случайное число, вы не сможете получить его снова.
Прямые итераторы, с другой стороны, предоставляют доступ к диапазонам, которые либо имеют материальную реализацию (т. Е. Все их элементы действительно существуют где-то в памяти), либо могут быть легко пересчитаны †. По своей природе контейнеры обычно предоставляют прямые итераторы: сами контейнеры являются материализацией диапазона.
Диапазоны, определенные с помощью входных итераторов, иногда можно преобразовать в диапазон, определенный с помощью прямых итераторов, просто материализовав его: просто используйте один проход, чтобы скопировать весь диапазон в контейнер, а затем итерируйте в этом контейнере столько раз, сколько захотите. Очевидно, что это будет нежелательно во всех ситуациях, а иногда это даже невозможно: некоторые диапазоны, такие как байты из / dev / random, бесконечны и никогда не могут быть полностью реализованы.
Если алгоритм может быть записан за один проход, нет причин запрещать его использование с входными итераторами. Тем не менее, ничто не запрещает такому алгоритму использовать оптимизированную версию, которая выполняет несколько проходов, когда передаются прямые или лучшие итераторы.
† Например, диапазон всех четных чисел не должен материализовать все числа в контейнере, но можно легко начать заново с заданного итератора, так как возможно и дешево пересчитать числа снова.
Другие решения
Выбранное имя уже дает подсказку, почему: думать об итераторе как об итерациях входной поток такие как ввод с клавиатуры или сетевой поток. Нет способа дважды перебрать поток, отсюда и ограничение.
В ситуациях, когда требуется оптимизация, и мы не против повысить требования итератора, прямой итератор или что-то еще более мощное — естественный выбор.
Связанный вопрос: В чем разница между входными итераторами и итераторами только для чтения?