为什么我需要一个Forward Iterator来实现我的自定义std :: search [英] Why do I need a Forward Iterator to implement my customized std::search

查看:127
本文介绍了为什么我需要一个Forward Iterator来实现我的自定义std :: search的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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



练习8-2要求我自行实现< algorithm> 的一些模板化函数< numeric> ,并指定我的实现需要什么样的迭代器。



code> std :: search ,我确定我只需要输入迭代器。



这里是我的代码到目前为止:

  template< class In1,In2> 
In1搜索(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 ::搜索与我的编译器一起安装,我可以看到他们使用forward迭代器,但我不明白为什么,因为没有必要写,只读和输入迭代器满足要求。 / p>

这里有人能帮我理解吗?为什么需要使用forward迭代器来实现 std :: search

解决方案

使用输入迭代器,您只能通过一次范围。也就是说,一旦你解除引用并增加了迭代器,你就不能回去再引用它。



这类迭代器对很多事情都非常有用。例如,如果你从某种流中读取,一旦你从流中读取了一些东西,你就不能回去再读那些东西;您不能存储迭代器的副本,继续使用原始迭代器迭代,然后返回并开始使用副本进行迭代,并假设您将获得相同的结果。



在您的算法中,您不止一次地传递该范围(请参阅您的来源中的评论):

 模板< class In1,class In2> 
In1搜索(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; //递增迭代器的副本b
++ b2c;
}
if(b2c == e2)
return b;
}
++ b; // increment the original b
}
}
return e;
}

ForwardIterator 最基本的迭代器类型,可以用于多遍算法,因为它保证您可以多次迭代一个范围。



迭代器是可变的还是不可变的也就是说,您是否可以修改其类型的迭代器引用的元素)独立于迭代器的类别: ForwardIterator 可能是不可变的。例如,任何迭代器类的const迭代器是不可变的(或者,对于一个具体的例子,C ++ 0x中的 std :: forward_list< int> :: const_iterator 正向迭代器)。


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?

解决方案

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

这篇关于为什么我需要一个Forward Iterator来实现我的自定义std :: search的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆