Iterator of the Week

=====================

This is on going series of articles showcasing different uses for STL style iterators in C++. All source code presented here is copyright 1998-2002 James M. Curran, but may be used freely.  All comment and suggestion are welcome.

=================================================

#0 - A Circular Iterator.

=================================================

The common usage of an iterator is to have it start at the beginning and progress to the end.  But what if you don’t want to get off the roller coaster? What if you want through the container over and over again, just like a circular buffer.  For that, we need a “circular” iterator.

First of all, we are going to want to use it for many different types of containers, so it’s going to have to be a template. (Even if we only want to use for, say, vectors, the compiler still considers vector<int> and vector<string> different types, so we’ll still need to templatize the iterator.)

template<typename T>

class const_circular_iter : public std::iterator<std::forward_iterator_tag, T::value_type> 

{ 

std::iterator<> base class is used to tell the compiler that this iterator has all the abilities of a forward iterator, and can be used wherever one is required.  The class is called “const_circular_iter” because we can only read values from it; we cannot modify the container using this iterator. (We’ll get to a modifiable circular iterator in a future article)

protected:

       T::iterator   begin;

       T::iterator   end;

       T::iterator   iter;

Now, clearly the principle behind this is that we act just like a normal iterator, until the point where we reach the end, where we jump back to the beginning.  So, clearly, we are going to need to know, where the end is, where the beginning is, and where we are now. These three iterators handle that.   You might think we can get by without begin & end, if we hold a reference to the container we are iterating through.  True, but that limits us to step completely through the container.  This way we can loop over a few elements in the middle of a large container.  Further, this allows us to iterators that don’t point into a container.  We’ll get do some of them in a future article as well.

And yes, I did cringe over making data elements protected instead of private, but we will soon be getting to deriving the modifiable circular iterator from this, and that is so tightly linked to this that avoiding using protected would cause a lot of pointless extra work.

public:

       const_circular_iter(T& t) : iter(t.begin()), begin(t.begin()), end(t.end()) {};

       const_circular_iter(T::iterator b, T::iterator e) : iter(b), begin(b), end(e) {};

Few classes can get by without constructors, and here are ours.  We can initialize it with the container we will be loop over, or with just iterators to the beginning and end.

const_circular_iter<T>& operator++()

{     

       ++iter;

       if (iter == end)

              iter = begin;

       return(*this);

}

Here, finally, we reach the heart of the class: the prefix increment operator.  It’s operation is quite obvious.  Increment the internal iterator; when we reach the end, point back to the beginning.  That’s it.  From here on, the rest is pretty much just boilerplate and buck passing.

const_circular_iter<T> operator++(int)

{

       const_circular_iter<T>     t=*this;

       ++(*this);

       return(t);

}

const T::value_type operator*() const

       {return (*iter);}

bool operator==(const const_circular_iter<T>&   rhs) const

       {return (iter == rhs.iter);}

bool operator!=(const const_circular_iter<T>&   rhs) const

       {return ! operator==(rhs); }

};

The postfix increment operator delegates much of its work to the prefix increment.  The dereference operator passes its work onto the internal iterator dereference operator; and the inequity operator uses the equity operator, and we’re done.

#include <iostream>

#include <vector>

#include "circular.h"

using namespace std;

int main(int argc, char* argv[])

{

       vector<int>          v;

       v.push_back(1);

       v.push_back(2);

       v.push_back(3);

       const_circular_iter<vector<int> >  out (v);     // or “out(v.begin(), v.end());”

      

       cout << *out ++;

       cout << *out ++;

       cout << *out ++;

       cout << *out ++;

       cout << *out ++ << endl;

      

       return 0;

}

This will print “12312”.    

Now you may be asking, “If we are going to create a modifiable circular iterator, why are we wasting our time now with a non-modifiable one?”  Well, sometimes, the underlying iterators is so opposed to being used to modify what it points to, it won’t even compile the modifiable template.  What kind of iterator is this?  Remember when I said some iterators don’t point into containers?  Stay tuned.

---

            You can download the full source code from here.   Circular.h (3KB)

---

James M. Curran is a Senior Software Engineer for e-Commerce Solution in New York City.  He can be reached at JamesCurran@mvps.org

=================================================

NOTE: This is part of a work-in-progress.  It may eventually lead to a print article, a series of print articles, and/or a book. Or, it may not.  By participating in the public discussion of these articles, you consent to allowing you contribution to be used in any subsequent work derived from this without compensation.  I will make a good-faith effort to acknowledge those that have contributed.