Tuesday, 18 November 2008

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!


Anonymous said...

Also note that there is an implementation of a STL-like circular buffer in boost, see http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html

Pete Goodliffe said...

Indeed. There are, in fact, many C++ implementations of a circular buffer floating round on the net, many of which pre-date the boost library (circular_buffer was added to Boost in version 1.35.0).

However, it would make a fairly boring series to just point at the boost library and stop there :-)

I've chosen circular buffers for this exercise as it's a meaty enough data structure to provide some real interest, whilst not being too complex to understand.

Anonymous said...

Why was there no follow on bankruptcy then? The bailout of AIG FP went to (wow power leveling) hedge funds that bound credit swaps on Lehman failing or others betting on rating (wow power leveling) declines. AIG has drained over 100 billion from the government. Which had to go to (wow power leveling) those who bet on failures and downgrades. Many of whom (power leveling)were hedge funds. I-banks that had offsetting swaps needed the money from the AIG bailout or they would have been caught. Its an (wow powerleveling) insiders game and it takes just a little bit too much time for most people to think (wow gold) through where the AIG 100 billion bailout money went to, hedge funds and players, many of whom hire from the top ranks of DOJ, Fed, Treasury, CAOBO