Можно ли использовать входные итераторы там, где ожидаются прямые итераторы?

Question

Насколько мне известно, иерархия категорий итераторов выглядит следующим образом:

Random access -> Bi-directional -> Forward -> Input
                                           -> Output

Правильно?

Я всегда думал, что существует правило, что, если алгоритм ожидает итератор определенного типа, вы можете предоставлять итераторы категорий вверх по цепочке, но не вниз. Итак, я читал этот ответ , где ildjarn предлагает предложил (затем исправил позже), используя std::ifstream с std::istream_iterator и std::search, чтобы найти данные в файле. Я собирался прокомментировать, что вы не можете этого сделать, потому что search ожидает итераторы Forward, а istream_iterator - итератор Input. Но чтобы убедиться, я попробовал это:

std::istringstream iss("Elephant hats for sale.");
std::istream_iterator<char> begin(iss), end;

std::string sub("hat");
auto i = std::search(begin, end, sub.begin(), sub.end());

Я не ожидал, что это скомпилируется, но это произошло. Тем не менее, результаты кажутся бесполезными, потому что, если я последую за этим следующим:

while(i != end)
{
    std::cout << *i;
    ++i;
}

Нет вывода. Итак, мой вопрос таков: мой компилятор по ошибке допустил мой вызов на search с использованием istream_iterator? Или нет правил, запрещающих подобные вещи?

Answer 1

Можно ли использовать входные итераторы там, где ожидаются прямые итераторы?

Нет.Разница между входным итератором и прямым итератором заключается в том, что входной итератор является «однопроходным» итератором, а прямой итератор является «многопроходным» итератором.

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

С прямым итератором вы можете выполнять итерацию последовательности любое количество раз, вы можете иметь несколько пригодных для использования копий итератора одновременно, вы можете использовать несколько итераторов в последовательностив то же время, и вы можете разыменовать итератор столько раз, сколько захотите, прежде чем снова его продвигать.

Итак, мой вопрос таков: мой компилятор по ошибке допустил мой вызовпоиск с использованием istream_iterator?

Нет правила, согласно которому компилятор должен отклонять код.

Правило состоит в том, что вы должны обязательно передать правильный тип итератора, требуемый функцией.Иногда, если вы передадите неверный тип итератора, вы получите ошибку компиляции.Иногда программа компилируется, но не работает правильно.Иногда все будет работать правильно.Результаты не определены, если вы нарушаете требования вызова функции.

---

Общие алгоритмы обычно накладывают требования на параметры своего типа, предполагая, что представленные аргументы типа действительно соответствуют требованиям.Так, например, алгоритм, который работает только с итераторами с произвольным доступом, будет «обеспечивать» это требование, выполняя некоторую операцию, которая работает только с итераторами с произвольным доступом (например, it + 1).Если итератор не поддерживает эту операцию (operator+(iterator, int) здесь), код не сможет скомпилироваться.

Проблема в том, что нет способа различить входные итераторы и прямые итераторы таким образом: вы можетеинкремент и разыменование их обоих;разница состоит в том, сколько раз вы можете выполнять каждую из этих операций, и в какой последовательности вы можете выполнять эти операции.Таким образом, алгоритм, подобный std::search, будет использовать *it и ++it, что будет прекрасно работать для входных итераторов, по крайней мере, если код будет компилироваться.

Теоретически алгоритм можетиспользуйте шаблон класса std::iterator_traits, чтобы определить, является ли итератор входным итератором или прямым итератором;Я не знаю, будет ли это разрешено стандартом языка C ++.Если бы библиотека сделала это, вы могли бы получить ошибку компиляции для своего кода, которая была бы лучше.