Why Aren't More Iterators Random Access?

Question

I'm trying to learn more about the STL iterators in C++. I understand how different data structures have different iterators but I don't understand why some iterators are not RandomAccess. For instance, why is the LinkedList iterator not a random access iterator? I understand that a LinkedList is not a "random access structure" perse, but couldn't we implement the iterator to give the illusion of a random access structure? For instance, the LinkedList has a Bidirectional Iterator which does not define the + or += operator but it defines the ++ operator. Couldn't we just define the + and += operators using something like:

iterator operator+= (int steps) {
     for (int i = 0; i < steps; ++i) {
          this->operator++();
     }
}

After looking at the RandomAccessIterator requirements, I think we could probably implement most if not all of those functions for the LinkedList so why don't we? I'm guessing its because some operations would have essentially O(N) time complexity, but I'm not sure if that is the key concern. If we were to implement RandomAccessIterators using this approach, what consequences would this have on using the LinkedList with STL algorithms? Would we suddenly be able to sort a LinkedList using the std::sort function?

Answer 1

I'm guessing its because some operations would have essentially O(N) time complexity, but I'm not sure if that is the key concern.

Yes, that is precisely the key concern. Iterators are modeled after pointers. And with pointers, people have certain expectations. One of those expectations is that pointer addition and subtraction are very fast operations (specifically, O(1)). The designers of the standard library decided to honor those expectations. So if a standard library iterator cannot perform addition and subtraction in O(1), then it does not implement those operations, and is not classified as a random access iterator.

Note that with the increment and decrement operators (++ and --), the performance requirements are slightly relaxed, and there are some iterators which implement those in O(log n) instead of O(1). This compromise is necessary, because if you can't increment or decrement an iterator, it's not much use.

If we were to implement RandomAccessIterators using this approach, what consequences would this have on using the LinkedList with STL algorithms? Would we suddenly be able to sort a LinkedList using the std::sort function?

Yes. But it would become (at least) an O(n^2) algorithm, instead of the O(n log n) which is promised by the standard.

Answer 2

Iterator categories are about more than what is possible; they're also about what is reasonable.

Any forward iterator can be advanced X number of times. But ForwardIterator does not include += for integers. This is important, because it allows code which is written against the RandomAccessIterator requirement to explicitly fail when provided with an iterator that doesn't explicitly provide this interface. And by doing so, such code can declare itself to have a particular performance characteristics.

For example std::sort is O(n log(n)). But it can only promise that because it requires random access iterators. You could in theory implement the same std::sort algorithm with any BidirectionalIterator, but your performance would be exceedingly bad for non-random access iterators. So bad that you should probably do something drastic with your code, rather than just accepting the performance penalty. Therefore, std::sort outright forbids it.

Or to put it another way, if someone told you to implement sort for a BidirectionalIterator, you would pick a very different algorithm than the one you would for a RandomAccessIterator.

Other algorithms are able to be more flexible. They may have a faster implementation with random access iterators, but they'd still be using the same general algorithm (in theory). This is why functions like std::advance exist; they allow mere Forward/BidirectionalIterators to have the same integer offsetting behavior as RandomAccessIterators. But you're using them with the full knowledge that it's going to be O(n) for non-RandomAccessIterators. For some algorithms, this performance difference is OK.