为什么std :: search需要转发iters [英] why does std::search need forward iters

问题描述

我的问题与下面的线程相同，我很难理解给出的答案，或者我的代码不应该工作，因为它只使用输入迭代器..但我的功能似乎工作和行为相同std： ：search ..so我在失去和厌恶移动而不理解正确...也许如果有人可以建议一个输入，将打破我的功能，但不是std ::

my issue is identical to the thread below, I'm struggling to understand the answers given, or rather my code shouldn't work as it only uses input iterators ..but my func appears to work and behave identically to std::search ..so I'm at a loss and loathe to move on without understanding properly ...maybe if someone can suggest an input that will break my function but not the std::

从为什么我需要一个Forward Iterator来实现我的自定义std :: search ：

我正在学习的书Accelerated
C ++，来自Koenig& Moo。

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

练习8-2要求我在
上实现一些模板化的函数，从
< algorithm> < numeric>和
指定我的
实现需要什么样的迭代器。

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.

当试图实现std :: search时，
我确定我只需要输入
迭代器。

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

但是，看看实现
std :: search用我的
编译器，我可以看到他们使用
forward迭代器，但是我不能
理解为什么，因为没有
需要写，只读，输入
迭代器符合要求。

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.

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

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

提前感谢。

myfunction：

myfunction:

template <class In> 
In search(  In begin, In end, In begin2, In end2 )
{
    In found ;                      // iter: 1st element in pattern match(in content)
    In pattern_begin = begin2 ;     // iter: 1st element in search pattern.
    int flag = 0 ;                  // flag: partial match found?

    // search content for pattern 
    while (  begin < end  ) {

        // if pattern-match fails ..reset vars
        // & continue searching remaining content/elements
        if ( *begin != *begin2 ) {

            In ret ;                     
            begin2 = pattern_begin ;
            flag = 0 ;
            begin++ ;


        } else {
            // compare next element in pattern with next element in content.
            // if: 1st element of 'pattern' is found, store iter to it's pos
            // ..then if entire pattern is found, we can ret an iter to where it starts
            if ( flag == 0 ) { 
                found = begin ;
                flag = 1 ;
            }
            // inc iters to compare next elements in partial match
            begin++ ;
            begin2++ ;
        }

        // if: iter is 1-past end of search pattern
        // then entire pattern has been found 
        // return the iter to where it starts
        if( begin2 == end2 ) {  return found ;  }

    }

    // end of content reached, no complete pattern found
    // begin should? equal an iter 1-past the end of content
    return begin ;
}

驱动程序：

///* // Driver: custom::search(  b, e, b2, e2  ) 
#include <string>
#include <vector>
#include <iostream>
//#include <algorithm>
#include "library_algorithms.h"

int main() {

    // init string test
    std::string content = "fo The fox  foxu jumped  foxe foxy " ;
    std::string search_pattern = "foxy" ;

    // func test on string
    std::string::iterator ret_iter = 
    custom::search(  content.begin(), content.end(), search_pattern.begin(), search_pattern.end()  ) ;
    //std::search(  content.begin(), content.end(), search_pattern.begin(), search_pattern.end()  ) ;

    // output
    if (  ret_iter != content.end()  ) {

        std::cout << std::endl << std::endl << search_pattern << ": found at position: " << int(  ret_iter - content.begin()  ) << std::endl;

    } else { 

        std::cout << std::endl << std::endl << search_pattern << ": ...not found" << std::endl;
    }




    // Init vec test:
    // create content values in range:  10 20 30 <......> 9970 9980 9990
    std::vector<int> myvector;
    for (int i=1; i<1000; i++) myvector.push_back(i*10);

    // create pattern values to search for
    std::vector<int> pattern ;
    pattern.push_back( 3730 ) ;
    pattern.push_back( 3740 ) ;
    pattern.push_back( 3750 ) ;
    pattern.push_back( 3760 ) ;

    // test: func on vector<int>
    std::vector<int>::iterator it;
    it = custom::search (  myvector.begin(), myvector.end(), pattern.begin(), pattern.end() );

    // output
    if (it!=myvector.end())
    std::cout << std::endl << std::endl << "pattern found at position " << int(it-myvector.begin()) << std::endl;
    else
    std::cout << std::endl << std::endl << "pattern not found" << std::endl;





    return 0 ;

}

推荐答案

ve误解了输入迭代器可以做什么。

You've misunderstood what an input iterator can do.

您不能保存或复制输入迭代器。它允许你完全遍历序列一次。换句话说，这一行，其中，将打破： begin2 = pattern_begin 。

You can't "save" or copy an input iterator. It allows you to traverse the sequence exactly once. In other words, this line, among others, will break: begin2 = pattern_begin.

输入迭代器可以表示你不能轻易地倒带，比如说，从网络适配器接收的数据流。指向6个元素之前的迭代器不再有意义，因为该数据可能不再在内存中可用。您只能在信息流中加入当前位置。

An input iterator may represents something that you can't readily "rewind", like, say, the stream of data received from a network adapter. An iterator pointing to "6 elements ago" is no longer meaningful, because that data may no longer be available in memory. You only have the current position in the stream.

很显然，为了实现 code>正确，您需要能够遍历部分序列多次。

It should be obvious that in order to implement search correctly, you need to be able to traverse parts of the sequence more than once.

这篇关于为什么std :: search需要转发iters的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！