What really is a deque in STL

Question

I was looking at STL containers and trying to figure out what they really are (i.e. the data structure used) when I came across the deque: at first, I thought it was a double linked list, which would allow insertion and deletion from both ends in constant time, but the promise made by the operator [] to be done in constant time concerned me. Arbitrary access in a linked list should be O(n), right?

And how can it add elements in constant time if it's a dynamic array?

It should be noted that reallocation may occur, and thus O(1), like a vector, is an amortised cost.

So I'm curious about this structure that permits arbitrary access in constant time while never requiring relocation to a larger location.

Answer 1

A deque is defined somewhat recursively: fundamentally, it keeps a double-ended queue of fixed-size pieces. Each chunk is a vector, and the queue of chunks ("map" in the figure below) is likewise a vector.

schematic of the memory layout of a deque
The map is internally represented as a T** in the GCC standard library implementation. Each data block is a T* with a defined size __deque buf size (which is determined by sizeof(T)).