Зачем мне нужен прямой итератор для реализации моего настраиваемого std :: search

Question

Я изучаю книгу «Ускоренный C ++» от Koenig & Moo.

В упражнении 8-2 меня попросили самостоятельно реализовать некоторые шаблонизированные функции из <algorithm> и <numeric> и указать, чтосвоего рода итератор требует моей реализации.

Когда я пытался реализовать std::search, я решил, что мне нужны только «входные» итераторы.

Вот мой код:

template <class In1, class In2>
In1 search(In1 b, In1 e, In2 b2, In2 e2)
{
    if (b2 != e2) {
        while (b != e) {
            if (*b == *b2) {
                In1 bc = b;
                In2 b2c = b2;
                while (bc != e && b2c != e2 && *bc == *b2c) {
                    ++bc;
                    ++b2c;
                }
                if (b2c == e2)
                    return b;
            }
            ++b;
        }
    }
    return e;
}

Однако, глядя на реализацию std::search, установленную с моим компилятором, я вижу, что они используют итераторы "forward", но яне могу понять почему, потому что нет необходимости писать, только читать, и входные итераторы отвечают требованию.

Может ли кто-нибудь здесь помочь мне понять это, пожалуйста?Зачем мне использовать «прямые» итераторы для реализации std::search?

Answer 1

При использовании итератора ввода вам разрешено проходить через диапазон только один раз.То есть после разыменования и увеличения итератора вы не сможете вернуться и разыменовать его снова.

Этот класс итераторов весьма полезен для многих вещей.Например, если вы читаете из какого-то потока, как только вы прочитаете что-то из потока, вы не сможете вернуться и прочитать это снова;Вы не можете сохранить копию итератора, продолжить итерацию с исходным итератором, затем вернуться и начать итерацию с копией и предположить, что вы получите те же результаты.

В своем алгоритме вы передаетечерез диапазон более одного раза (см. комментарии в вашем источнике здесь):

template <class In1, class In2>
In1 search(In1 b, In1 e, In2 b2, In2 e2)
{
    if (b2 != e2) {
        while (b != e) {
            if (*b == *b2) {
                In1 bc = b;            // copy iterator b
                In2 b2c = b2;
                while (bc != e && b2c != e2 && *bc == *b2c) {
                    ++bc;              // increment the copy of iterator b
                    ++b2c;
                }
                if (b2c == e2)
                    return b;
            }
            ++b;                       // increment the original b
        }
    }
    return e;
}

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

Независимо от категории итератора, является ли итератор изменчивым или неизменным (то есть можно ли изменить элемент, к которому относится итератор его типа): a ForwardIterator может быть неизменным.Например, константные итераторы любой категории итераторов являются неизменяемыми (или, для конкретного примера, std::forward_list<int>::const_iterator в C ++ 0x является неизменяемым прямым итератором).

Answer 2

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

Хотя вы (вроде) скрыли его, используя копии итераторов, вы все равно смотрите на один и тот же элемент (ы) дважды:

// Look at *b and *b2:
        if (*b == *b2) {

            In1 bc = b;
            In2 b2c = b2;

// Now look at the same items again:
            while (bc != e && b2c != e2 && *bc == *b2c) {

Ваш код зависит от разыменования одних и тех же итераторов (или, точнее, разных итераторов с одинаковыми значениями) дважды, поэтому он не будет работать с входными итераторами.