constant sized circular (ring) buffer

Question

I've implemented constant sized circular buffer. It provides push and pop operations, along with modern emplace. It is also optimized for destruction of trivially destructible types.

I didn't include iterators since it would be strange to have one pair of begin and end for input iterators and other for output iterators. Allocator support will come in the next version.

I'd like the review to focus on performance of push (emplace) and pop operations. Also, there is a code duplication in those functions. Should I leave just emplace?

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <cstddef>
#include <utility>

template <typename T, std::size_t mcapacity>
class circular_buffer
{
    T* data;
    T* begin;
    T* end;
    std::size_t msize;
    bool is_empty;

    template <bool trivially_destructible>
    struct destructor
    {
        void destroy(T* object)
        {
            object->~T();
        }

        void destroy_n(T* objects, std::size_t sz)
        {
            for (std::size_t i = 0; i < sz; ++i)
            {
                objects->~T();
                ++objects;
            }

            ::operator delete(objects);
        }
    };

    template <>
    struct destructor<true>
    {
        void destroy(T* object)
        {
            //empty, since trivially destroyable
        }

        void destroy_n(T* objects, std::size_t sz)
        {
            ::operator delete(objects);
        }
    };

    destructor<std::is_trivially_destructible<T>::value> destroyer;

public:
    using container = circular_buffer<T, mcapacity>;
    using value_type = T;
    using reference = value_type&;
    using pointer = T*;
    using const_reference = const reference;
    using size_type = std::size_t;

    circular_buffer(): 
        data((pointer)::operator new(sizeof(value_type) * mcapacity)),
        msize(0),
        begin(data),
        end(data)
    {}

    template <typename ... ArgTypes>
    void emplace(ArgTypes ... args)
    {
        end = new (end) T(args...);
        ++end;
        if (end == data + mcapacity)
        {
            end = data;
        }

        if (msize != mcapacity)
        {
            ++msize;
        }
    }

    void push(const T& value)
    {
        end = new (end) T(value);
        ++end;
        if (end == data + mcapacity)
        {
            end = data;
        }

        if (msize != mcapacity)
        {
            ++msize;
        }
    }

    void push(T&& value)
    {
        end->T(value);
        ++end;
        if (end == data + mcapacity)
        {
            end = data;
        }

        if (msize != mcapacity)
        {
            ++msize;
        }
    }

    const_reference front()
    {
        return *begin;
    }

    void pop()
    {
        destroyer.destroy(begin);
        ++begin;
        if (begin == data + mcapacity)
        {
            begin = data;
        }

        if (msize != 0)
        {
            --msize;
        }
    }

    size_type size()
    {
        return msize;
    }

    constexpr size_type capacity()
    {
        return mcapacity;
    }

    bool full()
    {
        return msize == mcapacity;
    }

    bool empty()
    {
        return msize == 0;
    }

    ~circular_buffer()
    {
        destroyer.destroy_n(data, mcapacity);
    }
};

#endif

Sample usage:

#include "circular_buffer.h"
#include <vector>
#include <iostream>

int main()
{   
    circular_buffer<int, 10> buffer;

    for (int i = 0; i < 30; ++i)
    {
        buffer.push(i);
    }

    std::cout << buffer.full() << '\n'
        << buffer.empty() << '\n';

    for (int i = 0; i < 20; ++i)
    {
        std::cout << buffer.front() << ' ';
        buffer.pop();
    }

    std::cout << buffer.full() << '\n'
        << buffer.empty() << '\n';
}

Answer 1

Type aliases

• The container alias is never used, it can be removed.
• The const_reference alias is wrong, it is still an alias to T&.
• Use a consistent aliasing scheme, only use T when aliasing value_type.
• Provide a const_pointer alias.

With these points in mind, your type aliases become:

using value_type = T;
using reference = value_type&;
using const_reference = value_type const&; // is now actually reference-to-const alias
using pointer = value_type*; // use value_type alias
using const_pointer = value_type const*; // for iterators, casting, etc.
using size_type = std::size_t;

Consider the rule of 5 when your class manages a resource.

Whenever your class manages a resource, it probably needs to implement the destructor, copy and move operations. You definitely do not want pointers to be copied when a copy of circular_buffer<> is made. Possible issues:

• Memory being freed twice.
• Dangling references.
• Invalid object states.

Use static memory when the size is known at compile-time.

This will be more efficient and exception-free during allocation. Possible replacement:

#include <type_traits>
std::aligned_storage_t<mcapacity * sizeof( T ), alignof( T )> data;

Now that you are using static memory, you can provide two private functions to avoid having to use ugly casts everywhere:

T* data() { return reinterpret_cast<T*>( &data ); }
T const* data() const { return reinterpret_cast<T const*>( &data ); }

Your constructor becomes:

circular_buffer() noexcept /* no exceptions with static memory allocation */ :
    /* members reordered to match class */
    begin( data() ),
    end( begin ),
    msize( 0 ),
    is_empty( false )
{}

• We now explicitly initialize is_empty in the constructor initializer list. I think this is clearer.
• To avoid weird bugs, members are initialized in the same order that they are declared in the class.
• If your class needs really big chunks of memory that aren't available statically, then don't make the capacity a template parameter: make it a constructor parameter.

Use universal references in the definition of emplace().

This avoids unnecessary copying of arguments. Replacement:

template <typename... ArgTypes>
void emplace( ArgTypes&&... args ); // variadic template of universal references

This change requires that we also perfect-forward these universal references wherever they may be used:

T{ std::forward<ArgTypes>( args )... }; // perfect-forward example

Use std::move() when you're finished with rvalue arguments.

In push( T&& ), argument value is actually used as an T const& (which calls the copy constructor) because you forget to call std::move(). The fix is simple:

end->T( value );

Becomes:

end->T( std::move( value ) );

Factor out repeated code.

Your push() overloads and emplace() have the exact same block of code being repeated; this block is a prime candidate for being extracted into a private function:

void tidy() noexcept // feel free to use a descriptive function name
{ // the repeating block of code
    ++end;

    if ( end == data + mcapacity )
        end = data;

    if ( msize != mcapacity )
        ++msize;
}

After modifications, emplace() and push() now look like this:

template <typename... ArgTypes>
void emplace( ArgTypes&&... args )
{
    ::new ( end ) T( std::forward<ArgTypes>( args )... );
    tidy();
}

void push( T const& value )
{
    ::new ( end ) T( value );
    tidy();
}

void push( T&& value )
{
    ::new ( end ) T( std::move( value ) );
    tidy();
}

Note the consistent use of the same construction approach (placement-new) which looks nice and prevents syntax issues with primitive types.

Mark functions as noexcept when appropriate.

Non-throwing functions of yours include size(), capacity() and a few more. This will help programmers know that certain functions do not throw, which can help with optimizations.

For compile-time conditional noexcept marking, use type traits. Here's a sample:

template <typename... ArgTypes>
void emplace( ArgTypes&&... args )
noexcept( std::is_nothrow_constructible<T, ArgTypes&&...>::value )
{ /* ... */ }

Mark non-modifying functions as const.

const functions of yours include front(), size() and a few more. Member functions that don't modify any of the class data members should be marked as const so that they can be used in the appropriate scenario (accessed through a circular_buffer<> const&).

Answer 2

I haven't looked at the whole code in detail, however two things stood out.

push

Because of the nature of the list, I can't help but wonder if push should return a value to indicate that it's started overwriting existing items. This could be useful if the client decided it needed to slow down when this occurred.

copy bug

Because you're using raw pointers in the buffer, you want to make sure you protect them. At the moment, you can cause issues if you assign one instance of the buffer to another one.

circular_buffer<int, 10> buffer2 = buffer;

At a minimum you probably want to do (although you might want to copy the buffer instead...):

circular_buffer(const circular_buffer &) = delete;
circular_buffer &operator=(const circular_buffer&) = delete;

---

Compilation Error

Template code often isn't resolved until after you exercise it. I'm not really sure if you code is supposed to support this or not (I'm not overly familiar with some of the newer standards), however if I use an std::stack, then I can do this and it works ok:

std::stack<float> buffer;
for (int i = 0; i < 30; ++i)
{
    buffer.push(float(i));
}

With your code, it fails to compile:

circular_buffer<float, 10> buffer;
for (int i = 0; i < 30; ++i)
{
    buffer.push(float(i));
}

If fails because it's going into the alternate version of push:

end->T(value);

error: request for member ‘T’ in ‘((circular_buffer)this)->circular_buffer::end’, which is of non-class type ‘float’

If I compile with g++ (g++ -std=c++14 CPPConsoleApp.cpp), I also get other compilation errors...

 CPPConsoleApp.cpp:114:15: error: explicit specialization in non-namespace scope ‘class circular_buffer<T, mcapacity>’
      template <>
                ^
 CPPConsoleApp.cpp:115:12: error: template parameters not deducible in partial specialization:
      struct destructor<true>
            ^
 CPPConsoleApp.cpp:115:12: note:         ‘T’
 CPPConsoleApp.cpp:115:12: note:         ‘mcapacity’
 CPPConsoleApp.cpp:146:10: error: too many template-parameter-lists
      void emplace(ArgTypes ... args)

Const correctness

Some of your methods (size, capacity etc) don't modify the class, so could be declared const.