How are random access iterators for non-contiguous containers (such as std::deque) implemented?

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 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.

Answer 2

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).