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

This is the first in a series of postings that will walk through the process of writing a C++ STL-like container. Specifically, we're going to look at the implementation of a circular buffer in C++.

In this first part we'll cover a little introductory ground.

What is a circular buffer?

A circular buffer is a fixed size data structure that presents its storage space as one long continuous buffer. The internal store effectively wraps around itself internally (circularly, hence the name).

Because of the internal data storage scheme, a circular buffer only lends itself to pushing a block of data onto the front of the buffer, and pulling a block of data from the back of buffer. It specifically will not support insertion in the middle of the data, and needn't support random access, either. Typically, circular buffers are FIFO.

Once the internal data store is full, a circular buffer implementation could either choose to:

• not accept any more data until the buffer is emptied, or to
• accept any amount of data, silently overwriting the older data with the new data.

Like a fixed-size array, you always know how much space a circular buffer will occupy - a useful property in many applications, and an possible advantage over a std::vector. It also has fixed performance characteristics.

A circular buffer is often employed in producer-consumer scenarios, where one component supplies data and another asynchronously consumes that data. We commonly see this pattern in multimedia and communications applications.

Why would you want an STL-like circular buffer?

So why would you specifically write an STL-like implementation of a circular buffer in C++?

1. Interoperability. Any container that subscribes to the STL's interface can be used seamlessly with existing C++ algorithms (either those in the std namespace supplied in the C++ standard library, or other third-party STL-like algorithms, like those in the Boost library).
   
2. Discoverability. If your container has an STL-like interface then C++ programmers will be easily able to pick it up and work with it. Sure, they'll have to understand its specific performance characteristics, and to which situations it is particularly suited (as you do with any C++ container). But an STL-like container will be easy to learn, and also easy to understand in order to modify.
3. Good taste. The STL is the benchmark for good C++ library design. Sure, there are a few oddnesses and warts in there. No library is perfect. But it's a generally well thought out, and carefully constructed beast. There's a lot to be said for fitting into its world view.
4. Reusability. Resuse is often a shadow that programmers chase unnecessarily. However, in most cases giving a simple container an STL-like interface, rather than a very application-specific interface will allow you to use it in more than one situation; a small sliver of a silver bullet, if ever there was one.
   
5. Learn the inner workings of the STL. And if you're really bored, here's another great reason to write your own STL-like container: If you want to understand how the STL really works, how to extend it, and how to use it like a master then there's nothing better than writing your own STL code.

Hopefully that's a compelling list of reasons.

In the next posting, I'll launch into some C++. Buckle your std::seatbelts!