Задача 03 — кольцевой буфер (C++)

Разминка уровня «основная»: структура маленькая, но встречается везде. Ориентир — 40–60 минут.

Глава I. Общая информация

Цель: научиться писать структуру с фиксированной памятью и без сдвигов элементов.
Почему это в Eltex: приём/передача пакетов, буферы DMA, очереди между потоками — всё это кольцевые буферы. Понимание wrap-around и «полный/пустой» — прямой вопрос на собеседовании. Механизм тот же, что у сетевой карты: пакеты пишутся в кольцо по мере прихода, драйвер вычитывает их с другого конца, и обе стороны никогда не двигают уже записанные данные по памяти — двигаются только индексы head/tail.
Что сдаётся: solution.cpp, проходящий python3 grade.py 03.

Глава II. Что нужно знать до старта

Идея: массив фиксированного размера + два индекса. head — куда писать, tail — откуда читать. Когда индекс доходит до конца, он возвращается в начало: idx = (idx + 1) % capacity. Сдвигать элементы не нужно никогда — в этом весь смысл: push/pop двигают только индекс, а не байты в памяти, поэтому обе операции остаются O(1) независимо от размера буфера.

Ловушка, из-за которой задача попадает в собеседования: как отличить пустой буфер от полного, если оба индекса совпали? При head == tail возможны оба состояния — буфер мог быть только что создан (пуст) или заполнен ровно capacity раз (полон) — по одним индексам это не различить. Варианты: хранить счётчик size, либо оставлять одну ячейку свободной. В нашем интерфейсе есть size(), поэтому проще хранить счётчик.

Почему дальше: тот же счётчик size_ вместо пересчёта по индексам — частый приём и в std::deque, и в реализациях lock-free очередей, где индексы вообще нельзя лишний раз читать.

Глава III. Задание

class RingBuffer {
public:
    explicit RingBuffer(size_t capacity);
    ~RingBuffer();
    bool   push(int v);       // false, если буфер полон (перезапись НЕ делать)
    bool   pop(int& out);     // false, если буфер пуст
    size_t size() const;
    size_t capacity() const;
    bool   empty() const;
    bool   full() const;
};

Требования:

O(1) на push/pop, никаких сдвигов элементов;
память выделяется один раз в конструкторе и освобождается в деструкторе;
корректное поведение после заворачивания индексов (записали до конца, продолжили с начала);
двойного освобождения быть не должно.

Глава IV. Ступени

Ступень 1 (10 минут). Поля: указатель на массив, capacity_, size_, head_, tail_. Конструктор выделяет массив и обнуляет поля. Деструктор освобождает. Если хочешь короче — std::vector<int> вместо ручного new[], тогда деструктор не нужен вовсе.

Ступень 2 (10 минут). empty() — это size_ == 0, full() — size_ == capacity_. Проверь на буфере ёмкости 1: после одного push он полон, после одного pop пуст.

Ступень 3 (15 минут). push: если полон — вернуть false и ничего не менять; иначе записать в head_, сдвинуть head_ = (head_ + 1) % capacity_, увеличить size_, вернуть true.

Ступень 4 (15 минут). pop: если пуст — false; иначе отдать buffer_[tail_], сдвинуть tail_, уменьшить size_, вернуть true.

Ступень 5. Проверь руками wrap-around: ёмкость 4, положи 4 элемента, сними 2, положи ещё 3 — все значения должны идти в правильном порядке. Затем python3 grade.py 03.

Глава V. Критерии приёмки

PASS от grade.py 03: сборка без предупреждений, ASAN/UBSAN чистые, все проверки ok, включая порядок FIFO и корректный wrap-around.

Глава VI. Подсказки (после первой попытки)

Значения после заворота идут не в том порядке

Проверь, что pop читает именно tail_, а push пишет именно в head_, и что оба индекса инкрементируются после операции. Классическая ошибка — сдвинуть head_ до записи.

Перезапись при полном буфере

Ты не проверяешь full() в push. По условию перезапись запрещена: полный буфер возвращает false и не портит старые данные.

ASAN: утечка или двойное освобождение

Если память выделена через new[], освобождать нужно delete[] (не delete). Проще взять std::vector<int> — тогда вопрос исчезает.

Глава VII. Ловушки

Сдвиг элементов вместо индексов → цена push/pop вырастает до O(n) → теряется весь смысл структуры, видно по сравнению с наивным std::vector на бенчмарке.
Путаница «пусто/полно» при совпавших индексах (head_ == tail_) без отдельного size_ → full() и empty() дают одинаковый ответ на разных состояниях → тест на заполненный буфер ёмкости > 1 падает.
% на каждом шаге там, где можно было обойтись условием — не ошибка, но на собеседовании спросят «а быстрее можно?» (ответ: if (++idx == cap) idx = 0;, деление по модулю дороже сравнения).
Копирование объекта без правила трёх/пяти → два объекта владеют одним и тем же new[]-буфером → двойное освобождение при выходе обоих из области видимости, ловится ASAN. Если сдаёшь с ручным new[], запрети копирование (= delete).

Факты для карточек

base | Сложность push/pop кольцевого буфера? — O(1)
core | Как отличить пустой буфер от полного при head_ == tail_? — хранить отдельный счётчик size_ (или жертвовать одной ячейкой)
core | Чем delete[] отличается от delete для массива, выделенного new[]? — delete без [] на массиве — UB, вызовет деструктор только для первого элемента и испортит подсчёт размера аллокации
base | Какое условие делает push дешевле, чем % capacity_ на каждый вызов? — if (++idx == cap) idx = 0;

После сдачи

Разбор: как устроены буферы в драйверах (ring buffer с head/tail для DMA), почему в многопоточном варианте нужны атомарные индексы и memory_order.

8.9 KiB Raw Permalink Blame History Unescape Escape