Title: STL-style Circular Buffers By Example, Part Two

In the first part of this series [Goodliffe] we started to look at how to implement a template container class in the style of the C++ standard template library (STL). The example container we're working with is a circular buffer. We started off by writing a minimal circular buffer class, and through a number of exercises refined this basic class until we had a mostly STL-like container class.

We're still not quite there yet. By the end of this article we'll have covered all the necessary ground, and our container class can truly be used like any other STL container.

As in the previous article, the approach adopted here is to present a number of exercises for you to perform. This is more than a clumsy article-writing device. Experience shows that you only really learn something when you try to actually do it. You can read around a subject as much as you like; it's only when you pick up tools and start applying what you've read, when the metaphorical rubber hits the hypothetical road, that you really solidify your knowledge. These exercises are then a good opportunity to learn in a practical way. Put as much effort into them as you want to get out of the article.

So far we have a template container class with forward and reverse iterators. Unlike traditional circular buffer implementations we've provided operator[] for random access; this is largely to provide the iterator's implementation.

You can download an example copy of the code this far from http://cthree.org/pete/cbuf.html.

Amongst the functions that we still need to implement for our circular_buffer class are a number of constructors. As an analogue, think about vector. It has a several useful constructors. So off we go…

The compiler will automatically generate

Sometimes these defaults are fine and do just what we want. Often when creating more adventurous classes (with dynamically created data members) they're not at all suitable and we have to provide our own, or just prevent the compiler from emitting its defaults.

If we provide our own versions, the defaults are suppressed. This is of particular note for constructors - any constructor you provide, no matter what signature it has^[1], will suppress the parameterless default constructor. If you want to have a parameterless constructor you will then have to provide it, even if it does exactly what the compiler generated version would.

If you don't want to supply the operations but the compiler generated versions are wrong, you can suppress them by declaring the functions, but not defining them. For this to make any sort of sense, you should declare the functions as private members of the class.

A copy constructor allows us to 'clone' objects. It allows us to write:

  // for some existent circular_buffer<int>
  // called cbuf;
  circular_buffer<int> copy_of_cbuf1(cbuf);
  circular_buffer<int> copy_of_cbuf2 = buf;

Both of these copies are created using the copy constructor.

We're storing data in a dynamically created array, so the default copy constructor is not appropriate. Consider what would happen if we wrote:

  {
  circular_buffer<int> cbuf1(100);
  circular_buffer<int> cbuf2(cbuf1);
  }

The default copy constructor will copy the array pointer, array_. Now both circular buffer objects use the same array, which is plainly nonsensical. Things get worse, though. At the end of the block scope cbuf2 will first be destroyed. The destructor calls delete [] array_. It is now an ex-array. Next the cbuf1 destructor is called. It will attempt to delete the same array which is now pushing up the daisies, a plainly wrong operation; and one that is potentially disastrous.

Our replacement copy constructor can look something like the following:

  circular_buffer(const circular_buffer &other)
    : array_(new value_type[other.array_size_]),
      array_size_(other.array_size_),
      head_(other.head_),
      tail_(other.tail_),
      contents_size_(other.contents_size_)
    {
      std::copy(other.begin(),
      other.end(), array_);
    }

Did you hand-roll your own loop for the copy operation? It pays to use standard library facilities where you can. This implementation works most of the time, but there are some lurking problems that we'll come back to later.

The vector class has a nice constructor that takes two forward iterators defining a range, as the initial contents of the container. Although not strictly required, we can have some of that goodness, too.

  template <class InputIterator>
  circular_buffer(InputIterator from, InputIterator to);

Here we'll have to consider what initial size our buffer should take. We could make this value an extra parameter, but that makes the interface less flexible and more lumpy. We could require that the supplied iterators are random access iterators and make some decision based on the value of to-from. Again, this requirement makes the code less flexible. Or we can try some other scheme.

It is possible to implement this constructor if we provide another function, reserve that ensures we have a specified capacity. The vector class has this capability. Whilst it makes a bit more sense as a member function of vector (since by definition vectors can grow), we can make good use of it here.

  template <class InputIterator>
  circular_buffer(InputIterator from, InputIterator to)
    : array_(new value_type[100]),
      array_size_(100),
      head_(0),
      tail_(0),
      contents_size_(0)
  {
    while (from != to) {
      if (contents_size_ == array_size_) {
        reserve(static_cast<size_type>(array_size_ * 1.5)); // (*)
      }
      push_back(*from);
      ++from;
    }
  }

The initial capacity value has been picked arbitrarily. I'll leave the implementation of reserve up to you. The choice of multiplication factor at the point marked (*) is interesting - there has been plenty of research into this. For most situations the value of 1.5 is practical, balancing the number of reallocations required with the amount of 'wasted space' in the buffer.

This differs from the copy constructor considerably, although you might think it is doing the same job. That's because the constructor has to correctly create and initialise an entire object, whilst the assignment operator has to deal with an already created object; in our case memory has already been allocated.

How did you do it? Be careful about the capacity of the buffer parameter passed and the capacity of the buffer you're assigning to. There are two ways to implement this function. You'll probably have written something like the following:

  circular_buffer &operator=(const circular_buffer &other) {
    clear();
    // Ensure we have enough space
    if (other.contents_size_ > array_size_) {
      reserve(other.array_size_ );
    }
    // Now copy the contents across
    std::copy(other.begin(), other.end(), array_);
    head_ = 0;
    tail_ = other.size();
    contents_size_ = other.size();
  }

We'll see the 'other way' later. This little function has the same lurking problem as the copy constructor. Can you see what it is?

The STL containers all take an additional template parameter, the allocator. This class type abstracts the real concerns of allocating, using, and releasing memory. The default library std::allocator is implemented in terms of new and delete, however other platforms may provide different views of memory, be it pooled memory, garbage collected memory, or whatever. By using an abstract allocator interface we can avoid worrying about this sort of implementation detail and also gain the benefits of these kinds of facilities for free. Even if it weren't required, it would be worth it.

So how do we need to modify circular_buffer? First we add another template parameter with a default value. It goes at the end of the template parameter list:

typename Alloc = std::allocator<T>

This requires us to include the <memory> header file, which defines this default std::allocator template class. Now we modify our list of container class typedefs, thus:

  typedef Alloc allocator_type;
  typedef typename Alloc::value_type value_type;
  typedef typename Alloc::pointer pointer;
  typedef typename Alloc::const_pointer const_pointer;
  typedef typename Alloc::reference reference;
  typedef typename Alloc::const_reference const_reference;
  typedef typename Alloc::size_type size_type;
  typedef typename Alloc::difference_type difference_type;

Note we've added the allocator_type and we also modified these other definitions, since the allocator now provides us with all the correct definitions. Next, to work like any other STL container we add a data member alloc_ of the allocator type and, for consistency, we also add a new member function, thus:

  allocator_type get_allocator() const {
    return alloc_;
  }

That's the basic stuff out of the way. Next we need to make the constructors and destructor call the allocator functions for their memory management, rather than new and delete. Given that the allocator class has the following functions, try exercise #5.

  template <class T>
  class std::allocator {
  public:
    typedef T *pointer;
    typedef size_t size_type;
    pointer allocate(size_type n, /*hint parameter*/);
    void deallocate(pointer p, size_type n)
    /* ... */
  };

Note that the 'hint' parameter can be ignored for our purposes, it defaults to zero and is usually unused. allocate returns space for n objects of type T. It doesn't initialise them. deallocate frees the memory resource, but doesn't destroy the objects.

That's not too onerous really. However, we're beginning to see a hint of the problem I alluded to in exercise #1 of the first article, and this is the solution. The allocator does not initialise any objects in the memory pool in the way that an array would. This is crucial. Why? Well, it doesn't matter too much for a container of ints. But think about a complicated class with a slow constructor. Creating an array of these objects is therefore a very slow operation; an array initialisation will call the default constructor to create an object at each array position. It's especially wasteful when you consider that you'll ignore the default construction, and use assignment to write the first value you care about to each array element anyway.

That's an awful lot of wasted array effort. It also introduces an unnecessary dependency on the value_type: it requires that there must be a default constructor in order to be able to allocate the array. Now using this 'allocator' approach we are no longer bound by this constraint, on top of not wasting effort constructing useless objects. Bonus!

However, we will need to construct and destruct each object by hand instead. This is the price we pay. Given that there are the std::allocator member functions below, answer exercise #6:

  void construct(pointer p, const T &val)
    { new (p) T(val); }
  void destroy(pointer p)
    { p->~T(); }

Note the use of placement new by the construct function.

push_back is the only function that needs to create new data elements^[2]. Rather than using assignment in this function, we call construct. However, we don't need to do this when the buffer is full and we're throwing away the data at the end of the buffer by reusing the last buffer element. In this case we only have to assign to the element as before. pop_front removes elements from the container, as do clear and the destructor (are there any others in your implementation?). These therefore need to use destroy. Note that it will no longer be valid to use the std::copy algorithm as we did before - it won't take care of the object construction for us.

As a final allocator modification, we must now change max_size. The allocator class provides this function itself. This is logical enough since it knows how many objects could potentially be allocated using its memory model. We therefore make our max_size call the allocator's.

If our class is not exception safe, it's of no real value in the Real World. See the sidebar for a brief description of what's involved in writing exception safe code. We don't have the space here to really describe the subject, but we'll take a look at what we need to do to make our code bullet proof. As it stands it is really not at all exception safe. In fact it's downright exception dangerous.

In truth, it's a bit late in the development to be considering exception safety. However, we really needed to have got this far to have illustrations of the issues involved.

We'd like to provide at least the basic exception safety guarantee in our member functions, and ideally we want to aim to provide the strong guarantee in every method. Let's quickly look at some of the reasons why our existing container is dangerous. We'll start at the beginning: some constructors, for example, are a cause of resource leaks.

Look at the copy constructor. The first thing it does is allocate memory in the initialiser list. If this fails then a std::bad_alloc exception is thrown and nothing leaks. This is fine behaviour, and a good reason to put dynamically allocated memory near the head of your list of variables (remember that data members are initialised in the order of the class definition, not the order you list them in the constructor's initialiser list). None of the other assignments might throw, so we're safe in the rest of this initialiser list.

However, on entering the constructor body, we loop around copying elements. Any of the value_type object constructors might throw an exception. Say we get half way through the copy loop and a constructor fails. The failure exception propagates through our constructor (so at least we're exception neutral here), and we leak the allocated memory. We've also created a number of contained objects that we didn't destroy - heaven help us if there are dangerous side effects from this behaviour.

Tightening up cases like this is not actually going to be impossible to do, since I've introduced facilities in a way that allows exception safety (for example, separating front and pop_front). We'll just have to think carefully about each member function. One of the golden rules when writing exception safe code is that each function should have at most one side effect, otherwise an exception safe implementation is complicated. You can see then that writing exception safe code does have an impact on your public API design, you have to design it in from the start.

When people think about exception safety they imagine code strewn with try/catch blocks. In fact this is far from the truth. Our exception safe code will be practically free of these. The basic technique we follow is to perform all potentially dangerous activities 'off to one side' in a way that means they'll get tidied up neatly if anything fails. Once these dangerous activities are complete we can then make the changes live using operations that are known not to throw.

In order to do this we are going to need some operations that are known not to throw. We asserted in the sidebar that our destructor can't throw. Now enter swap.

It's not too nasty. Note that we don't bother to swap the allocator objects. They should be identical if the circular_buffer types are the same.

  void swap(circular_buffer &other)
  /* nothrow */
    {
      std::swap(array_, other.array_);
      std::swap(array_size_, other.array_size_);
      std::swap(head_, other.head_);
      std::swap(tail_, other.tail_);
      std::swap(contents_size_, other.contents_size_);
    }

Although we're providing the nothrow guarantee note that we don't put an empty exception specification at the end of the function signature. We should try to avoid writing these when we can, they can add unnecessary overhead to the running code; they are more likely to make the compiler generate much worse code than anything better. We know the function won't throw; we don't need the compiler to check this for us too.

OK, that's a big task. Let's start with the basic constructor. It's actually already strongly exception safe. The only operation that might throw is the memory allocation. This is fine, the std::bad_alloc exception will propagate up and we won't leak at all. How must you alter the other constructors? I won't show you here, but note that you will actually need try/catch blocks in this case. Next, push_back:

  void push_back(const value_type &item) {
    size_type next = next_tail();
    // no state change yet
    if (contents_size_ == array_size) {
      array_[next] = item; // (*)
      increment_head();
    }
    else {
      alloc_.construct(array_ + next, item); // (*)
    }
    increment_tail();
  }

  private:

  size_type next_tail() {
      return (tail_+1 == array_size_) ? 0 : tail_+1;
  }

How is this different? Our interest is at the points marked (*). We move the constructions/assignments to positions above any other state manipulation. If an exception is thrown we haven't modified any other state. This is not quite a strong exception safety guarantee, though: our container is now as exception safe as the value_type's constructor/assignment operators. This is best we can do.

As a final example, we'll consider the assignment operator. We use a neat idiom here to ensure that we are strongly exception safe:

  circular_buffer &operator=(const self_type &other) {
    circular_buffer tmp(other);
    swap(tmp);
    return *this;
  }

Can you see how neat this is? We do all the work 'off to one side' by creating a temporary object that looks like other. If that fails (based on the fact the copy constructor is exception safe and won't leak) we will propagate the exception, but not have altered our own state and not leaked, so we are strongly exception safe. If it succeeds we 'make permanent' the change using two operations that are known not to fail: swap, and the destructor. We swap our current state with that of tmp so we now look as if we've been 'assigned to'. When tmp goes out of scope it is destroyed, taking with it our old state.

A lot of the other functions are adjusted in similar manners. We don't have space to describe them all here. See my reference code (in the Getting the code section below) for further examples.

The long and short of exception safety is: you can't reasonably bolt it on after writing the code. You have to factor it into the class' design from the start. Well written exception safe code shouldn't need tonnes of try/catch blocks. If it's not simple and clear to read then something's wrong. Generally you'll find that good 'exception safe' code is not just designed to be safe in the presence of potential exceptions at the expense of clarity and program efficiency - it will also be genuinely well designed and thought out code.

There are still a few loose ends we need to tie up, and then we're done.

  template <typename A, bool B, typename C>
  bool operator==(const circular_buffer<A, B, C> &a,
                  const circular_buffer<A, B, C> &b) {
    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
  }

  template <typename A, bool B, typename C>
  bool operator<(const circular_buffer<A, B, C> &a,
                 const circular_buffer<A, B, C> &b) {
    return std::lexicographical_compare(a.begin(),
                                        a.end(),
                                        b.begin(),
                                        b.end());
  }

Whilst I know you've been slavishly following the exercises I know that you'll want to see my reference implementation to see how close you came to it. Or perhaps you just want an STL style circular buffer class and can't be bothered to write your own.

My circular_buffer class library is available from http://cthree.org/pete/cbuf.html.

We've now created an entire template container class. It follows the STL style carefully. Not only does this mean that we now know how to write STL-like containers, it also means that anyone using this circular_buffer class can pick it up with a minimum of hassle. It behaves in a known way, can be accessed as most other STL containers, and it is immediately compatible with existing STL algorithms. Perhaps you've also gained a respect for the work that has been put into the standard C++ libraries.

Hopefully you've enjoyed these articles, and by stepping through the exercises you have now picked up some useful techniques that can be applied to other code you write. Let me know if it's been useful.