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

As far as I understand, deque's motivation is to provide a random access container with efficient push_front.

The commonly cited advantages of a vector over deque include faster traversal and at(), but mostly, its compatibility with C, as it provides continuous memory. Deque does not, because it is a collection of pieces of memory, each of which has several meanings.

I'm confused. Why is not deque created as a vector, but with memory reserved before the index 0in addition to the memory reserved after the index size-1? This ensures continuous memory, and allows you to effectively push_frontand even avoid additional indirectness when dereferencing iterators.

To minimize offset during insertion, the contained values ​​that need to be shifted will depend on the insertion point. If the insertion nis before size()/2, the shift values ​​to nremain. Otherwise, shift the values ​​after to the right n.

What I missed is it so important that deque is a collection of arrays of values, not one large array?

+5
source share
1 answer

, , , , .

++ , std::deque; [deque.modifiers]:

deque... deque.

( @BenjaminLindley!)

+8

All Articles