c++ - 为什么我需要一个前向迭代器来实现我定制的 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是可用于多 channel 算法的最基本类型的迭代器，因为它保证您可以多次迭代一个范围。

迭代器是可变的还是不可变的(即，您是否可以修改其类型的迭代器所引用的元素)与迭代器的类别无关:a ForwardIterator可能是不可变的。例如，任何迭代器类别的 const 迭代器都是不可变的(或者，对于具体示例，C++0x 中的 std::forward_list<int>::const_iterator 是一个不可变的前向迭代器)。