Question: 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?

Answer: 
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::array`s are actually blocks of properly aligned uninitialized memory and not `std::array`s, 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).
A deque iterator can be implemented by storing both a pointer to the referenced value and a double pointer to the contiguous block of memory in which that value is located. The double pointer points into a contiguous array of pointers to blocks managed by the deque.

```
class deque_iterator
{
  T* value;
  T** block;
  …
}

```

Because both `value` and `block` point into contiguous memory, you can implement operations such finding the distance between iterators in constant time (example adapted from libc++).

```
difference_type operator-(deque_iterator const& x, deque_iterator const& y)
{
  return (x.block - y.block) * block_size
       + (x.value - *x.block)
       - (y.value - *y.block);
}

```

Note that, while `value` will not be invalidated by operations such as `push_front` and `push_back`, `block` might be, which is why `deque_iterator` is invalidated by such operations.