为什么我需要一个Forward Iterator来实现我定制的std::search

Question

我正在研究Koenig & Moo的书"Accelerated C++“。

练习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实现，我可以看到它们使用“向前”迭代器，但我不明白为什么，因为不需要写，只需要读，输入迭代器满足要求。

在座的各位能帮我理解一下吗？为什么我需要使用“转发”迭代器来实现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是可用于多遍算法的最基本类型的迭代器，因为它保证您可以在一个范围内多次迭代。

迭代器是可变的还是不可变的(也就是说，您是否可以修改其类型的迭代器引用的元素)与迭代器的类别无关：ForwardIterator可能是不可变的。例如，任何迭代器类别的常量迭代器都是不可变的(或者，举个具体的例子，C++0x中的std::forward_list<int>::const_iterator是一个不可变的正向迭代器)。

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

您的代码依赖于两次取消引用相同的迭代器(或者，更准确地说，是具有相同值的不同迭代器)，因此它不能与输入迭代器一起工作。