4
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ I modified my review, adding some more things, in fact there's a lot of fix to apply :) \$\endgroup\$ – Calak Nov 24 '18 at 21:41
5
\$\begingroup\$

Message modified, see below for the updates

Coding idiomatically


Coding with style

  • Try to put public members first (primarily a matter of personal preference)
    • That's make your interface more explicit
    • When users read your header file, they directly know what your class do.
    • 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 does all type are "sneak_case" but circularBuffer is "camelCased"?)

Design choices

  • Type aliases

    Why member type aliases (value_type, reference, ...) are make privates ?

  • 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

    Does 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 forgot them? And what about swap or a max_size method?

  • Underlaying container type

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


End words

It's late, I've to stop here for now. If no one came completing my responses, I'll edit my post to try going further.

Second pass, let's use tooling

Finally, I took time to continue this review, trying to compile it.


Checking again


A second look

  • You really have a lot of formatting problems (too much or missing space, disgracefull indentation/alignment, ...). I think you have to consider adding a formater 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, you use nothing from them in your class.
  • You don't provide <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 helping 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 about a copy/paste mistake. Here, the use of a subtraction assignment is pointless. just remove lhs.index -= rhs;.

  • Problem: msvc complain 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 hide the member variable index.
  • Solution: For a global solution, use a decoration (e.g. post-fix with underscore) for your member variables. Otherwise, car 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 (aka an int) to size_t (a aka an unsigned integer, 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.
\$\endgroup\$
  • \$\begingroup\$ I have thought about using std::deque and decided that std::vector’s contiguous memory guarantee and that three is no need for insertion in this class made that option less attractive. I am curious as to how you generated all of those compiler errors, I don’t see them, and thus I didn’t know to fix them (I use VS17). Based on your review, I have substantially revised my code. What is the community standard for showing my new review inspired code? I would be very much interested in seeing if this c++ barbarian has understood all of your suggestions. \$\endgroup\$ – davidbear Nov 25 '18 at 17:07
  • \$\begingroup\$ " What is the community standard for showing my new review inspired code?" Dunno, maybe post a new question, or a new reply to this question. Or wait response from a moderator ;) For warning, I compiled on Clang/GCC with -Wpedantic -Werror -Wwrite-strings -Wno-parentheses -Warray-bounds -Weffc++ -Wstrict-aliasing and /W4 on msvc. Used CppCheck too. \$\endgroup\$ – Calak Nov 25 '18 at 17:22
0
\$\begingroup\$

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;

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.