How to Implement a Circular Buffer Using std::vector?
A circular buffer, also known as a cyclic buffer or ring buffer, is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. In this article, we will learn how to implement a circular buffer in C++ using std::vector.
Implementing Circular Buffer Using std::vector
We can implement a circular buffer using std::vector
that provides a flexible and dynamic array to manage data in a FIFO (First-In-First-Out) manner efficiently using the below approach.
Approach:
- Define a
std::vector
to hold the elements of the circular buffer and a variablecapacity
that
denotes the maximum size of the circular buffer.
- Maintain two pointers
head
andtail
pointing at the start and end of the buffer.- Increment the pointers using modulo operator (%) such that whenever it is about to go over the size of the array, it will move back to the start. We can do it using the formula: ptr = (ptr + 1) % size;
- To add elements use the
head
pointer: There are two possibilities:
- If the buffer is not full, add an element at the
head
position and increment thehead
pointer.- If the buffer is full, overwrite the element at the
head
pointer and update the head pointer in a circular manner.- To remove elements use the
tail
pointer: There are two possibilities:
- If the buffer is not empty, remove the element present at the position pointed by the
tail
pointer and then update the tail pointer.- If the buffer is empty return an error.
- Implement a function
empty()
to check if the circular buffer is empty or not. If both the head and tail pointers are equal and pointing at the 0th index then the circular buffer is empty.- Implement a function
full()
to
check if the circular buffer is full or not. If the head pointer is at the 0th index and the tail pointer is pointing to the last index of the buffer then the circular buffer is full.
C++ Program to Implement a Circular Buffer Using std::vector
The below program demonstrates how we can implement a circular buffer using a std::vector in C++.
// C++ program to illustrate how to implement a circular
// buffer using std::vector
#include <iostream>
#include <stdexcept>
#include <vector>
using namespace std;
class CircularBuffer {
private:
vector<int> buffer;
int head;
int tail;
int capacity;
public:
// Constructor to intialize circular buffer's data
// members
CircularBuffer(int capacity)
{
this->capacity = capacity;
this->head = 0;
this->tail = 0;
buffer.resize(capacity);
}
// Function to add an element to the buffer
void push_back(int element)
{
buffer[head] = element;
head = (head + 1) % capacity;
if (head == tail) {
tail = (tail + 1) % capacity;
}
}
// Function to remove an element from the buffer
void pop_front()
{
if (empty()) {
throw out_of_range("Buffer is empty");
}
tail = (tail + 1) % capacity;
}
// Function to check if the buffer is empty
bool empty() const { return head == tail; }
// Function to check if the buffer is full
bool full() const
{
return (head + 1) % capacity == tail;
}
// Function to get the size of the buffer
int size() const
{
if (head >= tail) {
return head - tail;
}
return capacity - (tail - head);
}
// Function to print the elements of the buffer
void printBuffer() const
{
int idx = tail;
while (idx != head) {
cout << buffer[idx] << " ";
idx = (idx + 1) % capacity;
}
cout << endl;
}
};
int main()
{
// Create a buffer of size 5
CircularBuffer buffer(3);
// Add elements to the buffer
for (int i = 1; i <= 3; ++i) {
buffer.push_back(i);
cout << "Added: " << i << endl;
}
// Print elements of the buffer after adding elements
cout << "Elements of the buffer: ";
buffer.printBuffer();
// Check the size of the circular buffer before deletion
// of elements
cout << "Buffer size: " << buffer.size() << endl;
// Remove elements from the buffer
for (int i = 0; i < 1; ++i) {
buffer.pop_front();
cout << "Removed" << endl;
}
// Print elements of the buffer after removing elements
cout << "Elements of the buffer: ";
buffer.printBuffer();
// Check the size of the circular buffer after deletion
// of elements
cout << "Buffer size: " << buffer.size() << endl;
return 0;
}
Output
Added: 1 Added: 2 Added: 3 Elements of the buffer: 2 3 Buffer size: 2 Removed Elements of the buffer: 3 Buffer size: 1
Time Complexity: O(N), here N is the number of elements in the circular buffer
Auxiliary Space: O(N)