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

Now it's time to think about the gory internal details of our circular_buffer.

Obviously, we need a data store for the buffer. A good old-fashioned array will do nicely, thank you. We'll need to remember the capacity of the array so we don't overrun it. And we must maintain a record of the front and the back of the data stored in the array. We could store these as indexes into the array, or as a pointer to the data. Let's go with the latter. There will be no need to separately store the number of items held in the buffer as it can be derived easily from the front/back pointers.

We want to play the C++ game nicely and make sure that we never leak resources, so we'll store the buffer in a boost::scoped_array (see here). So, here's a first stab at the data members for our class:

private:
const size_type                 m_capacity;
boost::scoped_array<value_type> m_buffer;
value_type                     *m_front;
value_type                     *m_back; // points to next unused item

Stylistic note #1: I really don't usually like m_ prefixes for member variables. However, since we will shortly need to create a public method called capacity(), we can't use that as a variable name. I don't want to instead use a bizarre variable name for "capacity", so I'll adopt this naming scheme.

Here's the plan:

• We insert new data at m_back.
• We read data from m_front.
  
• When m_front == m_back (as it will after construction), the buffer is empty.
• If the item after m_front is m_back, then the buffer is full.
  

Having established this, we can get on with some serious implementation:

The constructor

The constructor sets everything up as you'd expect. Note that we make it explicit so you can't write the nonsensical line: circular_buffer cb = 20;

// In declaration
explicit circular_buffer(size_t capacity);


template <typename T>
circular_buffer<T>::circular_buffer(size_t capacity)
: m_capacity(capacity),
m_buffer(new value_type[capacity]),
m_front(buffer.get()),
m_back(buffer.get())
{
}

Stylistic note #2: I'm writing the definitions of all methods out-of-line underneath the class declaration. This makes the class declaration far easier to read, at the expense of more typing are the definition.

If you're paying attention then you'll already realise that there may be some problems with this design. We'll get to this in Part 6.

Some easy questions

Now we can implement some of the simpler methods required by section 23.1 of the C++ standard. size() returns the number of items held in the buffer. empty() tells you if the container is empty (rather than emptying all the items out of it, which is a common newbie misunderstanding!) capacity() tells you how many items the container can hold. max_size() returns the size() of the largest possible container.

// In declaration
size_type size()     const;
size_type max_size() const;
bool      empty()    const;
size_type capacity() const;

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::capacity() const
{
  return m_capacity;
}

template <typename T>
bool circular_buffer<T>::empty() const
{
  return m_front == m_back;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::size() const
{
  return (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T>
typename circular_buffer<T>::size_type circular_buffer<T>::max_size() const
{
  // Yes, this is a rather nasty trick. We could pull the maximum value for
  // size_type from std::numeric_limits instead of using -1.
  // But we'll do something even nicer shortly.
  const size_type count = size_type(-1) / sizeof(value_type);
  return std::max(count, size_type(1));
}

The only reasonably complex function is size() and it's clear what's going on in there, isn't it?

Note the use of typename in the function implementations above. That is required to help the compiler deduce that circular_buffer<T>::size_type is the name of a type; the poor thing can't work this out for itself.

Notable by their absense

The circular_buffer is notionally a sequence container (as defined by section 23.1.1 of the standard), by its very nature it does not support insertion or removal of items in the middle of the sequence. So we will not provide a version of insert() or erase(). We'll also chose not to support reserve(); unlike a growing container (e.g. std::vector), the circular buffer size must be supplied on construction. There is little point in providing an interface to change this capacity. (If you want to do this, I will leave it as an exercise for the reader).

Prohibit the prohibitable

Our choice of data storage means that it is not safe to copy or assign to a circular_buffer. Until we deign to fix this, we'll make sure that a user of the code can't shoot themselves in the foot:

// In declaration
private: // Not to be implemented
   typedef circular_buffer class_type;
   circular_buffer(const class_type &);
   class_type &operator=(const class_type &);

This is a standard c++ technique: we declare the copy constructor and assignment operator in the private section and don't implement them.

Testing

Before we bring part 4 to rest, we'd best check that those methods work. I usually use Aeryn, a great unit test framework for C++. But rather than indoctrinate you into the cult Aeryn right now, we'll write some simple tests using nothing more that the standard C assert macro.

int main()
{
  circular_buffer<int> cb(5);

  assert(cb.size() == 0);
  assert(cb.capacity() == 5);
  assert(cb.empty());
  assert(cb.max_size() > 0);
}

Right now, there's not much more we can do to the buffer. But that's all set to change...