Double-Ended Queues using std::deque

How std::deque is implemented internally

How does a std::deque store its elements in memory?

Vector art representing computer hardware

Under the hood, a std::deque is typically implemented as a sequence of contiguous chunks of memory, sometimes called "blocks" or "pages".

Each block holds a fixed number of elements. The deque maintains a dynamic array of pointers, where each pointer points to one of these blocks.

This structure provides several advantages:

  1. It allows efficient insertion and deletion at both ends of the deque. Only the pointers need to be adjusted, no elements need to be moved.
  2. It provides random access to elements. To access an element, the deque calculates which block it's in and the offset within that block.
  3. It avoids the reallocation overhead of std::vector when inserting at the front.

However, this structure is not as cache-friendly as a std::vector's contiguous memory, which can impact iteration and random access performance.

Here's a simplified example of how a deque might be implemented:

template <typename T>
class Deque {
  T** blocks_;
  size_t frontBlock_;
  size_t backBlock_;
  // ...

  T& operator[](size_t index) {
    size_t block =
      frontBlock_ + (index / blockSize);
    size_t offset = index % blockSize;
    return blocks_[block][offset];  
  // ...

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved