Search code examples
c++c++11deque

Random access iterators and deque

I was reading some text today and it stated that since a std::deque does have a random access iterator its item retrieval rate time complexity is O(1). Although I agree with the fact that the time complexity of item retrieval is O(1) but what does having a random access iterator have to do with it ?

Solution

  • The RandomAccessIterator concept requires that the + and - operations must be implemented in constant time:

    From [iterator.concept.random.access]:

    The RandomAccessIterator concept adds support for constant-time advancement with +=, +, -=, and -, as well as the computation of distance in constant time with -. Random access iterators also support array notation via subscripting.

    This means that any standard-compliant container that implements a random-access iterator must provide constant-time element retrieval.