Step 5 of 5

Challenge: a ring buffer

A ring buffer (circular buffer) is a fixed-capacity queue stored in an array. New items go at the write position, which wraps around to the start with %. When the buffer is full, the newest item overwrites the oldest. Audio pipelines, loggers and network stacks use ring buffers because they never allocate memory after construction.

capacity 4, after pushing 1..6:   [5][6][3][4]   oldest = 3
                                          ^head

The key idea is translating a logical index (0 = oldest) into a physical array index:

physical = (head + i) % N

Here's that translation in a small class that keeps the last few temperatures:

#include <array>
#include <cstddef>
#include <iostream>

class LastThree {
public:
    void push(int v) {
        std::size_t write = (head_ + size_) % 3;   // the slot after the newest
        data_[write] = v;
        if (size_ < 3) size_++;
        else head_ = (head_ + 1) % 3;              // full: the oldest was overwritten
    }
    int at(std::size_t i) const { return data_[(head_ + i) % 3]; }   // 0 = oldest
    std::size_t size() const { return size_; }

private:
    std::array<int, 3> data_{};
    std::size_t head_ = 0, size_ = 0;
};

int main() {
    LastThree t;
    for (int temp : {18, 21, 19, 25, 23}) {
        t.push(temp);
        std::cout << "after " << temp << ":";
        for (std::size_t i = 0; i < t.size(); i++) std::cout << " " << t.at(i);
        std::cout << "\n";
    }
}

after 18: 18
after 21: 18 21
after 19: 18 21 19
after 25: 21 19 25
after 23: 19 25 23

How it works

• Where does the next item go? size_ items follow the oldest, so the next free slot is (head_ + size_) % N.
• While not full, pushing just grows size_. Once full, that slot is the oldest item, so it's overwritten and head_ moves forward one.
• Every index is taken % N, so positions wrap around the end of the array.

Adding iteration

For begin()/end(), write a small iterator holding a pointer to the buffer and a logical index. operator* returns (*buf)[i] using the translation above, ++ increments i, and == compares i. Then begin() is logical index 0 and end() is logical index size_. Range-for then visits oldest to newest, no matter where the data physically sits.

Your turn: write template <typename T, std::size_t N> class RingBuffer with:

• void push(const T& v): adds v; when full, overwrites the oldest
• std::size_t size() const, bool full() const
• const T& operator[](std::size_t i) const: i-th element counting from the oldest
• begin()/end() so range-for visits oldest to newest (an iterator holding a buffer pointer and an index works well)

Previous: A lazy range