Circular Buffer in C++

circular_buffer.cpp

//===================================================================
// File: circular_buffer.cpp
//
// Desc: A Circular Buffer implementation in C++.
//
// Copyright © 2019 Edwin Cloud. All rights reserved.
//
//===================================================================

//-------------------------------------------------------------------
// Includes
//-------------------------------------------------------------------
#include <memory>

//-------------------------------------------------------------------
// Circular_Buffer (Class)
//     We will implement the buffer with a templated class so
//     the buffer can be a buffer of specified type.
//-------------------------------------------------------------------
template <class T> class Circular_Buffer {
private:
  //---------------------------------------------------------------
  // Circular_Buffer - Private Member Variables
  //---------------------------------------------------------------

  std::unique_ptr<T[]> buffer; // using a smart pointer is safer (and we don't
                               // have to implement a destructor)
  size_t head = 0;             // size_t is an unsigned long
  size_t tail = 0;
  size_t max_size;
  T empty_item; // we will use this to clear data
public:
  //---------------------------------------------------------------
  // Circular_Buffer - Public Methods
  //---------------------------------------------------------------

  // Create a new Circular_Buffer.
  Circular_Buffer<T>(size_t max_size)
      : buffer(std::unique_ptr<T[]>(new T[max_size])), max_size(max_size){};

  // Add an item to this circular buffer.
  void enqueue(T item) {

    // if buffer is full, throw an error
    if (is_full())
      throw std::runtime_error("buffer is full");

    // insert item at back of buffer
    buffer[tail] = item;

    // increment tail
    tail = (tail + 1) % max_size;
  }

  // Remove an item from this circular buffer and return it.
  T dequeue() {

    // if buffer is empty, throw an error
    if (is_empty())
      throw std::runtime_error("buffer is empty");

    // get item at head
    T item = buffer[head];

    // set item at head to be empty
    T empty;
    buffer[head] = empty_item;

    // move head foward
    head = (head + 1) % max_size;

    // return item
    return item;
  }

  // Return the item at the front of this circular buffer.
  T front() { return buffer[head]; }

  // Return true if this circular buffer is empty, and false otherwise.
  bool is_empty() { return head == tail; }

  // Return true if this circular buffer is full, and false otherwise.
  bool is_full() { return tail == (head - 1) % max_size; }

  // Return the size of this circular buffer.
  size_t size() {
    if (tail >= head)
      return tail - head;
    return max_size - head - tail;
  }
};

//---------------------------------------------------------------
// Main Function
//---------------------------------------------------------------
int main() {

  Circular_Buffer<uint32_t> cb(10);

  printf("\n === CircularBuffer Test ===\n");
  printf("Size: %zu\n", cb.size());

  uint32_t x = 1;
  printf("Enqueue 1, val: %d\n", x);
  cb.enqueue(x);
  printf("Size: %zu\n", cb.size());
  x = 2;
  printf("Enqueue 1, val: %d\n", x);
  cb.enqueue(x);
  printf("Size: %zu\n", cb.size());
  printf("Enqueue 1, val: %d\n", x);
  cb.enqueue(x);
  printf("Size: %zu\n", cb.size());
  x = cb.dequeue();
  printf("Dequeue: %d\n", x);
  printf("Size: %zu\n", cb.size());
  x = cb.dequeue();
  printf("Dequeue: %d\n", x);
  printf("Size: %zu\n", cb.size());
  x = cb.dequeue();
  printf("Dequeue: %d\n", x);
  printf("Size: %zu\n", cb.size());
  x = cb.dequeue();
  printf("Dequeue: %d\n", x);
  printf("Size: %zu\n", cb.size());
  printf("Empty: %d\n", cb.is_empty());
}

Thanks for the implementation, but I think there are a missing parentheses in size() function:
return max_size - head - tail; should be return max_size - (head - tail); if not variable will overflow.

Hi! Thanks for posting your implementation.

Personally I would go with std::vector-based storage
vector buffer;

Am I missing some benefits of unique_ptr<T[]> or it is just matter of taste?

According to [1] you could get negative modulo results when using negative input values which can be the case on line 83. It's probably safer to write it as bool is_full() { return (head + 1) % max_size == head; }

[1] https://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo

According to [1] you could get negative modulo results when using negative input values which can be the case on line 83. It's probably safer to write it as bool is_full() { return (head + 1) % max_size == head; }

[1] https://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo

Do you mean this: bool is_full() { return (tail + 1) % max_size == head; }

Do you mean this: bool is_full() { return (tail + 1) % max_size == head; }

Thx for the reply. I made a typo.

It's should be either
bool is_full() { return (tail + 1) % max_size == head; } or
bool is_full() { return (head + 1) % max_size == tail; }

I don't have the time right now to figure out which one exactly.

In this implementation, if you have a buffer with max_size 10, you can only queue 9 elements effectively since the is_full() function will return true and cause an exception when tail + 1 % max_size == head (which means there is still one space that is not used).

To solve this problem, we can create a variable to keep track of the number of elements added, then we can simply understand whether the array is full or empty by simply looking count.

bool is_full() { return count == max_size; }
bool is_empty() { return count == 0; }

Hi! Thanks for posting your implementation.

Personally I would go with std::vector-based storage
vector buffer;

Am I missing some benefits of unique_ptr<T[]> or it is just matter of taste?

Yes, there are benefits to this over std::vector.

Circle buffers are used when you know exactly how many slots you need and you want fast push/pop and when you want FIFO behavior. Vectors can be relatively slow and heavy (this is the price we pay for dynamic containers). This implementation uses unique_ptr<T[]> because the size is dynamic at runtime, though sometimes we may know the size at compile time and if it's small it'd be better to put it on the stack.

Using buffer(std::unique_ptr<T[]>(new T[max_size])) is bad practice since you first create the fixed size array and then copy it in your unique_pointer. Instead, consider using buffer(std::make_unique<T[]>(max_size)), which 1) resolves the auxiliary copy, refer to this cpp conference and 2) is both faster and exception safe, refer to this article.

Using buffer(std::unique_ptr<T[]>(new T[max_size])) is bad practice since you first create the fixed size array and then copy it in your unique_pointer. Instead, consider using buffer(std::make_unique<T[]>(max_size)), which 1) resolves the auxiliary copy, refer to this cpp conference and 2) is both faster and exception safe, refer to this article.

Could you elaborate on how std::make_unique is better here?

There is no array copy since the smart pointer only holds the pointer (and even if there was an array copy hopefully it would be optimized away by the compiler).

With std::make_unique we're actually incurring a cost due to value-initializing the array's contents which could be significant and will prevent the container from being used with types that do not have default constructors. https://godbolt.org/z/dj9vGTrc7.

@jeremy-rifkin Using the new operator calls the default constructor of the object to initialize the allocated memory. I'm not sure there's an easy way to make this class usable with non-default-constructible objects except possibly using something like type erasure or c-style allocation via malloc which doesn't call an object's constructor. https://godbolt.org/z/TExGz15jW

@kylesemelka-figure The typical well-formed solution to avoid default constructing the whole underlying array is to essentially make a char array and do placement-new into that memory (this is how std::vector is commonly implemented)