Hippicoder - 1 year ago 132
C++ Question

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

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
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 ) );
}
};
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download