Why do I need a Forward Iterator to implement my customized std::search

Question

I am studying the book "Accelerated C++" from Koenig & Moo.

Exercise 8-2 ask me to implement on my own some templatized functions from <algorithm> and <numeric>, and to specify what kind of iterator does my implementation require.

When trying to implement std::search, I determined that I need only "input" iterators.

Here is my code so far:

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;
}

However, looking at the implementation of std::search installed with my compiler, I can see that they use "forward" iterators, but I cannot understand why, because there is no need to write, only to read, and input iterators meet the requirement.

Can anybody here help me to understand this, please? Why would I need to use "forward" iterators to implement std::search?

Thanks in advance.

Answer 1

With an input iterator, you are only allowed to pass through the range once. That is, once you've dereferenced and incremented the iterator, you can't go back and dereference it again.

This class of iterators is quite useful for many things. For example, if you are reading from a stream of some kind, once you've read something from the stream you can't go back and read that thing again; you can't store off a copy of the iterator, continue iterating with the original iterator, then go back and start iterating with the copy and assume you'll get the same results.

In your algorithm, you pass through the range more than once (see the comments in your source here):

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 is the most basic type of iterator that can be used for multi-pass algorithms because it guarantees that you can iterate over a range multiple times.

Whether an iterator is mutable or immutable (that is, whether you can modify the element to which an iterator of its type refers) is independent of the category of the iterator: a ForwardIterator may be immutable. For example, const iterators of any iterator category are immutable (or, for a concrete example, std::forward_list<int>::const_iterator in C++0x is an immutable forward iterator).

Answer 2

I think your conclusion that you need only input iterators is incorrect. With an input iterator, you're only allowed to de-reference a particular iterator value once (e.g., when you're reading from standard input, two reads will get two separate items, not two references to the same item).

Although you've (sort of) hidden it by using copies of the iterators, you still look at the same item(s) twice:

// 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) {

Your code depends on dereferencing the same iterators (or, more accurately, different iterators with the same values) twice, so it won't work with input iterators.