YACB - Yet Another Circular Buffer #

Circular buffers, next to producer/consumer queues, are one of those data structures that have been forever in the arsenal of every programmer. What is surprising, is that there is no standard implementation in C++ standard library. There is a circular buffer in Boost but, like many Boost things, it is fairly large and not that easy to integrate in other projects. The implementation shown in this article wants to be small and easy to use.

Photo by: James Taylor via Unsplash

Background #

A circular, or ring buffer, is a container of a fixed size. When the container is full and a new element is added to it, the oldest element is discarded. Traditionally ring buffers are implemented as a pre-allocated memory area together with a couple of pointers or indexes that keep track of the insertion point (back) and extraction point (front):

The pointers must wrap around at the end of the memory area. One solution for reducing the computations required for this wrap around is to have a buffer whose size is a power of 2 and simply truncate the indexes. For example, if the buffer size is 256, the indexes can be kept as 8-bit integers and wrap around is automatic. This was a popular solution in the days of assembler when memory was expensive and CPU cycles valuable.

The two pointers can be equal either when the buffer is empty or when the buffer is completely full:

There are different mechanisms for distinguishing between the two cases. The obvious solution is to keep also a count of the number of elements in buffer. Another solution is to always keep an empty space in the buffer. In this case, if after an insertion the two pointers would become equal, that means the buffer is full and the extraction pointer is also advanced.

Usage #

The only file required is the ringbuf.h header file. The circular buffer structure is implemented as the ring_buffer¹ class. This is a plain vanilla implementation that doesn’t use any of the smart techniques mentioned before. It is a container class and the access methods are modelled on the std::queue class.

Constructors #

    ring_buffer ()                                            [1]
    ring_buffer (size_t sz)                                   [2]
    ring_buffer (std::initializer_list<T> il)                 [3]
    ring_buffer (const ring_buffer<T>& other)                 [4]

[1] is the default constructor that creates an empty buffer with capacity 0.
[2] is the normal constructor that creates a buffer with capacity sz. Keep in mind that, once allocated, the buffer size can be changed only by calling the resize function.
[3] is another constructor that accepts an initializer list. This allows you to write something like:

  ring_buffer<int> my_buffer ({100, 101, 102});

[4] is the copy constructor that creates a copy of an existing buffer. There is also an assignment operator:

    ringbuf& operator= (const ringbuf& rhs)

It can be used like in this example:

    ringbuf<int> b1;            //empty
    ringbuf<int> b2(5);         //b2 capacity is 5

    b1 = b2;                    //now b1 has capacity of 5

Data Insertion and Extraction #

To add an object to circular buffer you call the push_back function:

    void push_back (const T& item)

The element can be accessed using the back function:

    T& back ()

The oldest element in buffer can be accessed using the front function:

    T& fron ()

And can be removed from buffer using the pop_front function:

    void pop_front ()

Iterators #

Any well-behaved container must implement some iterators. In our case, ring_buffer implements a bidirectional iterator in two flavors: const and non-const. The usual functions begin and end return those iterator objects:

    iterator begin ();
    const_iterator begin () const;
    const_iterator cbegin ();

    iterator end ();
    const_iterator end () const;
    const_iterator cend ();

The iterator objects provide all the expected functions: increment, decrement, addition, subtraction, comparison.

With these elements now we can write something like this:

    ring_buffer<string> container = {"abc", "def", "ghi"};
    for (auto p = container.begin(); p != container.end(); p++)
        cout << *p << ' ';

Or even better:

    ring_buffer<string> container = {"abc", "def", "ghi"};
    for (auto p : container)
        cout << p << ' ';

More functions #

In addition to the functions described before, there are just a few more functions in the ring_buffer class:

• empty() checks if the buffer is empty
• clear() removes all elements from the buffer
• capacity () returns the buffer capacity
• resize (size_t n) changes the buffer capacity

One particular note for the vector conversion operator: this allows you to transfer the buffer content into a standard vector where elements are ordered from the oldest to the newest. For instance:

  ring_buffer<string> b{ "first", "second", "third" };
  b.pop_front ();
  b.push_back ("fourth");       //b conatins (from newest) "fourth", "third", "second"
  v = b6;                       //v[0]="second", v[1]="third", v[2]="fourth"

Implementation Notes #

The ring_buffer data is stored as a classical C array, albeit wrapped in a unique_ptr to make it easier to manage. In addition to the data array, the class contains the front and back indexes and size information.

To avoid code duplication between the const and non-const versions of the iterators, they are implemented using a template with a bool parameter. The const version of the iterator is instantiated with the parameter set to true while the non-const is instantiated with the parameter set to false.

  template <bool C_>
  class iterator_type
  {
  //...
  }

  typedef iterator_type<false> iterator;
  typedef iterator_type<true> const_iterator;

Performance #

I included a performance test inspired by the article Performance of a Circular Buffer vs. Vector, Deque, and List. It creates a number of random key-value pairs, shuffles them to a random order and then inserts them in different containers. On my machine results are like these:

Random vector prepared in 1328ms
ring_buffer push_back of 10000000 elements in 74ms
size is 156250kb
vector push_back of 10000000 elements in 316ms
vector with reserve push_back of 10000000 elements in 97ms
list push_back of 10000000 elements in 575ms
ring to vector conversion of 10000000 elements in 97ms

Pushing 156MB in a vector without pre-allocating memory takes about 316ms. The time drops to only 97ms if the vector pre-allocates memory (using reserve function). Our ring_buffer is still a bit faster at only 74ms. Converting from ring buffer to vector takes also about the same time as filling a pre-allocated vector. This is not surprising as, internally, the vector conversion operator does exactly that: pre-allocates and fills a vector.

Show me teh codez #

The code is on GitHub as part of mlib library. For the performance test, see the unit test program.

Footnotes #