Implementing a Circular Buffer with Vector
How do I implement a circular buffer using std::vector?
A circular buffer, also known as a ring buffer, is a fixed-size buffer that wraps around when it reaches its end. It's particularly useful for scenarios like buffering data streams or implementing a queue with a fixed maximum size. Let's implement a simple circular buffer using std::vector.
Basic Implementation
Here's a basic implementation of a circular buffer:
// CircularBuffer.h
#pragma once
#include <vector>
#include <stdexcept>
template <typename T>
class CircularBuffer {
public:
CircularBuffer(size_t size)
: buffer(size), max_size(size){}
void push(const T& item){
buffer[head] = item;
if (full) { tail = (tail + 1) % max_size; }
head = (head + 1) % max_size;
full = head == tail;
}
T pop(){
if (empty()) {
throw std::runtime_error(
"Buffer is empty");
}
T item = buffer[tail];
full = false;
tail = (tail + 1) % max_size;
return item;
}
bool empty() const{
return (!full && (head == tail));
}
size_t size() const{
if (full) { return max_size; }
if (head >= tail) { return head - tail; }
return max_size + head - tail;
}
bool full = false;
private:
std::vector<T> buffer;
size_t head = 0;
// Points to the next write position
size_t tail = 0;
// Points to the oldest element
size_t max_size;
};Using the Circular Buffer
Now let's see how we can use this circular buffer:
#include <iostream>
#include "CircularBufer.h"
int main(){
CircularBuffer<int> buffer(5);
// Fill the buffer
for (int i = 1; i <= 5; ++i) {
buffer.push(i);
}
std::cout << "Buffer full? "
<< (buffer.full ? "Yes" : "No") << '\n';
std::cout << "Buffer size: " << buffer.size()
<< '\n';
// Overwrite some values
buffer.push(6);
buffer.push(7);
// Pop and print all values
while (!buffer.empty()) {
std::cout << buffer.pop() << ' ';
}
std::cout << '\n';
std::cout << "Buffer empty? "
<< (buffer.empty() ? "Yes" : "No") << '\n';
}Buffer full? Yes
Buffer size: 5
3 4 5 6 7
Buffer empty? YesIn this example, we create a circular buffer of size 5. We fill it with numbers 1 to 5, then add 6 and 7, which overwrite 1 and 2. When we pop all elements, we get 3, 4, 5, 6, 7 in that order.
This implementation uses std::vector as the underlying container, which provides contiguous memory storage and efficient random access. The head and tail indices wrap around using the modulo operator, creating the circular behavior.
Remember, this is a basic implementation and could be extended with additional features like iterators, capacity changes, or thread safety, depending on your specific needs.
Dynamic Arrays using std::vector
Explore the fundamentals of dynamic arrays with an introduction to std::vector