Deque implemented as vector of vectors?

[venkatacplpl]

I am unable to imagine implementation of deque as it promises random access,insertion and deletion at both ends in constant time.

If a deque is implemented as vector of vectors how it can do 'random access' & 'insertion/deletion at the front' in constant time?

[Cubbi]

I think a vector of arrays is a better mental model. Imagine it's a vector< array <T,1000>>.

So to access the element at index k, you can access v [k%1000][k/1000] (constant time indexed vector access plus constant time indexed array access)

To append at end, you either write to the next unused location in the array (so you have to keep track of that position), which is constant time, or you have to allocate one more array without copying any elements (which is much slower, but treated as constant time for the purpose of container operations complexity)

Real deque would of course use blocks of uninitialized storage instead of arrays, and the indexing is a bit different because of the ability to push_front, but the idea is the same: two pointer derefences to reach the value, allocating in chunks, and never reallocating.

[JLBorges]

Outline of an implementation using such a scheme:
https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/deques/page/deques.html

[venkatacplpl]

Thanks a lot guys ....that is really helpful.