Кольцевой БуферRing Buffer

Массив фиксированной ёмкости cap хранит элементы, а два индекса — head (следующий элемент на извлечение) и tail (следующая свободная позиция для вставки) — определяют, какая часть массива логически "занята". Вставка (push) записывает значение в buf[tail] и сдвигает tail на (tail + 1) % cap — операция по модулю и есть "оборачивание": если tail дошёл до конца массива, следующая позиция — снова индекс 0. Извлечение (pop) читает buf[head] и аналогично сдвигает head. Отдельный счётчик count (или иногда — соглашение "оставлять одну ячейку пустой") нужен, чтобы различить состояния "буфер пуст" и "буфер полон", которые иначе неразличимы по одному условию head == tail.A fixed-capacity array cap stores elements, and two indices — head (the next element to remove) and tail (the next free slot for insertion) — define which part of the array is logically "occupied." Insertion (push) writes the value into buf[tail] and advances tail to (tail + 1) % cap — the modulo operation is exactly the "wrapping": once tail reaches the array's end, the next position is index 0 again. Removal (pop) reads buf[head] and advances head the same way. A separate count (or, in some conventions, "always leave one cell empty") is needed to distinguish "buffer empty" from "buffer full," which otherwise both look like head == tail.

template<typename T>
class RingBuffer {
    std::vector<T> buf;
    size_t head = 0, tail = 0, count = 0;
public:
    explicit RingBuffer(size_t cap) : buf(cap) {}

    bool push(const T& val) {
        if (count == buf.size()) return false;  // полон// full
        buf[tail] = val;
        tail = (tail + 1) % buf.size();          // оборачивание через модуль// wrapping via modulo
        ++count;
        return true;
    }

    std::optional<T> pop() {
        if (count == 0) return std::nullopt;      // пуст// empty
        T val = buf[head];
        head = (head + 1) % buf.size();
        --count;
        return val;
    }
};

Ячейки массива фиксированной ёмкости расположены по кругу. Оранжевая метка — head, синяя — tail. Переключатель режима меняет поведение при заполнении: bounded — push отклоняется, пока не освободится место (типично для очередей между потоками); overwrite — push всегда успевает, затирая самый старый элемент и сдвигая head вместе с tail (типично для циклических логов вроде dmesg).The fixed-capacity array's cells are laid out in a circle. Orange marks head, blue marks tail. The mode switch changes what happens when the buffer is full: bounded — push is rejected until space frees up (typical for inter-thread queues); overwrite — push always succeeds, evicting the oldest element and advancing head along with tail (typical for circular logs like dmesg).

Обычный массив без оборачивания индекса реализует стек или очередь только пока не достигнут конец памяти — после этого нужно либо остановиться, либо сдвинуть все элементы к началу (O(n)). Кольцевой буфер решает это раз и навсегда арифметикой по модулю: логическая позиция элемента отделена от его физического адреса в памяти, что позволяет переиспользовать освободившееся пространство в начале массива без единого перемещения существующих данных. Это тот же общий приём "разделить логическую и физическую адресацию", что лежит и в основе хеш-таблиц (2.3.1.3+) — там позиция тоже вычисляется, а не задаётся порядком вставки.A plain array without index wrapping implements a stack or queue only until memory runs out — after that, either stop or shift every element to the start (O(n)). A ring buffer solves this once and for all with modulo arithmetic: an element's logical position is decoupled from its physical memory address, allowing freed space at the array's start to be reused without moving a single existing element. This is the same general "separate logical from physical addressing" trick underlying hash tables (2.3.1.3+) too — there, position is also computed rather than set by insertion order.