Why is std::deque not a vector with memory reserved before index 0?

Question

As far as I understand, the motivation behind deque is to provide a random-access container with efficient push_front.

Commonly cited advantages of vector compared to deque include faster traversal and at(), but mostly its C compatibility, as it guarantees contiguous memory. Deque does not, since it is a collection of chunks of memory, each holding a number of values.

I'm confused. Why is not deque built like a vector but with memory reserved before index 0 in addition to the memory reserved after index size-1 ? This would guarantee contiguous memory, enable efficient push_front and even avoid the additional indirection when dereferencing iterators.

To minimize shifting during insertion, the contained values to be shifted would depend on the insertion point. If inserting at index n being before size()/2, shift values up to n left. Otherwise shift right the values after n.

What did I miss that is so important that deque is a collection of arrays of values and not one big array ?

Answer 1

According to Wikipedia, what you're describing is indeed one possible implementation, at least in general.

However, the C++ standard imposes requirements that essentially prohibit this as an implementation for std::deque; [deque.modifiers] states:

An insertion at either end of the deque ... has no effect on the validity of references to elements of the deque.

(Thanks to @BenjaminLindley!)