Ring Buffer Implementation in C++14

Question

A ring buffer or circular buffer is a fixed sized queue that advances head and tail pointers in a modulo manner rather than moving the data. Ring buffers are often used in embedded computer design.

This implementation of a c++14 compatible Ring Buffer that was inspired by a Pete Goodliffe's ACCU article and the Chris Riesbeck web page.

As a hobbyist programmer, I started this project so I could learn some more about using templates. I intentionally avoided allocators since I don’t fully understand them (yet). I also did not attempt “emplace_back” for the same reason, but would love to learn about this. I used default copy/move constructors. Any suggestions or feedback that I can get about style, design and completeness of class will be appreciated. I believe that the iterator is basically STL compatible, but I would enjoy feedback on this aspect of the project as well.

#pragma once
#include <iostream>
#include <exception>
#include <cassert>
#include <vector>
#include <initializer_list>


template <class T>
class ring
{
    using value_type = T;
    using reference = T & ;
    using const_reference = const T &;
    using size_type = size_t;
    using circularBuffer = std::vector<value_type>;

    circularBuffer m_array;
    size_type m_head;
    size_type m_tail;
    size_type m_contents_size;
    const size_type m_array_size;
public:

    ring(size_type size = 8) : m_array(size),
        m_array_size(size),
        m_head(1),
        m_tail(0),
        m_contents_size(0) {
        assert(m_array_size > 1 && "size must be greater than 1");
    }
    ring(std::initializer_list<T> l) :m_array(l),
        m_array_size(l.size()),
        m_head(0),
        m_tail(l.size() - 1),
        m_contents_size(l.size()) {
        assert(m_array_size > 1 && "size must be greater than 1");
    }

    template <bool isconst> struct my_iterator;
    reference front() { return m_array[m_head]; }
    reference top() { return front(); }
    reference back() { return m_array[m_tail]; }
    const_reference front() const { return m_array[m_head]; }
    const_reference back() const { return m_array[m_tail]; }
    void clear();
    void push_back(const value_type &item);
    void push(const value_type &item) { push_back(item); }
    void pop_front() { increment_head(); }
    void pop() { pop_front(); }
    size_type size() const { return m_contents_size; }
    size_type capacity() const { return m_array_size; }
    bool empty() const;
    bool full() const;

    size_type max_size() const { return size_type(-1) / sizeof(value_type); }
    reference operator[](size_type index);
    const_reference operator[](size_type index) const;
    reference at(size_type index);
    const_reference at(size_type index) const;

    using iterator = my_iterator<false>;
    using const_iterator = my_iterator<true>;
    iterator begin();
    const_iterator begin() const;
    const_iterator cbegin() const;
    iterator rbegin();
    const_iterator rbegin() const;
    iterator end();
    const_iterator end() const;
    const_iterator cend() const;
    iterator rend();
    const_iterator rend() const;

private:
    void increment_tail();
    void increment_head();

    template <bool isconst = false>
    struct my_iterator
    {
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = long long;
        using reference = typename std::conditional_t< isconst, T const &, T & >;
        using pointer = typename std::conditional_t< isconst, T const *, T * >;
        using vec_pointer = typename std::conditional_t<isconst, std::vector<T> const *, std::vector<T> *>;
    private:
        vec_pointer ptrToBuffer;
        size_type offset;
        size_type index;
        bool reverse;

        bool comparable(const my_iterator & other) {
            return (reverse == other.reverse);
        }

    public:
        my_iterator() : ptrToBuffer(nullptr), offset(0), index(0), reverse(false) {}  //
        my_iterator(const ring<T>::my_iterator<false>& i) :
            ptrToBuffer(i.ptrToBuffer),
            offset(i.offset),
            index(i.index),
            reverse(i.reverse) {}
        reference operator*() { 
            if (reverse) 
                return (*ptrToBuffer)[(ptrToBuffer->size() + offset - index) % (ptrToBuffer->size())];
            return (*ptrToBuffer)[(offset+index)%(ptrToBuffer->size())]; 
        }
        reference operator[](size_type index) {
            my_iterator iter = *this;
            iter.index += index;
            return *iter;
        }
        pointer operator->() { return &(operator *()); }

        my_iterator& operator++ ()
        {
            ++index;
            return *this;
        };
        my_iterator operator ++(int)
        {
            my_iterator iter = *this;
            ++index;
            return iter;
        }
        my_iterator& operator --()
        {
            --index;
            return *this;
        }
        my_iterator operator --(int) {
            my_iterator iter = *this;
            --index;
            return iter;
        }
        friend my_iterator operator+(my_iterator lhs, int rhs) {
            lhs.index += rhs;
            return lhs;
        }
        friend my_iterator operator+(int lhs, my_iterator rhs) {
            rhs.index += lhs;
            return rhs;
        }
        my_iterator& operator+=(int n) {
            index += n;
            return *this;
        }
        friend my_iterator operator-(my_iterator lhs, int rhs) {
            lhs.index -= rhs;
            return lhs;
        }
        friend difference_type operator-(const my_iterator& lhs, const my_iterator& rhs) {
            lhs.index -= rhs;
            return lhs.index - rhs.index;
        }
        my_iterator& operator-=(int n) {
            index -= n;
            return *this;
        }
        bool operator==(const my_iterator &other)
        {
            if (comparable(other)) 
                return (index + offset == other.index + other.offset);
            return false;
        }
        bool operator!=(const my_iterator &other)
        {
            if (comparable(other)) return !this->operator==(other);
            return true;
        }
        bool operator<(const my_iterator &other)
        {
            if(comparable(other)) 
                return (index + offset < other.index + other.offset);
            return false;
        }
        bool operator<=(const my_iterator &other)
        {
            if(comparable(other)) 
                return (index + offset <= other.index + other.offset);
            return false;
        }
        bool operator >(const my_iterator &other)
        {
            if (comparable(other)) return !this->operator<=(other);
            return false;
        }
        bool operator>=(const my_iterator &other)
        {
            if (comparable(other)) return !this->operator<(other);
            return false;
        }
        friend class ring<T>;
    };
};

template<class T>
void ring<T>::push_back(const value_type & item)
{
    increment_tail();
    if (m_contents_size > m_array_size) increment_head(); // > full, == comma
    m_array[m_tail] = item;
}

template<class T>
void ring<T>::clear()
{
    m_head = 1;
    m_tail = m_contents_size = 0;
}

template<class T>
bool ring<T>::empty() const
{
    if (m_contents_size == 0) return true;
    return false;
}

template<class T>
inline bool ring<T>::full() const
{
    if (m_contents_size == m_array_size) return true; 
    return false;
}

template<class T>
typename ring<T>::const_reference ring<T>::operator[](size_type index) const
{
    index += m_head;
    index %= m_array_size;
    return m_array[index];
}

template<class T>
typename ring<T>::reference ring<T>::operator[](size_type index)
{
    const ring<T>& constMe = *this;
    return const_cast<reference>(constMe.operator[](index));
    //  return const_cast<reference>(static_cast<const ring<T>&>(*this)[index]);
}
//*/

template<class T>
typename ring<T>::reference ring<T>::at(size_type index)
{
    if (index < m_contents_size) return this->operator[](index);
    throw std::out_of_range("index too large");
}

template<class T>
typename ring<T>::const_reference ring<T>::at(size_type index) const
{
    if (index < m_contents_size) return this->operator[](index);
    throw std::out_of_range("index too large");
}

template<class T>
typename ring<T>::iterator ring<T>::begin()
{
    iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = 0;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::begin() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = 0;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::cbegin() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = 0;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::iterator ring<T>::rbegin()
{
    iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_tail;
    iter.index = 0;
    iter.reverse = true;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::rbegin() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_tail;
    iter.index = 0;
    iter.reverse = true;
    return iter;
}

template<class T>
typename ring<T>::iterator ring<T>::end()
{
    iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = m_contents_size;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::end() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = m_contents_size;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::cend() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_head;
    iter.index = m_contents_size;
    iter.reverse = false;
    return iter;
}

template<class T>
typename ring<T>::iterator ring<T>::rend()
{
    iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_tail;
    iter.index = m_contents_size;
    iter.reverse = true;
    return iter;
}

template<class T>
typename ring<T>::const_iterator ring<T>::rend() const
{
    const_iterator iter;
    iter.ptrToBuffer = &m_array;
    iter.offset = m_tail;
    iter.index = m_contents_size;
    iter.reverse = true;
    return iter;
}

template<class T>
void ring<T>::increment_tail()
{
    ++m_tail;
    ++m_contents_size;
    if (m_tail == m_array_size) m_tail = 0;
}

template<class T>
void ring<T>::increment_head()
{
    if (m_contents_size == 0) return;
    ++m_head;
    --m_contents_size;
    if (m_head == m_array_size) m_head = 0;
}

Here is the code that I used to test stuff out.

int main()
{
    ring<int> mybuf(10);

    for (size_t i = 0; i < 20; ++i) {
        mybuf.push(i);
        for (auto i = mybuf.begin(); i != mybuf.end(); ++i) cout << *i << ": ";
        if (mybuf.full()) cout << "full";
        cout << '\n';
    }
    cout << "Buffer Size: " << mybuf.size() << '\n';
    for (size_t i = 0; i < mybuf.size() + 1; ++i) {
        try
        {
            cout << mybuf.at(i) << ": ";
        }
        catch (std::exception e)
        {
            cout << e.what() << '\n';
            continue;
        }
    }
    cout << '\n';
    auto start = mybuf.begin();
    start += 1;
    cout << "start++: " << *start << '\n';
    ring<int>::const_iterator cstart(start);
    cout << "cstart(start)++: " << *(++cstart) << '\n';
    cout << "--start: " << *(--start) << '\n';
    if (start == mybuf.begin()) cout << "Start is mybuf.begin\n";
    else cout << "Lost!\n";
    cout << "Push!\n";
    mybuf.push(100);
    if (start == mybuf.begin()) cout << "In the begining :-)\n";
    else cout << "Start is no longer mybuf.begin\n";
    start = mybuf.begin();
    cout << "after push, start: " << *start << '\n';
    cout << "forwards:  ";
    for (auto i = mybuf.begin(); i < mybuf.end(); i+=2) cout << *i << ": ";
    cout << '\n';
    cout << "backwards: ";
    for (auto i = mybuf.rbegin(); i < mybuf.rend(); i+=2) cout << *i << ": ";
    cout << '\n';
    cout << "mybuf[0]: "<<mybuf[0] << " " << "\nPush!\n\n";
    mybuf.push(20);
    for (size_t i = 0; i < mybuf.size(); ++i) cout << mybuf[i] << ": ";
    cout << '\n';
    cout << "pop: " << mybuf.top() << '\n';
    mybuf.pop();
    cout << "new front: " << mybuf[0] << " new size: ";
    cout << mybuf.size() << '\n';
    cstart = mybuf.end();
    cout << "last: " << *(--cstart) << '\n';
    for (auto i = mybuf.begin(); i != mybuf.end(); ++i) cout << *i << ": ";
    cout << '\n';
    cout << "pop again: " << mybuf.front() << '\n';
    mybuf.pop();
    cstart = mybuf.rbegin();
    cout << "last: " << *cstart << '\n';
    for (auto i = mybuf.begin(); i != mybuf.end(); ++i) cout << *i << ": ";
    cout << "\n\nclone: ";
    ring<int> cbuf(mybuf);
    for (auto i = std::find(mybuf.begin(),mybuf.end(),100); i != cbuf.end(); ++i) cout << *i << ": ";
    auto iter = cbuf.cbegin();
    cout << "\nbegin[3] = " << iter[3];
    cout << '\n' << '\n';
    cout << "Hello World!\n";
}

And this is the output from that test.

0:
0: 1:
0: 1: 2:
0: 1: 2: 3:
0: 1: 2: 3: 4:
0: 1: 2: 3: 4: 5:
0: 1: 2: 3: 4: 5: 6:
0: 1: 2: 3: 4: 5: 6: 7:
0: 1: 2: 3: 4: 5: 6: 7: 8:
0: 1: 2: 3: 4: 5: 6: 7: 8: 9: full
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: full
2: 3: 4: 5: 6: 7: 8: 9: 10: 11: full
3: 4: 5: 6: 7: 8: 9: 10: 11: 12: full
4: 5: 6: 7: 8: 9: 10: 11: 12: 13: full
5: 6: 7: 8: 9: 10: 11: 12: 13: 14: full
6: 7: 8: 9: 10: 11: 12: 13: 14: 15: full
7: 8: 9: 10: 11: 12: 13: 14: 15: 16: full
8: 9: 10: 11: 12: 13: 14: 15: 16: 17: full
9: 10: 11: 12: 13: 14: 15: 16: 17: 18: full
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: full
Buffer Size: 10
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: index too large

start++: 11
cstart(start)++: 12
--start: 10
Start is mybuf.begin
Push!
Start is no longer mybuf.begin
after push, start: 11
forwards:  11: 13: 15: 17: 19:
backwards: 100: 18: 16: 14: 12:
mybuf[0]: 11
Push!

12: 13: 14: 15: 16: 17: 18: 19: 100: 20:
pop: 12
new front: 13 new size: 9
last: 20
13: 14: 15: 16: 17: 18: 19: 100: 20:
pop again: 13
last: 20
14: 15: 16: 17: 18: 19: 100: 20:

clone: 100: 20:
begin[3] = 17

Hello World!

Answer 1

Coding idiomatically

• Remember that #pragma once isn't standard (unlike include guards).
  • If you only intend your class works on major compilers, you can use #pragma once (but care about defects and drawbacks)
  • If you wish your class works on all compilers, use both #pragma once and the include guards.
  • If you want your class to be 100% compatible with standards, use only include guards.
  • For completeness, I have to mention redundant include guards too, which you could combine (or not) with #pragma once.
• Don't misspell size_t
  • You should use the full qualified std::size_t instead of just size_t, because it's the standard way to go.

---

Coding with style

• Try to put public members first (primarily a matter of personal preference)
  • That makes your interface more explicit.
  • When users read your header file, they directly know what your class does.
  • That's what is adopted in a lot of coding standards (google, gcc, ...)
• Be consistent
  • In your methods' order (e.g. you shuffled front/back overloads )
  • In your spacing (e.g. look at your operators' definitions)
  • In your members initialization alignment (It's really odd how you place the first member init on the same line that constructors signature, and other at the line, aligned with asserts)
  • In your naming (Why are all types "snake_case" but circularBuffer is "camelCased"?)

---

Design choices

• Type aliases

  Why are the member type aliases (value_type, reference, ...) made private?

• Naming

  Use explicit name (ring_iterator instead of my_iterator, container_type instead of circularBuffer). Avoid useless function aliases (pop_front(), push_back(), top()).

• Reconsider methods

  Are increment_head(), increment_tail() or full() are really useful?

• Consider computing size at compile time

  If you don't need to allow size to be computed at runtime, consider making it constexpr or template parameter. It will allow some optimizations.

• Maybe an oversight

  Where are crbegin/crend ? Did you forget them? And what about swap or a max_size method?

• Underlying container type

  Did you considered using a std::deque as inner data type?

---

Checking again

---

A second look

• You really have a lot of formatting problems (too much or missing space, disgraceful indentation/alignment, ...). I think you have to consider adding a formatter in your tooling. There's ton of options. You can also complete your toolbox using some "static code analysis" application and trying to compile on multiple compilers with a selected set of flags to get useful warnings.
• Consider adding the keyword explicit for constructors callable with one argument.
• You don't have to #include <iostream> nor <exception> in your ring's header, as you use nothing from them in your class.
• You don't include <iostream>, <algorithm> and <exception> headers in the example file.
• Don't implicitly use using namespace std (using it is a mistake, but using it without writing it is even worse).
• Care about readability, even for example code.

• You have a ninja semicolon after the definition of my_iterator::operator++()

  my_iterator& operator++ ()
  {
      ++index;
      return *this;
  }; // <------ Here's the ninja!
  

---

Help the compiler to help you

• Problem: error: field 'm_array_size' will be initialized after field 'm_head' [-Werror,-Wreorder]
• Solution: Initialize members in order of their declaration

---

Once the <iostream> header removed :

• Problem: error: 'out_of_range' is not a member of 'std'
• Solution: Simply #include <stdexcept> in your ring's header

Note that removing the <exception> header have no positive/negative effect on that, so keep it removed since you don't use it in your ring class.

---

• Problem: error: implicitly-declared 'constexpr ring<int>::my_iterator<false>& ring<int>::my_iterator<false>::operator=(const ring<int>::my_iterator<false>&)' is deprecated [-Werror=deprecated-copy]
• Solution: Simply define explicitly a copy assignment operator

---

• Problem: A lot of verbose errors coming from the std::find call in the example.
• Solution: Referring to the documentation and this post your my_iterator class have to provide a value_typemember. using value_type = typename std::conditional_t<isconst,T ,const T>; should do the trick (or simply T).

---

• Problem: Another verbose error starting with error: no match for 'operator-=' (operand types are 'const size_type' {aka 'const long unsigned int'} and 'const ring<int>::my_iterator<true>')
• Solution: I think this is a copy/paste mistake. Here, the use of a subtraction assignment is pointless. just remove lhs.index -= rhs;.

---

• Problem: msvc complains about "assignment operator" and "move assignment operator" implicitly defined as deleted for ring<int>. (C4626 & C5027) (note: these warning are caused by the const-ness of m_array_size.)
• Solution: Consider implementing them.

---

• Problem: In ring::my_iterator::operator[] your parameter index hides the member variable index.
• Solution: For a global solution, use a decoration (e.g. post-fix with underscore) for your member variables. Otherwise, care about naming; here change the name of the parameter.

---

In your example:

• Problem: catching polymorphic type 'class std::exception' by value [-Werror=catch-value=]
• Solution: Catch exceptions using const & instead.

---

• Problem: You pass 10 (which is an int) as size_t (an unsigned integer type, e.g. uint32_t or uint64_t) to the constructor of ring.
• Problem: You use push 20 times i which is size_t into ring<int>.
• Solution: Use the right type at the right place, even in examples.

---

• Problem: You redeclare i in the nested "for-loop", already declared in the top-level one.
• Solution: Care about naming, even in examples. Here, the outside one can be named value: it's more explicit, and bonus, you might have noticed the typing problem.

Answer 2

The implementation of full() should just be return m_contents_size == m_array_size;.

Similarly, make the implementation of empty() be return m_contents_size == 0;