Skip to content

Instantly share code, notes, and snippets.

@edwintcloud
Created May 7, 2019 18:40
Show Gist options
  • Save edwintcloud/d547a4f9ccaf7245b06f0e8782acefaa to your computer and use it in GitHub Desktop.
Save edwintcloud/d547a4f9ccaf7245b06f0e8782acefaa to your computer and use it in GitHub Desktop.
Circular Buffer in C++
//===================================================================
// 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());
}
@ra2u18
Copy link

ra2u18 commented Jul 8, 2021

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.

@jeremy-rifkin
Copy link

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.

@kyle-figure
Copy link

@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

@jeremy-rifkin
Copy link

@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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment