Random access iterators mean you can efficiently advance or retreat an iterator by an arbitrary amount. So a vector (via pointer arithmetic) but not a linked list.

Right but why should this matter at the type level? All you need to implement is next() and annotate it with documentation of the performance characteristics.

Yeah, this is a good question. Scott Myers has a talk where he pokes fun at the "guaranteed O(N log N)" sort of a linked list, where the guarantee is in number of comparisons and not the (very large) number of pointer chases.

Why describe at the type level the difference between a backwards pointer chase and a pointer decrement? The hope is: if you know at compile time that your iterator is efficient in this way, you can pick a more specialized algorithm, say, quicksort instead of mergesort. C++ really does enable this at the type level through template specialization. In practice the STL collections haven't lived up to this, and I think the iterator tags are mostly deadweight.

Thanks, that was helpful. I suspect the reason it ends up being dead weight is that it doesn't make much sense to prevent an API customer from using an iterator with certain performance characteristics with certain algorithms. Ultimately, the onus is on the developer to know something about the data; for instance, why wouldn't I be allowed to use any iteration algorithm on my slow-to-increment iterator if I know the length is 1?

So long as it's safe I think it's on the designer to make sure it's efficient, and I suspect that's where the API has gravitated to.

You can think of it as implementing `seek`, not just `next`.

`RandomAccessIterator` implements the `+=` and `-=` operations that `BidirectionalIterator` does not. Algorithms that accept `RandomAccessIterator` can then assume that calling += is possible.

What's the advantage to using a random access iterator over a get() indexed? Like to me the point of an iterator is that it abstracts over access kind, and exposes the minimum viable view, which is sequential forward and possibly backward access.

If you want indexed access why wouldn't you just, you know, use anything that implements operator[]?

Just that iterators is the API that C++ settled on for doing this in a generic way (well concepts in C++20, but I haven't learned that yet).

It's totally 100% kosher to write a function that calls `.at()` instead of `operator+=`. As long as it only needs to work on vectors, strings, or other stuff with a `.at()` method.

But if the function works on iterators instead it can work on ANY data structure that also fulfills the requirements of RandomAccessIterator API. String Views, raw pointers, a 3rd party Cord library, etc.

There's no inherent meaning to the iterator API requiring `operator+=` instead of something closer to `get()`, except that it means that the iterator itself doesn't need to know anything about container bounds (like I said above, raw pointers work as RandomAccessIterators).

[] alone doesn't imply that the view is sequential. Binary search for example requires both sequential items and indexed access. You can't binary search an std::map even if it implements [].

You need an additional API to create views/sublists if you want to transparently operate on sub ranges and if you want to return a found index you may need to convert its value to apply to a parent view.

The way the random access iterator was described in the article is not that it allows iteration over an un-ordered collection but rather that it allows random access within the collection. This would not necessarily map well to an un-ordered collection. This appears to be born out by the API which supports arbitrary addition and subtraction to the iterator. I could of course be mistaken.

What you're describing based on my experience with other languages is simply an "input iterator" over an un-ordered collection. An iterator does not guarantee deterministic/repeatable ordering, just defined ordering (as in, guarantees it won't visit the same element twice), in my experience.