I understand how random access iterators work for contiguous containers like std::vector: the iterator simply maintains a pointer to the current element and any additions/subtractions are applied to the pointer.
However, I'm baffled as to how similar functionality could be implemented for a non-contiguous container. My first guess for how std::deque:iterator works, is that it maintains a pointer to some table of the groups of contiguous memory it contains, but I'm not sure.
How would a typical standard library implement this?
You can satisfy the requirememts of a std::deque with a std::vector<std::unique_ptr<std::array<T,N>>> roughly. plus a low/high water mark telling you where the first/last elements are. (for an implementation defined N that could vary with T, and the std::arrays are actually blocks of properly aligned uninitialized memory and not std::arrays, but you get the idea).
Use usual exponential growth, but on both front and back.
Lookup simply does (index+first)/N and %N to find the block and sub element.
This is more expensive than a std::vector lookup, but is O(1).