Q:

C++ How do iterators for non-contiguous containers like deque find the next element

Following from this here.
I am wondering how containers that are non-contiguous and are not linked lists actually know where to find the next element given that it is not guaranteed to come right after this element? Is there an extra table saying the first x chunks of the deque are located at this starting point, the next y chunks are starting over there, and so on?

A:

The container keeps necessary information internally for direct access to elements as the internal implementation of deque is basically a double ended queue of chunks(vectors). Each chunks has elements indexed,once the chunk is full,another chunk is added maintaining the integrity of indexing and the container class keeps information it needs to provide access,locating the correct chunk and thereafter the indexed location of the element sought.
You can read the great article here which would provide all the knowledge you seek and even more than what you seek: 
https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container
Also to see a brief implementation of deque,you can go through the accepted answer on stack overflow
What really is a deque in STL?

