Search code examples
c++iteratorrandom-access

Does RandomAccessIterator imply that the data is continuous in memory?


The other iterator types surely don't have the implication that they point to continuous data, but I'm wondering if I can treat RandomAccessIterators as if they point to a buffer of continuous data – i.e. they could be converted to pointers to data.

Is this assumption correct? Can I always safely use &*it and get a pointer not just to one element, but to a continuous buffer, if it is a RandomAccessIterator?


Solution

  • No, it is not a valid assumption. The standard library itself has a counterexample in std::deque:

    from cppreference:

    As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

    std::deque's iterator is a RandomAccessIterator:

    [deque.overview]/1

    A deque is a sequence container that, like a vector ([vector]), supports random access iterators.

    If you want a guarantee of contiguous memory, you don't need to wait long: the guarantee will be provided by the ContiguousIterator in C++17.1


    the ContiguousIterator concept was proposed in a sequence of documents ending in N4284, and adopted in November 2014