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 stepsThe 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.
So that's it. The last person left in the office has handed his keys in. I'm the only one left now.
