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

Time to air the dirty laundry, and — since every good metaphor must run to the bitter end — to ask a pantomime washer woman to save the day. Or something like that.

In part 6 we identified some serious object management issues with the existing circular_buffer design. Now we understand them, we'll learn how to fix them, and how to use a C++ allocator. This whole sordid tale will show us exactly how useful allocators are.

What is an allocator?

All STL containers take an allocator as a template parameter. The allocator is an abstraction used to allocate and free memory for items held in the container. The allocator interface is described in section 20.1.5 of the C++ standard.

An allocator is itself templated over the type of object it can allocate space for. Every STL container defaults the allocator template parameter to std::allocator, the standard C++ allocator which employs new and delete. You'll rarely specify an allocator by hand in day-to-day C++ code. The std::allocator class is described in section 20.4.1 of the standard.

The allocator interface is pretty straightforward. An allocator provides a number of typedefs, identical to those required of a container:

• value_type
• pointer
• const_pointer
• reference
• const_reference
• size_type
• difference_type

It provides a number of methods, including:

size_type max_size(); // Same as a container

// Allocate memory. The second parameter is an optional "hint"
// to the allocator, the address of the object allocated prior to
// this allocation.
pointer allocate(size_type,
          typename std::allocator<void>::const_pointer = 0);

// Relinquish allocated memory
void deallocate(pointer p, size_type);

// Construct an object at this (allocated) memory location
void construct(pointer p, const T &t);

// Destruct the object that was constructed in this memory location
void destroy(pointer p);

allocate and deallocate, as their names suggest, service requests for memory allocation or deallocation. More interestingly, construct and destroy are used to vivify an object in already-allocated memory (the memory must have originally come from this allocator). The default implementations employ placement new and invoke the object's destructor in place, as below:

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

That's the kind of C++ you'll very, very rarely write, but that is worth understanding all the same.

Adding the allocator to circular_buffer

So let's thread an allocator through our circular_buffer. The first step, naturally, is to add a new template parameter to the class. We'll default this to std::allocator, which will suit 99% of all users.

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
    // ...

Since the allocator provides a host of useful typedefs related to the object it allocates, we can refine our class' definitions accordingly:

 typedef T                                        value_type;
typedef A                                        allocator_type;
typedef circular_buffer<T,A>                     self_type;
typedef typename allocator_type::difference_type difference_type;
typedef typename allocator_type::reference       reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer         pointer;
typedef typename allocator_type::const_pointer   const_pointer;

We also extend the constructor to take an explicit allocator object (and supply a sensible default), and add get_allocator to retrieve it.

explicit circular_buffer(size_type capacity,
                        const allocator_type &a = allocator_type());
allocator_type get_allocator() const;

We'll need to hold a copy of the allocator alongside the other private data members. But more importantly, we must use the it to allocate the memory for m_buffer and to delete it again afterwards. The boost::scoped_array (which seemed like such a good idea at the time) goes, and we must therefore add a corresponding custom destructor, too.

public:
  ~circular_buffer();

private:
  size_type      m_capacity;
  allocator_type m_allocator;
  pointer        m_buffer;
  pointer        m_front;
  pointer        m_back;

The updated method implementations look like this:

template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
    (size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
m_allocator(allocator),
m_buffer(m_allocator.allocate(capacity)),
m_front(0),
m_back(m_buffer)
{
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
  clear(); // Delete all objects before deallocating the buffer
  m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
typename circular_buffer<T,A>::allocator_type
inline
circular_buffer<T,A>::get_allocator() const
{
  return m_allocator;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
  // This is clearly more elegant than the previous implementation!
  return m_allocator.max_size();
}

// This version of push_back must constuct and detroy objects in m_buffer
// using m_allocators methods, rather than traditional construction, copying,
// assignment.
template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
  // If the buffer is full, and data will fall off the back of the
  // buffer - so we must destroy the stale object first.
  // This is an implementation choice, we could instead use operator= on
  // the value_type to replace the item. However, that would require
  // value_type to provide a copy assignment operator.
  if (m_front && m_front == m_back)
      m_allocator.destroy(m_back);

  m_allocator.construct(m_back, value);

  // The rest of push_back is as it was before
  value_type *const next = wrap(m_back+1);
  if (!m_front)
  {
      // first entry in the buffer
      m_front = m_back;
      m_back = next;
      return true;
  }
  else if (m_front == m_back)
  {
      // buffer is full already, throw something away
      m_front = m_back = next;
      return false;
  }
  else
  {
      m_back = next;
      return true;
  }
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
  assert(m_front);

  m_allocator.destroy(m_front);
  value_type *const next = wrap(m_front+1);
  if (next == m_back)
      m_front = 0;
  else
      m_front = next;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
  if (m_front)
  {
      do
      {
          m_allocator.destroy(m_front);
          m_front = wrap(m_front+1);
      }
      while (m_front != m_back);
  }
  m_front = 0;
}

That's everything that needs substantial change. Every other existing method definition gains an additional template parameter (but ignores it). Oh, and wrap() needs the ".get()"s striped from the m_buffer address lookups.

That's it.

We've fixed some nasty, subtle bugs and taken one step closer to STL perfection.

Next time: We begin to iterate. And then we iterate. And then we iterate. And then we...