Circular Buffer Container Class

C++ comes with a set of templatized container classes so developers don't have to re-implement a doubly linked list or balanced binary tree class for every project. This is a tremendous time-saver you may not appreciate unless you've had to live without. It can also be a trap that limits performance.

The roster of container classes in the standard library is thin; there are three kinds of sequence container (vector/array/string, deque, list/forward_list), and two kinds of associative container (map/multimap/set/multiset, unordered_map/unordered_multimap/unordered_set/unordered_multiset). With such limited choice, a developer who needs a container with specific behavior may be forced to accept a lot of unwanted implementation baggage.

By giving up the ability to access the sequence as a C-style array, it is possible to obtain a container that is about as fast as std::vector, but supports constant-time insertion and removal from both ends. One variation of this container is the circular buffer. Work to standardize the circular buffer is underway, and in the meantime boost has a version. The circular buffer makes a great queue data structure.

I ran boost::circular_buffer through the performance tests for sequence containers from my book Optimized C++. Here is a link to a long article reporting the results.

Only one new kind of container (the unordered associative container) has been added to C++ since 1995 when the Standard Template Library was introduced. There is a lot of interest from communities with performance issues in adding additional container classes to future versions of C++.