how does random access of an element in deque gives constant time complexity? [duplicate]

Question

Deque gives constant complexity for accessing any element( cpp reference ). In Vector, it's always constant complexity(the address of the first element in vector + no of elements * size of each element) but how does it work for Deque? Deque elements are not contiguous in memory, so how does it enable O(1) time complexity to access any element? When I ran the following program, in the case of Vector, it gives correct output, but for Deque, it gives some arbitrary numbers (agreed to not give the correct result because elements are not contiguous).

vector<int> v1;
deque<int> d1;
for(int i =0; i < 1000000;++i)
    v1.push_back(i);
for( int j =0; j < 1000000;++j)
    d1.push_back(j);
cout << *(&v1[0] +90000) << endl; // output 90000
cout << *(&d1[0] +90000)<<endl;   // Output is not 90000

Answer 1

A deque is typically implemented as a two-layer structure, the top level is an array of pointers to fixed-sized chunks. Using knowledge of that size it is constant complexity to determine which chunk holds the item of interest and constant complexity to determine which item in the chunk is being requested.

Just because it is constant does not indicate that it is always a simple direct memory access, only that all accesses for that particular operation will require the same steps.

Answer 2

Don't let the "1" confuse you. O(1) is the computer-science way of saying that the number of calculation steps necessary to arrive at the desired element does not depend on the size of the container. Whether you have a std::deque<T> with 10 elements or a std::deque<T> with 10000000 elements doesn't matter - getting the desired element at index i always involves two pointer dereferences.

See https://en.cppreference.com/w/cpp/container/deque:

typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences

Compare this to a std::list<T>, where the number of calculation steps necessary to get the element at index i does depend on the size of the container.

Answer 3

Random access to deque elements involves two pointer de-referencing, and is constant across any elements. However it won't be as efficient as vector.