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!

• Calak: I modified my review, adding some more things, in fact there's a lot of fix to apply :)
• Dmitriano: class ring is not movable, because it has const member.

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.

• davidbear: 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.
• Calak: " 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.
• Violet Giraffe: This is a good review, but point #1 about #pragma once is bad advice. It already was in 2018, and it definitely is now (I'm writing this in 2023).

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;