C++: An STL-like circular buffer (Part 10)

Part 10 already! There's quite a lot of detail involved in writing an STL-like container. Now we're going to delve into some of the more interesting stuff...

I promised you iterators, and so iterators is what you'll get. Like the indexing operations we added in part 8, a circular buffer traditionally doesn't let you iterate through the contents. But where's the fun in that?

Different containers support different classes of iterator:

• An input iterator allows you to read values with forward movement. It can be incremented, compared, and deferenced.
  
• An output iterator also moves forwards, but allows you to write values rather than read them on the way.
  
• A forward iterator effectively combines the input and output iterators, allowing you to read or write values with forward movement.
  
• A bidirectional iterator adds the capability to move backwards; you can increment and decrement them.
  
• A random access iterator allows you to read and write with the ability to do pointer arithmentic and pointer-like comparisons of the iterators.
  
• A reverse iterator is a bidirectional or random iterator that moves through the container in the reverse direction.
  

So what kind of iterator should we support? In our simple container it's perfectly possible to support a random access iterator.

First steps

The container must supply the following nested types: iterator and const_iterator. These can be typedefs or nested class declarations (for example, the most efficient iterator implementation for the std::vector is a typedef of a pointer). However, to start off with, we can simply construct a nested class inside circular_buffer.

Let's start off with the non-const iterator version.

    // In declaration
 class iterator;
 iterator begin();
 iterator end();

Our most implementation is not quite as simple as a pointer, but not much more complex. We need only maintain an index into the buffer and a back-pointer to the parent circular_buffer class. The iterator can be implemented in terms of circular_buffer::operator[].

Like a container, and an allocator, an STL iterator must provide a number of nested type definitions for algorithms to be able to use them appropriately. These include:

• difference_type
  
• value_type
  
• pointer
  
• reference
  
• iterator_category
  

These are picked up by the std::iterator_traits class (see section 24.3.1 of the standard). You needn't follow the mechanics here completely, since the standard library provides a convenient iterator base class, std::iterator, that your iterator implementation can inherit from. This base class will define all the relevant types for you based on the template parameters you give it. The template parameters are:

• the iterator category (these are tag types in the std namespace)
  
• the difference_type
  
• the pointer type
  
• the reference type
  

All of these can be selected from circular_buffer's existing pool of typedefs.

Here's our first stab at an implementation:

template <typename T, typename A>
class circular_buffer<T,A>::iterator
 : public std::iterator<std::random_access_iterator_tag,
                        value_type,
                        size_type,
                        pointer,
                        reference>
{
public:
 typedef circular_buffer<T>             parent_type;
 typedef typename parent_type::iterator self_type;

 iterator(parent_type &parent, size_type index)
     : parent(parent), index(index) {}

 self_type &operator++()
 {
     ++index;
     return *this;
 }
 self_type operator++(int) // postincrement
 {
     self_type old(*this);
     operator++();
     return old;
 }
 self_type &operator--()
 {
     --index;
     return *this;
 }
 self_type operator--(int) // postdecrement
 {
     self_type old(*this);
     operator--();
     return old;
 }

 reference operator*() { return parent[index]; }
 pointer operator->()  { return &(parent[index]); }

 bool operator==(const self_type &other) const
     { return &parent == &other.parent && index == other.index; }
 bool operator!=(const self_type &other) const
     { return !(other == *this); }

private:
 parent_type &parent;
 size_type    index;
};

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::begin()
{
 return iterator(*this, 0);
}

template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::end()
{
 // Remember: end() is one past the last element.
 return iterator(*this, size());
}

This works nicely enough, although we'll refine the design as we add more facilities to the iterator.

Make sure that you understand the difference between preincrement and postincrement and how you overload each operator in a class declaration. Also make sure you know the difference between operator* and operator->.

Implementing reverse iterators

If we want to support reverse iteration, we must provide type definitions for the iterator and const_iterator counterparts: reverse_iterator and const_reverse_iterator.

Helpfully, the C++ standard library provides a useful implementation trick for reverse iteration: std::reverse_iterator. This class wraps a bidirectional/random forward iterator and adapts forward and backward movement to appropriate calls on the underlying forwards iterator.

We can use it like this:

    typedef std::reverse_iterator<iterator> reverse_iterator;
 reverse_iterator rbegin() { return reverse_iterator(end()); }
 reverse_iterator rend()   { return reverse_iterator(begin()); }

When we eventually write a const_iterator, we can also write this:

    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
 const_reverse_iterator rend()   const { return const_reverse_iterator(begin()); }

It's that simple.