Creating a Custom Container and Iterator

Learn how containers and iterators work by implementing a circular buffer.

We'll cover the following

The best way to understand how containers and iterators work is to experience them firsthand by creating our own. To avoid implementing something that already exists in the standard library, we’ll consider something different—more precisely, a circular buffer. This is a container that, when full, overwrites existing elements.

Requirements

We can think of different ways such a container could work; therefore, it’s important that we first define the requirements for it. These are as follows:

  • The container should have a fixed capacity that is known at compile-time. Therefore, there would be no runtime memory management.

  • The capacity is the number of elements the container can store, and the size is the number of elements it actually contains. When the size equals the capacity, we say the container is full.

  • When the container is full, adding a new element will overwrite the oldest element in the container.

  • Adding new elements is always done at the end; removing existing elements is always done at the beginning (the oldest element in the container).

  • There should be random access to the elements of the container, both with the subscript operator and with iterators.

Implementation details

Based on these requirements, we can think of the following implementation details:

  • The elements could be stored in an array. For convenience, this could be the std::array class.

  • We need two variables, which we call head and tail, to store the index of the first and last elements of the container. This is needed because due to the circular nature of the container, the beginning and the end shift over time.

  • A third variable will store the number of elements in the container. This is useful because otherwise, we wouldn’t be able to differentiate whether the container is empty or has one element only from the values of the head and tail indexes.

Note: The implementation shown here is provided for teaching purposes only and is not intended as a production-ready solution. The experienced reader will find different aspects of the implementation that could be optimized. However, the purpose here is to learn how to write a container and not how to optimize the implementation.

The following diagram shows a visual representation of such a circular buffer with a capacity of eight elements with different states:

Get hands-on with 1400+ tech skills courses.