why is the time complexity of std::distance() function O(n) for std::list iterators, and O(1) for std::vector iterators?

Question

This question is related to remove and erase functions

Answer 1

The reason is that std::list::iterator is a ForwardIterator, while std::vector::iterator is a RandomAccessIterator.

A Forward iterator is just required to be incrementable to point to the successive element and be dereferencable to yield a value. Thus if you want to point to the 5th element, you need to perform 5 increment operations.

Now to calculate the distance for a list, we must reach the final iterator passed as argument from the list, which is n elements away. Thus calculating the distance is linear, or the complexity is O(n).

A Random Access Iterator, like a raw pointer, is bidirectional (can be incremented and decremented), is subtractable from another address to get the number of elements in between them, and can be added to a number to get the successive address in constant time.

Thus when you use distance on std::vector's iterators, it simply subtracts the iterators, which is a constant operation. Thus the complexity is O(1).