Is there a standard cyclic iterator in C++

Question

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.

Answer 1

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 ) );
    }
};

Answer 2

This should provide some ideas/solutions: 2 renditions, the second is a little lighter in weight. Both tested using a subrange of a vector and a list ...

#include <vector>

template <typename T, typename Container = std::vector<T>, typename Iterator = Container::iterator>
class RingIterator : public std::iterator <std::bidirectional_iterator_tag, T, ptrdiff_t>
{
  Container& data;

  Iterator   cursor;
  Iterator   begin;
  Iterator   end;

  public:

    RingIterator (Container& v) : data(v), cursor(v.begin()), begin(v.begin()), end(v.end()) {}

    RingIterator (Container& v, const Iterator& i) : data(v), cursor(i), begin(v.begin()), end(v.end()) {}

    RingIterator (Container& v, const Iterator& i, const Iterator& j) : data(v), cursor(i), begin(i), end(j) {}

    RingIterator (Container& v, size_t i) : data(v), cursor(v.begin() + i % v.size()), begin(v.begin()), end(v.end()) {}

    bool operator == (const RingIterator& x) const 
    { 
      return cursor == x.cursor; 
    }

    bool operator != (const RingIterator& x) const 
    {
      return ! (*this == x); 
    }

    reference operator*() const 
    {
      return *cursor; 
    }

    RingIterator& operator++() 
    {
      ++cursor;
      if (cursor == end)
        cursor = begin;
      return *this;
    }

    RingIterator operator++(int) 
    {
      RingIterator ring = *this;
      ++*this;
      return ring;
    }

    RingIterator& operator--() 
    {
      if (cursor == begin)
        cursor = end;
      --cursor;
      return *this;
    }

    RingIterator operator--(int) 
    {
      RingIterator ring = *this;
      --*this; 
      return ring;
    }

    RingIterator insert (const T& x)
    {
      return RingIterator (data, data.insert (cursor, x));
    }

    RingIterator erase() 
    {
      return RingIterator (data, data.erase (cursor));
    }
};

template <typename T, typename Iterator>
class CyclicIterator : public std::iterator <std::bidirectional_iterator_tag, T, ptrdiff_t>
{
  Iterator   cursor;
  Iterator   begin;
  Iterator   end;

  public:

    CyclicIterator (const Iterator& i, const Iterator& j) : cursor(i), begin(i), end(j) {}

    bool operator == (const CyclicIterator& x) const 
    { 
      return cursor == x.cursor; 
    }

    bool operator != (const CyclicIterator& x) const 
    {
      return ! (*this == x); 
    }

    reference operator*() const 
    {
      return *cursor; 
    }

    CyclicIterator& operator++() 
    {
      ++cursor;
      if (cursor == end)
        cursor = begin;
      return *this;
    }

    CyclicIterator operator++(int) 
    {
      CyclicIterator ring = *this;
      ++*this;
      return ring;
    }

    CyclicIterator& operator--() 
    {
      if (cursor == begin)
        cursor = end;
      --cursor;
      return *this;
    }

    CyclicIterator operator--(int) 
    {
      CyclicIterator ring = *this;
      --*this; 
      return ring;
    }
};

#include <iostream>
#include <iomanip>

#include <list>

enum { CycleSize = 9, ContainerSize };

template <typename cyclicIterator>
void test (cyclicIterator& iterator, size_t mn)
{
  int m = mn;
  while (m--)
    for (int n = mn; n--; ++iterator)
      std::cout << std::setw(3) << *iterator << ' ';
  --iterator;
  m = mn;
  while (m--)
    for (int n = mn; n--; --iterator)
      std::cout << std::setw(3) << *iterator << ' ';
}

template <typename containers>
void load (containers& container)
{
  while (container.size() < ContainerSize)
    container.push_back (container.size());
}

void main (void)
{
  typedef std::vector<int>     vContainer;
  typedef vContainer::iterator vIterator;
  typedef std::list<int>       lContainer;
  typedef lContainer::iterator lIterator;

  vContainer v;  load (v);
  vIterator vbegin = v.begin() + 1;

  RingIterator <int, vContainer, vIterator> vring (v, vbegin, v.end());
  CyclicIterator <int, vIterator> vcycle (vbegin, v.end());

  lContainer l;  load (l);
  lIterator lbegin = l.begin(); ++lbegin;

  RingIterator <int, lContainer, lIterator> lring (l, lbegin, l.end());
  CyclicIterator <int, lIterator> lcycle (lbegin, l.end());

  test (vring, CycleSize);
  test (vcycle, CycleSize);
  test (lring, CycleSize);
  test (lcycle, CycleSize);
}

Answer 3

The CGAL library defines Circulators. They are used like this.

template<class Circulator, class T> 
bool contains(Circulator c, Circulator d, const T& value) { 
  if (c != 0) { 
    do { 
      if (*c == value) 
        return true; 
    } while (++c != d); 
  } 
  return false; 
} 

Note that they look like iterators at first glance but note that the logic (and the structure of the loop) is different than for iterators). if(not empty) do{..}while() instead of while(){...}.

Answer 4

Eric Niebler's ranges-v3 library (on which the upcoming C++20 ranges is based) has ranges::view::cycle. This adapts its source range into an endlessly repeating infinite range. However we require a single repeat which may be easily achieved using ranges::view::concat.

#include <ranges/v3/all.hpp>

int main() {
    std::string s1 = "abc";
    std::string s2 = "bca";

    auto s2s2 = ranges::view::concat(s2, s2);
    auto i = std::search(s2s2.begin(), s2s2.end(), s1.begin(), s1.end());
    if (i != s2s2.end() && s1.size() == s2.size()) {
        std::cout << "s1 is a rotation of s2\n";
    }
}

Answer 5

You’re maybe looking for Boost’s Circular Buffer. But if you’ve already checked Boost, it might not be the one you want.

Answer 6

On the other hand, the very idea of cyclic iterator is not compatible to STL container ideology. You should not want cyclic iterator, as the user of this iterator may be surprized by its unusual behavior. Usually in STL you are iterating from the beginning to the end of container. Infinite loop in that case. Because the end is not reachable.

After all, obviously, you are not going to do more than 2 cycles to solve your task. No reason to have special iterator with confusing behavior. That is better to iterate usual linear container twice or may be even less then twice.