Now that we understand the design behind the common STL dequeue implementations, we can peek into the implementation details.

Inside STL: The deque, implementation

By Raymond Chen

From the article:

All three of the major implementations of the standard library maintain an array of pointers to blocks, which they confusingly call a “map” even though it is unrelated to std::map. (Even more confusingly, gcc internally uses the term “node” instead of “block”.) Initially, all the pointers in the map are nullptr, and the blocks are allocated only on demand.

We will say that a block is spare if it contains only spare elements.