How is std::deque implemented ?

Deque is sometimes thought of as an dynamic array that is comprised of linked arrays.

typical deque layout

Such a structure could lead to extremely fast insert and remove operations.

Exactly what performance should one expect from a std::deque implementation though?


The C++ standard defines that the deque should have

• O(1) complexity for push_back(), push_front(), pop_back(), pop_front()
• O(1) complexity for random access, via operator[]
• Up to N/2 shifts on an insert/remove operation, for a N-sized deque

These restrictions naturally --but not necessarily-- lead to a structure like this, where each memory chunk has constant size:

possible deque implementation

Constant chunk size is important, because then it's easy to map the index of an array to the index inside a chunk, in O(1). Only the first and last chunk may be partly empty.

Whenever a push_back() takes place, the entry is added inside the last chunk, or a new chunk is allocated. The same procedure happens on a push_front(), at the first chunk.

During an insert() operation however, lots of shifts have to take place. Shifts take place all the way from the point of insertion to the nearest end of the deque -- either the front, or the back, whichever is closest. Hence the "up to N/2 shifts" restriction.
You can't expect a chuck to emerge, because no chunks in the middle of the deque can have gaps.
You can't expect a chunk to expand, because all chunks have constant size, for fast indexing.

In general, it's useful to think of deque either as

• a data structure suitable for a stack or a queue, with fast push/pop and random access operations
• a vector with half the shifts during an insertion/deletion, and no doubling of memory or reallocations during push_back().