This post is part of a series on implementing classic data structures in
modern C++ (C++20), without new/delete scattered around and with the
sanitizers watching every step. The code lives in
collections101.
A queue is the data structure of waiting lines: the first element in is the first one out (FIFO). It shows up everywhere, from task schedulers to breadth-first search. Its interface is tiny:
| Operation | What it does |
|---|---|
enqueue | inserts an element at the back |
dequeue | removes the element at the front |
front | reads the element at the front |
is_empty | tells whether there is anything in it |
When we restrict ourselves to these four operations, we can implement a queue on (at least amortized) constant time. The restriction is the point: a queue cannot do much, and in exchange it can do it fast and communicate intent clearly.
The naive array, and why it fails
The obvious approach is to keep the elements in an array, append at the end,
and remove from the beginning. Appending is cheap. Removing from the
beginning is not: every remaining element must shift one position to the left,
which costs O(n). Reversing the roles just moves the problem to enqueue.
A linked list solves this (keep a pointer to the first and to the last node), and it is a fine implementation. But each element pays for a pointer and a separate allocation, and walking the nodes jumps around in memory. Can we keep the contiguous array and still get O(1) at both ends?
Don’t move the elements, move the indices
The trick is to stop treating position 0 of the array as the front of the queue. Instead, we store where the front currently is, and let the queue wrap around the end of the array as if the memory were a circle.
Here is a queue (e₁, e₂, e₃) in an array of capacity 8, sitting in the middle:
index: 0 1 2 3 4 5 6 7
[ ][ ][ ][e₁][e₂][e₃][ ][ ]
^ begin = 3, size = 3
And the same queue after a few enqueues and dequeues pushed it past the end:
index: 0 1 2 3 4 5 6 7
[e₂][e₃][ ][ ][ ][ ][ ][e₁]
^ begin = 7, size = 3
Both are valid. To find the i-th element of the queue, we compute its physical position with a modulo:
position(i) = (begin + i) mod capacity
The front is at position(0), the next free slot is at position(size).
Dequeuing just advances begin; enqueuing writes at position(size).
Nothing ever shifts.
The class
template <std::movable T>
class Queue {
public:
Queue() = default;
Queue(const Queue&) = delete;
auto operator=(const Queue&) -> Queue& = delete;
~Queue() noexcept;
void enqueue(T);
auto dequeue() -> T;
[[nodiscard]] auto front() const -> const T&;
[[nodiscard]] auto is_empty() const noexcept -> bool;
private:
void double_capacity();
auto wrap(std::size_t) const noexcept -> std::size_t;
[[no_unique_address]] std::allocator<T> alloc_;
T* values_ = nullptr;
std::size_t begin_ = 0;
std::size_t size_ = 0;
std::size_t capacity_ = 0;
};
A few things worth noticing:
std::movable Tis a C++20 concept: we only accept element types that can be moved (and destroyed). A bad element type fails at the declaration, with a readable error, instead of deep inside a template instantiation.- We keep a
std::allocator<T>member. We need to allocate memory without constructing objects in it: the array hascapacity_slots, but onlysize_of them hold live objects.new T[n]would construct alln. std::allocatorhas no state, but an ordinary empty member still occupies at least one byte (eight, after padding). The C++20 attribute[[no_unique_address]]lets the compiler give it no storage at all. Older code got the same effect by inheriting privately from the allocator (the empty base optimization), which also dumps names likeallocateandvalue_typeinto the class; the attribute keeps it a plain member.- Apart from the allocator, the state is four numbers: the buffer, where the
queue begins, how many elements it has, and how many fit. There is no “end”
pointer; it is
begin_ + size_, wrapped. - Copying is deleted. We will come back to that, because it is the most instructive bug in this post.
The mapping from logical to physical index is one line:
template <std::movable T>
auto Queue<T>::wrap(std::size_t i) const noexcept -> std::size_t {
return i % capacity_;
}
The operations
enqueue grows the buffer when it is full, then constructs the new element
in the first free slot with std::construct_at:
template <std::movable T>
void Queue<T>::enqueue(T value) {
if (size_ == capacity_)
double_capacity();
std::construct_at(values_ + wrap(begin_ + size_),
std::move(value));
++size_;
}
Taking value by value and moving it in serves both callers: a temporary is
moved twice (cheap), an lvalue is copied once, which is unavoidable anyway.
dequeue moves the front element out, destroys what is left in its slot,
advances begin_, and hands the element to the caller:
template <std::movable T>
auto Queue<T>::dequeue() -> T {
if (is_empty())
throw std::runtime_error{"no element to dequeue"};
T value(std::move(values_[begin_]));
std::destroy_at(values_ + begin_);
begin_ = wrap(begin_ + 1);
--size_;
return value;
}
std::destroy_at is the mirror of std::construct_at: one starts an
object’s lifetime in raw memory, the other ends it and leaves raw memory
behind. (They are the C++20 spelling of placement new and an explicit
destructor call, p->~T(), with names that make the pairing obvious.)
Because we separated allocation from construction, we are now responsible
for keeping them paired: every slot in [begin, begin + size) (wrapped) holds a live
object, every other slot is raw memory. That invariant is the whole
implementation.
Note that moving from the slot does not end the object’s lifetime. A
moved-from std::string is still a std::string (typically empty), and its
destructor must still run, which is why the destroy_at stays. What the move
buys us is that this destruction is cheap: the expensive part (the
characters, the pointee of a unique_ptr) now belongs to value.
And value is no longer the queue’s problem. It is returned to the caller,
who owns it from then on. In practice the compiler constructs it directly
in the caller’s variable (named return value optimization), so there is no
second move. If the caller ignores the result, as in a plain
queue.dequeue();, the compiler materializes a temporary at the call site
and destroys it at the end of that statement. Either way, every object is
destroyed exactly once, and the queue does not need to know which case
happened.
Why does std::queue::pop return void, then?
The standard library’s pop returns nothing, and you are expected to write
auto x = q.front(); q.pop();. That design predates move semantics. In
C++98, returning the element meant copying it after it had been removed;
if that copy threw, the element was gone for good, and the operation could
not offer the strong exception guarantee.
With moves, the risk mostly disappears. We move into value before
touching the queue, so if that move throws, nothing was removed. The
remaining gap is narrow: the return is not guaranteed to be elided for a
named variable, so a compiler that skipped the elision would perform a second
move, after removal, and a throwing move there would lose the element. Real
compilers elide here, and moves rarely throw. In exchange we get a queue that
works with move-only types such as std::unique_ptr and a one-step
auto x = q.dequeue();. Other designs made the same call: Rust’s
pop_front, and concurrent queues, where a separate front() and pop()
would race against other threads.
front only reads. Standard containers also offer a non-const overload
that lets the caller modify the element in place, but we leave it out on
purpose: once an element is in the queue, it is not modified. To change it,
dequeue it and enqueue the new value. The queue keeps to the four
operations in the table, and since dequeue hands the element back, that
round trip is cheap. is_empty is what you would expect:
template <std::movable T>
auto Queue<T>::front() const -> const T& {
if (is_empty())
throw std::runtime_error{"empty queue has no front"};
return values_[begin_];
}
template <std::movable T>
auto Queue<T>::is_empty() const noexcept -> bool {
return size_ == 0;
}
Growing without breaking anything
When the buffer is full, we allocate one twice as large and move the elements over, unwrapping them on the way so that the new queue starts at index 0:
template <std::movable T>
void Queue<T>::double_capacity() {
auto new_capacity = capacity_ == 0 ? 1 : 2 * capacity_;
auto buffer = alloc_.allocate(new_capacity);
std::size_t i;
try {
for (i = 0; i < size_; ++i)
std::construct_at(
buffer + i,
std::move_if_noexcept(values_[wrap(begin_ + i)]));
} catch (...) {
std::destroy_n(buffer, i);
alloc_.deallocate(buffer, new_capacity);
throw;
}
for (i = 0; i < size_; ++i)
std::destroy_at(values_ + wrap(begin_ + i));
if (values_) // deallocate only takes what allocate gave
alloc_.deallocate(values_, capacity_);
begin_ = 0;
values_ = buffer;
capacity_ = new_capacity;
}
Two details make this robust:
- Exception safety. Constructing an element can throw (copying a
std::stringallocates). If the k-th construction fails, we destroy the k objects already built in the new buffer, release it, and rethrow. The old buffer was never touched, so the queue is exactly as it was before. std::move_if_noexcept. Moving is fast, but if a move can throw halfway through, the old elements are already gutted and we cannot roll back.move_if_noexceptmoves when the move constructor isnoexceptand copies otherwise, which keeps the rollback above honest. This is the same choicestd::vectormakes when it reallocates.
Doubling is what makes enqueue amortized constant time: a reallocation
costs O(n), but it happens after n cheap insertions, so the average cost
per insertion stays bounded. The price is memory: right after a resize, up to
half of the buffer is empty.
The destructor
template <std::movable T>
Queue<T>::~Queue() noexcept {
for (std::size_t i = 0; i < size_; ++i)
std::destroy_at(values_ + wrap(begin_ + i));
if (values_) // deallocate only takes what allocate gave
alloc_.deallocate(values_, capacity_);
}
Destroy the live objects (wrapped, again), then release the memory. Same invariant, last time.
The if (values_) guard (also in double_capacity, for the first growth)
covers a queue that never allocated. Unlike delete, which accepts a null
pointer, std::allocator::deallocate requires a pointer that allocate
returned. Passing nullptr usually works in practice, since the default
allocator ends up in operator delete, which ignores null. But it breaks the
allocator’s contract, and nothing guarantees it works.
The bug that copying would have caused
Here is the version without the two = delete lines, and a two-line program:
Queue<std::string> a;
a.enqueue("x");
auto b = a; // compiles!
The compiler happily generates a copy constructor that copies the four
members. Now a and b point at the same buffer, and when both go out of
scope, both destructors destroy the same string and free the same memory.
Compiled with -fsanitize=address, this program stops immediately:
ERROR: AddressSanitizer: heap-use-after-free
SUMMARY: AddressSanitizer: heap-use-after-free ... in Queue<std::string>::~Queue()
Without the sanitizer, it may crash, corrupt the heap silently, or appear to work. This is the rule of five in action: a class that manages a resource in its destructor must decide what copying and moving mean. Deleting the copy operations is the simplest correct answer (and, as a side effect, suppresses the equally broken implicit move operations). Implementing a real deep copy and a pointer-stealing move are good exercises; the second one is short.
This is also why the tests in collections101 are always built with
-fsanitize=address,undefined,leak: in hand-written containers, the bugs that
matter are the ones that do not crash right away.
Linked or circular?
Both implementations give O(1) operations. They differ in everything else:
| Linked nodes | Circular buffer | |
|---|---|---|
enqueue | O(1) worst case | O(1) amortized |
| Extra memory | one pointer per element | up to half the buffer, unused |
| Allocations | one per element | one per doubling |
| Cache locality | poor (nodes are scattered) | good (elements are contiguous) |
In practice the circular buffer usually wins, thanks to locality and far fewer
allocations. The linked version is the one to pick when you need a hard
worst-case bound on every single enqueue (no occasional O(n) resize).
Exercises
- Since the capacity is always a power of two,
i % capacity_can be replaced by a bit mask. Write it. Does it make a measurable difference? - Add
size()in constant time. (It is almost free here. Why is it not free in the linked version without an extra member?) - Implement a move constructor and a move assignment for
Queue. - Shrink the buffer when the queue is less than a quarter full. Why a quarter and not a half?
- Add
clear(), which empties the queue but keeps its capacity.
The complete implementation and a small test are in collections101.