Easiest way to make a cyclic iterator (circulator)?

Question

I have an object that I want to travel in a continuous loop in a game. I have a series of coordinates in a std::vector that I want to use as waypoints.

Is there any way to make an std::vector<T>::iterator cyclic (also known as a circulator)?

The best I can come up with is to have two iterators and then whenever the first iterator is exhausted assign to it the value of the second (which would not be used to do anything else) but I am not even sure it will work - will the assignment operator copy whatever the iterator is using to hold the index or will it merely be referenced (and therefore will be useless after the second round)?

I want the object to travel the waypoint forever (unless it is destroyed but that doesn't happen in that method), but the iterator will only be called once for each frame and must return so that I can update the other objects in the game.

The solution must work on gcc and microsoft compiler (if it isn't possible to write it in standard C++).

Answer 1

Ok, now your problem is clearer :-)

Take a look at boost::iterator_facade and boost::iterator adaptor. They implement the full iterator interface and your cycle_iterator only as to implement a few methods like increment(), decrement():

template<class IteratorBase>
class cycle_iterator 
     : public boost::iterator_adaptor< 
          cycle_iterator,     // the derived class overriding iterator behavior
          IteratorBase,       // the base class providing default behavior
          boost::use_default, // iterator value type, will be IteratorBase::value_type
          std::forward_iterator_tag, // iterator category
          boost::use_default  // iterator reference type
       > 
{
  private:
     IteratorBase m_itBegin;
     IteratorBase m_itEnd;

  public:
     cycle_iterator( IteratorBase itBegin, IteratorBase itEnd ) 
       : iterator_adaptor_(itBegin), m_itBegin(itBegin), m_itEnd(itEnd)
     {}

     void increment() {
        /* Increment the base reference pointer. */
        ++base_reference();

        /* Check if past-the-end element is reached and bring back the base reference to the beginning. */
        if(base_reference() == m_itEnd)
            base_reference() = m_itBegin;
     }

     // implement decrement() and advance() if necessary
  };

This probably doesn't compile but should get you started.

Edit:

boost::iterator_adaptor implements the full iterator interface in terms of few functions. It provides default implementations for increment(), decrement(), advance(), distance_to(), equal_to() and dereference() using the base iterator passed down to the iterator_adaptor base class.

If all you need is a forward iterator, only the increment() method must be implemented to wrap around once you reach the end iterator. A cyclical iterator can be bidirectional if you implement decrement() in a similar fashion. If IteratorBase is itself a random access iterator, the cycle iterator can also be random access and method advance and distance_to must be implemented using modulo operations.

Answer 2

boost::iterator adaptor is the way to go, take my word for it ;)

That being said I want to point out a few pitfalls. I don't think I can edit an existing answer, so bear with me.

Given that your base iterator is going to be a vector you need to be careful which core interface functions you need to implement. If you want your cycle_iterator to be a random access iterator you need all of the following:

increment() 
decrement()
advance(n)
distance_to(j)

Now distance_to(j) is a somewhat funny concept for a cycle_iterator and its semantics can get you in all kind of trouble. This can be avoided by restricting the iterator category of the adapted iterator to either forward or bidirectional. Like this:

template <class BaseIterator>
class cycle_iterator
  : public boost::iterator_adaptor<
        cycle_iterator                  // Derived
      , BaseIterator                    // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{ ... };

In this case you only need to implement increment:

void increment()
{
  if (++this->base_reference() == this->m_itEnd)
  {
    this->base_reference() = this->m_itBegin;
  }
}

For a bidirectional you also need decrement:

void decrement()
{
  if (this->base_reference() == this->m_itBegin)
  {
    this->base_reference() = this->m_itEnd;
  }
  --this->base_reference();
}

Disclaimer: I did not run this through a compiler, so I am ready to be embarrassed.