为什么我需要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 是最基本的迭代器类型,可用于多次通过算法,因为它可以保证您可以多次迭代一个范围.

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