6
\$\begingroup\$

Minimal implementation of a circular buffer based on std::array, where elements can only be pushed and iterated. I'm interested on potential failures and very trivial optimizations, as I'd like to keep it as simple as possible.

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <array>

// Array-based push-only circular buffer.

// Sample usage:
//
// CircularBuffer<int, 3> buff;
// buff.push( 1 ); // 1
// buff.push( 2 ); // 1 2
// buff.push( 3 ); // 1 2 3
// buff.push( 4 ); // 2 3 4
// buff.push( 5 ); // 3 4 5

//for( int i : buff )
//  std::cout << i << std::endl;

template <class T, std::size_t SIZE>
class CircularBuffer
{
public:
  static_assert( SIZE > 0 );

  void push( const T & value )
  {

    if( ( ++mCurrentIndex ) == mCapacity )
      mCurrentIndex = 0;

    mBuffer[ mCurrentIndex ] = value;

    if( mSize != mCapacity )
      ++mSize;
  }

  void push( T && value )
  {

    if( ( ++mCurrentIndex ) == mCapacity )
      mCurrentIndex = 0;

    mBuffer[ mCurrentIndex ] = std::move( value );

    if( mSize != mCapacity )
      ++mSize;
  }

  void reset()
  {
    mCurrentIndex = -1;
    mSize         = 0;
  }

  class iterator
  {
  public:
    using iterator_category = std::output_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;


    explicit iterator( pointer bufferPtr, unsigned int index, unsigned int visited ) :
        mBufferPtr( bufferPtr ),
        mIndex( index ),
        mVisited( visited )
    {}

    iterator& operator++()
    {
      if( ++mIndex == mCapacity )
        mIndex = 0;
      ++mVisited;
      return *this;
    }

    iterator operator++( int )
    {
      iterator retval = *this;
      ++( *this );
      return retval;
    }

    bool operator==( iterator other ) const
    {
      return ( ( mBufferPtr + mIndex ) == ( other.mBufferPtr + other.mIndex ) ) &&
             ( mVisited == other.mVisited );
    }

    bool operator!=( iterator other ) const
    {
      return !( *this == other );
    }

    reference operator*() const
    {
      if( mIndex == -1 )
        throw std::runtime_error( "Circular buffer is empty" );
      return mBufferPtr[ mIndex ];
    }

  private:
    pointer      mBufferPtr;
    unsigned int mIndex;
    unsigned int mVisited;
  };

  iterator begin()
  {
    const unsigned int beginIndex = ( mSize < mCapacity ) ? 0 : ( mCurrentIndex + 1 ) % mCapacity;
    return iterator( mBuffer.data(), beginIndex, 1 );
  }

  iterator end()
  {
    const unsigned int endIndex = ( mSize < mCapacity ) ? ( mCurrentIndex + 1 ) : ( mCurrentIndex + 1 ) % mCapacity;
    return iterator( mBuffer.data(), endIndex, mSize + 1 );
  }

private:
  enum {                   mCapacity     = SIZE };
  std::array<T, mCapacity> mBuffer;
  unsigned int             mCurrentIndex = -1;
  unsigned int             mSize         = 0;
};

#endif // CIRCULAR_BUFFER_H
\$\endgroup\$
1
  • \$\begingroup\$ I just found out you that I cannot get a const iterator :( \$\endgroup\$
    – Sdra
    May 20 at 15:14

2 Answers 2

5
\$\begingroup\$

Missing Includes

It doesn't compile for me without the #include <stdexcept>.
Other stuff is luckily included by other includes. I'm personally a fan of explicit includes though. (std::size_t, std::move, std::output_iterator_tag, std::ptrdiff_t)

Size & Capacity

As already mentioned in another answer use one type only for one thing, namely your size and current index values. (It could lead to bugs btw if mSize can never reach mCapacity.)
And while doing that think about "fixing" mCapacity. Maybe I'm missing something but what's up with that enum wrapper? Why not just simply make it a static and/or constexpr member? Or why not just omit it altogether and just use the template parameter directly?
Also note that the template parameter says "size" while the member says "capacity" and the mSize member has actually nothing to do with the SIZE template parameter.

Bug: Deref begin() on an Empty Buffer

That should probably lead to an exception if I understand the intention of the check in the operator*. But it doesn't. And if I see correctly it actually can only throw if you reach the maximum possible size given by the type of the variable, i.e. std::numeric_limits<unsigned>::max() (or whatever common size type you settle on - and given that it will be an unsigned one).
(As already mentioned in another answer it is questionable though if you want to throw there, anyway, because standard containers don't. But it can be a nice safety feature of course.)

Circular Iterator

The iterator is circular for fully filled buffers only. It should be if(++mIndex == mSize) in operator++() - if it is intended to be a circular iterator after all.

About reset

Note that this does not what clear for standard containers does. I.e. it does not erase and therefore does not destruct anything.
That could of course be intended and be the reason why it is not called clear after all.

\$\endgroup\$
6
\$\begingroup\$

It's missing a lot of features

The parts you have implemented look reasonably OK, but it is missing a lot of features you would expect from a container class. You already mentioned you cannot get a const iterator, but it also misses things like pop(), front(), back(), empty(), operator[]() and so on. Have a look at something close to your container, like std::deque, and try to implement as much of the API of such a container as possible for your class.

You also might want to consider splitting push() into push_front() and push_back(); there is nothing that prevents you from doing that in a circular buffer, and there might be a use case for it.

Use std::size_t consistently

Use std::size_t for counts, sizes and indices. You already use it for the template parameter SIZE, so you have to make sure the member variables mCurrentIndex and mSize match.

Avoid code duplication

You have two overloads of push(), as is appropriate, but you'll have noticed that the body of those overloads are almost identical. To avoid having to repeat yourself, you can for example factor out the common parts into a separate, private function:

T& get_next_slot() {
    if (++mCurrentIndex == mCapacity)
      mCurrentIndex = 0;

    if (mSize != mCapacity)
      ++mSize;

    return mBuffer[mCurrentIndex];
}

Then the two push() functions become:

void push(const T& value) {
    get_next_slot() = value;
}

void push(T&& value) {
    get_next_slot() = std::move(value);
}

Avoid using -1 as a special value

I would try to avoid -1 as a special value to indicate an empty circular buffer. I would initialize mCurrentIndex to zero, and post-increment it instead of pre-increment it. Furthermore, you should not have to check in operator*() whether the index is valid. The common rule is that callers should not try to dereference iterators that are equal to end().

Appropriate iterator tag

I don't think std::output_iterator_tag is appropriate for your class, unless you only want callers to be able to write to the contents of the buffer. Also, you can do multiple passes over the buffer without any issues, so a std::forward_iterator_tag seems more appropriate.

I also think it should be possible to make this into a std::random_access_iterator, by adding the necessary overloads to your iterator class.

\$\endgroup\$
1
  • \$\begingroup\$ All good points, thanks! The purpose of this circular buffer is indeed restricted only to pushing elements and then iterate them, so that should probably be reflected in the name as well. However you are right, the interface can be extended to have a more flexible usage \$\endgroup\$
    – Sdra
    May 20 at 17:00

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.