Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
585 views
in Technique[技术] by (71.8m points)

stl - Is there a standard cyclic iterator in C++

Based on the following question: Check if one string is a rotation of other string

I was thinking of making a cyclic iterator type that takes a range, and would be able to solve the above problem like so:

std::string s1 = "abc" ;
std::string s2 = "bca" ;
std::size_t n = 2; // number of cycles
cyclic_iterator it(s2.begin(),s2.end(),n);
cyclic_iterator end;

if (std::search(it, end, s1.begin(),s1.end()) != end)
{
   std::cout << "s1 is a rotation of s2" << std::endl;
}

My question, Is there already something like this available? I've checked Boost and STL and neither have an exact implementation.

I've got a simple hand-written (derived from a std::forward_iterator_tag specialised version of std::iterator) one but would rather use an already made/tested implementation.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

There is nothing like this in the standard. Cycles don't play well with C++ iterators because a sequence representing the entire cycle would have first == last and hence be the empty sequence.

Possibly you could introduce some state into the iterator, a Boolean flag to represent "not done yet." The flag participates in comparison. Set it true before iterating and to false upon increment/decrement.

But it might just be better to manually write the algorithms you need. Once you've managed to represent the whole cycle, representing an empty sequence might have become impossible.

EDIT: Now I notice that you specified the number of cycles. That makes a big difference.

template< class I >
class cyclic_iterator
 /* : public iterator< bidirectional, yadda yadda > */ {
    I it, beg, end;
    int cnt;
    cyclic_iterator( int c, I f, I l )
        : it( f ), beg( f ), end( l ), cnt( c ) {}
public:
    cyclic_iterator() : it(), beg(), end(), cnt() {}

    cyclic_iterator &operator++() {
        ++ it;
        if ( it == end ) {
            ++ cnt;
            it = beg;
        }
    } // etc for --, post-operations

    friend bool operator==
        ( cyclic_iterator const &lhs, cyclic_iterator const &rhs )
        { return lhs.it == rhs.it && lhs.cnt == rhs.cnt; } // etc for !=

    friend pair< cyclic_iterator, cyclic_iterator > cycle_range
        ( int c, I f, I l ) {//factory function, better style outside this scope
        return make_pair( cyclic_iterator( 0, f, l ),
                          cyclic_iterator( c, f, l ) );
    }
};

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...