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?
source
share