Saturday, 22 November 2008

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

We now have a circular_buffer that you can add data to, read data from, remove data from, and that seems superficially correct. Let's add one extra method, clear(), and then start fretting.


We can quite easily add clear(), a method that removes all the data from the buffer. (This is what many programmers initially confuse the empty() method for. Obviously empty is a question, and clear is a command. Go figure)
template <typename T>
void circular_buffer<T>::clear()
m_front = 0;
That's simple enough, isn't it? We can make the buffer think it is empty again by simply resetting the m_front pointer. Let's test...
  circular_buffer<int> cb(5);

assert(cb.size() == 3);
assert(cb.capacity() == 5);
assert(cb.front() == 7);

assert(cb.size() == 0);
assert(cb.capacity() == 5);
Success. Hurray.

Falling from grace

However, we've ignored the elephant for long enough. This method is the straw that broke the elephant's back. What happened to all the data that was in the buffer? So far, we've only tested with ints, so nothing interesting has happened at all.

But what if you want a circular_buffer of a large user-defined class, Foo? This is what is going to happen:
  • The constructor will allocate an array of m_capacity default-constructed Foos. If there isn't a default constructor then constructing the circular_buffer will not compile. An empty buffer should not have constructed anything.
  • push_back replaces Foo objects in the array with Foo's assignment operator
  • pop_back does not destruct the Foo being removed
  • empty does not destruct the Foos that have been put in the buffer
That's not ideal. In fact, it's downright incorrect. Here's a little illustration to prove the point; at the end of IllustrateTheProblem you would have expected no TheProblem objects to have been constructed.
  struct TheProblem
static size_t constructed;
TheProblem() { ++constructed; }

size_t TheProblem::constructed = 0;

void IllustrateTheProblem()
assert(TheProblem::constructed == 0);
circular_buffer<TheProblem> bufer(5);
assert(TheProblem::constructed == 0); // this fails
There, we've said it. It's out in the open. We'll address this problem when we add allocators to the class design.

No comments: