Circular Buffer C++11 Implementation

Question

Here's the implementation of a common data structure I use at work, mainly for logging purposes.

I tried to make it C++11-compliant, but even if this standard has been around for a few years, it is still quite new to me since I play with it only in my spare time (locked on VS2010 at work, which has a poor implementation of then-so-called C++0X.)

So, feel free to criticize and, hopefully, suggest some improvement; I'm especially interested in exception safety and correct implementation of move semantics (other than code style, performance issues and so on...)

I know it is still a naive implementation, so I intentionally avoided allocators and iterators by now, but...dont't be shy if you have something in mind.

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <algorithm>
#include <cstddef>
#include <cassert>
#include <stdexcept>
#include <iostream>

template <typename T>
class CircularBuffer
{
public:
    typedef size_t size_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T* pointer;
    typedef const T* const_pointer;

    explicit CircularBuffer(size_type capacity);
    CircularBuffer(const CircularBuffer<T> &rhs);
    CircularBuffer(CircularBuffer<T>&& rhs);
    ~CircularBuffer() { if (_buffer) delete[] _buffer; }

    CircularBuffer<T>& operator=(CircularBuffer<T> rhs);

    size_type size() const { return (_full ? _capacity : _front); }
    size_type capacity() const { return _capacity; }
    bool is_full() const { return _full; }

    const_reference operator[](size_type index) const;
    reference operator[](size_type index);

    void add(T item);
    void resize(size_type new_capacity);

    friend void swap(CircularBuffer<T> &a, CircularBuffer<T> &b)
    {
        std::swap(a._buffer, b._buffer);
        std::swap(a._capacity, b._capacity);
        std::swap(a._front, b._front);
        std::swap(a._full, b._full);
    }

private:
    pointer _buffer;
    size_type _capacity;
    size_type _front;
    bool _full;

    CircularBuffer();
};

template<typename T>
CircularBuffer<T>::CircularBuffer()
    : _buffer(nullptr)
    , _capacity(0)
    , _front(0)
    , _full(false)
{
}

template<typename T>
CircularBuffer<T>::CircularBuffer(size_type capacity)
    : CircularBuffer()
{
    if (capacity < 1) throw std::length_error("Invalid capacity");

    _buffer = new T[capacity];
    _capacity = capacity;
}

template<typename T>
CircularBuffer<T>::CircularBuffer(const CircularBuffer<T> &rhs)
    : _buffer(new T[rhs._capacity])
    , _capacity(rhs._capacity)
    , _front(rhs._front)
    , _full(rhs._full)
{
    std::copy(rhs._buffer, rhs._buffer + _capacity, _buffer);
}

template<typename T>
CircularBuffer<T>::CircularBuffer(CircularBuffer<T>&& rhs)
    : CircularBuffer()
{
    swap(*this, rhs);
}

template<typename T>
typename CircularBuffer<T>::const_reference
CircularBuffer<T>::operator[](size_type index) const
{
    static const std::out_of_range ex("index out of range");
    if (index < 0) throw ex;

    if (_full)
    {
        if (index >= _capacity) throw ex;
        return _buffer[(_front + index) % _capacity];
    }
    else
    {
        if (index >= _front) throw ex;
        return _buffer[index];
    }
}

template<typename T>
typename CircularBuffer<T>::reference 
CircularBuffer<T>::operator[](size_type index)
{
    return const_cast<reference>(static_cast<const CircularBuffer<T>&>(*this)[index]);
}

template<typename T>
CircularBuffer<T>& 
CircularBuffer<T>::operator=(CircularBuffer<T> rhs)
{
    swap(*this, rhs);
    return *this;
}

template<typename T>
void 
CircularBuffer<T>::add(T item)
{
    _buffer[_front++] = item;
    if (_front == _capacity) {
        _front = 0;
        _full = true;
    }
}

template<typename T>
void 
CircularBuffer<T>::resize(size_type new_capacity)
{
    if (new_capacity < 1) throw std::length_error("Invalid capacity");
    if (new_capacity == _capacity) return;

    size_type num_items = size();
    size_type offset = 0;
    if (num_items > new_capacity)
    {
        offset = num_items - new_capacity;
        num_items = new_capacity;
    }

    pointer new_buffer = new T[new_capacity];
    for (size_type item_no = 0; item_no < num_items; ++item_no)
    {
        new_buffer[item_no] = (*this)[item_no + offset];
    }

    pointer old_buffer = _buffer;

    _buffer = new_buffer;
    _capacity = new_capacity;
    _front = (num_items % _capacity);
    _full = (num_items == _capacity);

    delete[] old_buffer;
}

#endif // CIRCULAR_BUFFER_H

Answer 1

Exception safety

Let's look at the copy constructor:

template<typename T>
CircularBuffer<T>::CircularBuffer(const CircularBuffer<T> &rhs)
    : _buffer(new T[rhs._capacity])
    // ...
{
    std::copy(rhs._buffer, rhs._buffer + _capacity, _buffer);
}

What will happen if std::copy (read T's copy constructor/assignment operator) throws? Right, a memory leak - CircularBuffer won't get constructed, its' destructor will not be called, and the memory allocated for _buffer will be lost.

To avoid this issue, consider using something RAII'ish for your _buffer (as Loki Astari mentioned, std::vector might be a good choice) . Or simply wrap std::copy in a try block and delete[] your _buffer in a catch-handler.

Logic errors

if (index < 0) throw ex;

Your index is unsigned, it cannot be less than zero.

Style and usability

Consider using default member initializers and explicitly deleting your default constructor:

template <typename T>
class CircularBuffer
{
public:
    CircularBuffer() = delete;
    // ...
private:
    pointer _buffer = nullptr;
    size_type _capacity = 0;
    size_type _front = 0;
    bool _full = false;
};

Doing this will clean up your code a bit and will clearly state that your CircularBuffer is not default-constructible.

Answer 2

Rather than implement all the memory management yourself use an existing container and just implement the circular part yourself.

template <typename T>
class CircularBuffer
{
    std::vector<T>  buffer; // maybe there is a better one
    ...                     // I would think on this a bit.

The main reason is that std::vector will not construct the elements that are not used. Yours on the other hand default constructs all the elements in _buffer. If T is not default constructible this is a problem. If T is expensive to default construct this is a problem.

Move

The move operators should usually be marked as noexcept

CircularBuffer(CircularBuffer<T>&& rhs) noexcept;
// Also you should probably have an explicit move assignment.
CircularBuffer<T>& operator=(CircularBuffer<T>&& rhs) noexcept;

Swap

I normally implement the function swap in terms of a member function swap that I mark as noexcept (because the move operators usually need swap and they need it to be noexcept).

friend void swap(CircularBuffer<T>& lhs, CircularBuffer<T>& rhs)
{
    lhs.swap(rhs);
}

Swap is one of those rare places that you should use using std::swap.

void swap(CircularBuffer<T>& rhs)
{
    using std::swap;
    swap(_buffer,   rhs._buffer);
    swap(_capacity, rhs._capacity);
    swap(_front,    rhs._front);
    swap(_full,     rhs._full);
}

The reason for this is if you change the types of your members (possibly to some custom type) then the swap() function continues to work without modification.

Design

Not really a circular buffer as there is no back or front concept implemented here.

Answer 3

To expand on Loki's comment "Not really a circular buffer as there is no back or front concept implemented here." I have attached a small section of some JavaScript code implementing a dynamic start/end (front/back) that was very useful to me (my head hurts when dealing that kind of "math")

You can learn a-lot about the sneaky ways in which to handle circular buffers by examining this JavaScript code (not mine, only excerpt attached). Ignoring the fact that it's JavaScript, it is an excellent example of how to have a dynamic start and end index, such that if your circular buffer is set to have a size of 10, only indexes 0 through 9 will ever be used.

Note, this also implements an optional callback (this.overflow) which is called when an element is about to removed from the buffer.

/**
 * a circular bufffer
 * @class
 */
function CBuffer() {
    this.size = this.start = 0;
    // set to callback fn if data is about to be overwritten
    this.overflow = null;
    // emulate Array based on passed arguments
    if (arguments.length > 1 || typeof arguments[0] !== 'number') {
        this.data = new Array(arguments.length);
        this.end = (this.length = arguments.length) - 1;
        this.push.apply(this, arguments);
    } else {
        this.data = new Array(arguments[0]);
        this.end = (this.length = arguments[0]) - 1;
    }
    // need to `return this` so `return CBuffer.apply` works
    return this;
}


/** @typedef {*} item */

CBuffer.prototype = {
    // properly set constructor
    constructor : CBuffer,

    /* mutator */

    /**
     * pop last item
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    pop: function () {
        var item;
        if (this.size === 0) return void 0;
        item = this.data[this.end];
        // remove the reference to the object so it can be garbage collected
        delete this.data[this.end];
        this.end = (this.end - 1 + this.length) % this.length;
        this.size--;
        return item;
    },
    /**
     * push item to the end
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    push: function () {
        var i = 0;
        // check if overflow is set, and if data is about to be overwritten
        if (this.overflow && this.size + arguments.length > this.length) {
            // call overflow function and send data that's about to be overwritten
            for (; i < this.size + arguments.length - this.length; i++) {
                this.overflow(this.data[(this.end + i + 1) % this.length], this);
            }
        }
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for (i = 0; i < arguments.length; i++) {
            this.data[(this.end + i + 1) % this.length] = arguments[i];
        }
        // recalculate size
        if (this.size < this.length) {
            if (this.size + i > this.length) this.size = this.length;
            else this.size += i;
        }
        // recalculate end
        this.end = (this.end + i) % this.length;
        // recalculate start
        this.start = (this.length + this.end - this.size + 1) % this.length;
        // return number current number of items in CBuffer
        return this.size;
    },
    remove: function(predicate, options) {
        options = _.defaults(options, {
            // whether to quash notification via callback of removal
            silent: false, 
        });
        var newData = this.slice();
        var removed = _.remove(newData, predicate);
        this.fill(null); // delete references
        this.data = _.merge(this.data, newData);
        this.start = 0;
        this.size = newData.length;
        this.end = this.size - 1;
        if (!options.silent) {
            for (var i = 0, len = removed.length; i < len; ++i) {
                this.overflow(removed[i], this);
            }
        }
        return removed;
    },
    torray: function (start, end) {
        var length = this.size;

        start = Number(start) || 0;

        if (start < 0) {
            if (start >= end)
                return [];
            start = (-start > length) ? 0 : length + start;
        }

        if (end == null || end > length)
            end = length;
        else if (end < 0)
            end += length;
        else
            end = Number(end) || 0;

        length = start < end ? end - start : 0;

        var result = Array(length);
        for (var index = 0; index < length; index++) {
            result[index] = this.data[
                (this.start + start + index)
                % this.length
            ];
        }
        return result;
    }