Skip to content

Practice Lab 24 — Ring buffer with non-type parameters

Difficulty: Advanced · Estimated time: 5 hours · Module 12: Templates and Generic Programming

Capacity as part of the type. A small, exact container where every decision has a visible consequence, and where the compiler will help you if you let it.

At a glance
Difficulty Advanced
Estimated time 5 hours
Module Module 12 — Templates and Generic Programming
Concepts practised Non-type template parameters, fixed capacity, specialisation, generic versus concrete trade-offs, constexpr, type safety at compile time
Prerequisite Practice Lab 23
Class design the container's operations are specified; its internals and choices are yours

Scenario

An embedded logger captures sensor readings at a fixed rate. It must never allocate — the device has no heap worth the name — and it must keep the most recent N readings, discarding the oldest when full. A telemetry link occasionally asks for the last N in order.

The logger is used with exactly two capacities: 64 readings for a fast channel and 4096 for a slow one, and the capacity is a compile-time constant in both cases. Nothing at run time decides it.

Written badly, this container is where students discover that a "full" ring buffer has four states confused for two, and that a copy of the buffer-with-index is a bug waiting to happen.

Problem statement

Implement a RingBuffer<T, N>: a fixed-capacity container with no dynamic allocation.

  1. Operations: push (overwriting the oldest when full, as a documented choice), pop_oldest, pop_newest, size, capacity, empty, full, at(index) with a documented indexing meaning, and iteration in oldest-to-newest order.
  2. Two capacities in use, both as non-type parameters.
  3. A specialisation for one element type: for example a bool or char specialisation with a documented difference — or a full specialisation that stores counts rather than elements, if you prefer. The specialisation must be justified in the notes; a specialisation that behaves identically is a defect.
  4. A constexpr capacity query, so RingBuffer<int, 64>::capacity() is usable in a constant expression.
  5. A compile-time failure: attempting to instantiate with capacity 0 must fail with a clear message.
  6. Overwrite accounting: overwritten() counts how many elements were discarded, because the logger's diagnostics need it.

In ring-notes.md:

  • The four states of a ring buffer, and how your implementation stores them (two indices, a count, or a flag).
  • Why no allocation is required, and which of the standard containers could not be used here and why.
  • The specialisation's difference, and what it cost in lines and in surprise.
  • The cost of capacity being part of the type: which operations become free, and which become impossible.

Learning objectives

By the end of this lab you will be able to:

  • Write a class template with a non-type parameter and use it for two instantiations.
  • Implement a fixed-capacity container correctly, including the full/empty distinction and overwrite policy.
  • Specialise a template where the element type genuinely allows a better representation.
  • Make an invalid instantiation fail with a message that names the problem.
  • Explain what putting a value into the type buys and what it forbids.

Functional requirements

  1. Capacity is a compile-time constant, and capacity() is usable in constexpr contexts.
  2. Empty and full are distinguishable at all times, including with capacity 1 — the case that breaks two-index implementations.
  3. push on a full buffer discards the oldest and increments overwritten().
  4. pop_oldest and pop_newest both refuse an empty buffer with a documented result.
  5. Iteration is oldest-to-newest, and is stable across a wrap-around.
  6. at(index) has a documented meaning — oldest-relative is the sensible choice; say which you picked.
  7. The container works for a non-copyable element type if the operations used permit it, or you document which operation forces a copy.
  8. sizeof(RingBuffer<T, N>) does not depend on the heap; the container contains its storage.
  9. Capacity 0 does not compile, and the message names the capacity requirement.
  10. The specialisation is exercised in the program, and produces the documented, different behaviour.

Constraints

  • Header-only template, plus a small main per instantiation and one that must fail to compile.
  • No dynamic allocation anywhere — no new, no std::vector, no std::deque.
  • No exceptions in the hot operations: refusals are reported through documented results.
  • No static mutable state in the container.
  • No warnings in the programs that should compile.

Starter task

In ring-notes.md, before coding:

  1. Write the four states (empty, partly full, exactly full, wrapped) and the data you will store to tell them apart. Predict what capacity 1 does to your design.
  2. Decide the overwrite policy and write it as one sentence at the class.
  3. Decide what at(index) means, and what an out-of-range index does.
  4. Write the specialisation you intend, and the sentence that justifies it being different.
  5. Predict sizeof for two instantiations, then measure.

Implementation tasks

  1. Implement RingBuffer<T, N> with the state model from your notes.
  2. Implement both pops and the iteration.
  3. Add overwritten() and use it in a scripted sequence that wraps twice.
  4. Implement the specialisation and demonstrate its difference.
  5. Add the capacity-0 failure and capture the message.
  6. Write main per instantiation, and the failing program as a separate file.
  7. Print sizeof and the constexpr capacity check.

Test cases

# Action Expected result
1 Push 5 into capacity 64 size 5, not full, empty false
2 Fill exactly to capacity full true, size == capacity
3 Push one more oldest discarded, overwritten() 1, iteration order correct
4 Wrap twice with 130 pushes into capacity 64 overwritten() equals the expected count
5 pop_oldest after wrapping The oldest surviving element
6 pop_newest The most recently pushed
7 Pop from empty Refused, documented result
8 Capacity 1: push, push, iterate size 1, the newest element, overwritten() 1
9 at(0) and at(size-1) Oldest and newest, per your documented meaning
10 constexpr capacity check Compiles as a constant expression
11 sizeof for two instantiations Recorded numbers; no heap member
12 Capacity 0 Does not compile; message captured
13 The specialisation's program The documented, different behaviour

Boundary cases to run deliberately: capacity 1 (again, deliberately); push then immediately pop; iteration right after a wrap; a RingBuffer of a struct larger than the capacity is long.

Expected behaviour

RingBuffer<int, 4>
  push 1..4 -> size 4, full
  push 5    -> overwritten 1, iteration oldest->newest: 2 3 4 5
  push 6    -> overwritten 2, iteration: 3 4 5 6
  pop_oldest -> 3
  pop_newest -> 6
  capacity as a constant expression: 4
  sizeof(RingBuffer<int, 4>) = 24
RingBuffer<int, 1>
  push 7, push 8 -> size 1, iteration: 8, overwritten 1
capacity 0:
  error: static_assert failed: RingBuffer capacity must be at least 1

Extension challenge

Add iteration by chunks of the most recent K elements (for a telemetry request), where K is a run-time value, not a template parameter.

Record in ring-notes.md:

  • Why K should not be a template parameter (one sentence about what that would do to instantiations).
  • How the chunk iteration is expressed, and whether it needs a copy.
  • What happens when K exceeds size(), and when K exceeds capacity().
  • The change cost: operations, lines, and any new requirement on T.

Debugging challenge

The buffer reports full when it is empty, but only after exactly one wrap:

bool full() const { return head_ == tail_; }
bool empty() const { return head_ == tail_; }

Reproduce it — capacity 4, push 4, pop 1, push 1, then query — and answer:

  1. Why are full and empty indistinguishable with two indices alone, and what is the third piece of information every correct ring buffer keeps?
  2. Which two operations produced the same index pair in your reproduction?
  3. Write the corrected predicate pair, and say which one is now obviously derived from the other.
  4. Which test case in the table catches this, and did the capacity-1 case catch it first?

Reflection questions

  1. Where is your "full" state kept, and how did capacity 1 influence that choice?
  2. Capacity is part of the type. Which operations became constexpr for free, and which became impossible (for example, changing capacity at run time)?
  3. Your specialisation behaves differently. What would a user be surprised by, and how did you document it?
  4. The container performs no allocation. Which of the standard containers could have been used instead, and what would each have cost you here?
  5. overwritten() is a diagnostic. What else would an embedded logger want to know that this container cannot tell it?
  6. If a second channel needed a capacity chosen from a configuration file, what would you change, and what would you lose?

Completion checklist

  • [ ] The compiling programs build with -Wall -Wextra -Werror and no warnings
  • [ ] No dynamic allocation — searched for and recorded
  • [ ] Empty and full are correct, including at capacity 1
  • [ ] Overwrite accounting is exact across two wraps
  • [ ] Both pops refuse an empty buffer with a documented result
  • [ ] Iteration is oldest-to-newest and correct after wrapping
  • [ ] Capacity is a constexpr query usable in a constant expression
  • [ ] Capacity 0 fails to compile, with the message captured
  • [ ] The specialisation exists and differs in a documented way
  • [ ] sizeof recorded for two instantiations
  • [ ] All thirteen test cases run, with output recorded
  • [ ] The debugging challenge was explained before being fixed

Related: Lab index · Module 12 — Templates · Previous: Practice Lab 23 · Next: Practice Lab 25 — Order validation with an exception hierarchy