Subtracting and comparing random-access iterators: why and where?

Question

I am developing a small library for my work, and I derived a few classes from the standard random-access iterator category. This allows me to use things like iterator traits and to not worry too much when I use standard libraries like algorithm for example. Of course I know I don't have to, and that I could either chose the bidirectional category instead or even implement my own. But that is not the point.

IMO, the "gap" between the bidirectional and random-access categories is too large, and I don't understand the necessity for the subtraction and comparison operators between iterators -- that is: a-b, a<b and a>b (and the loose variants thereof).

Why does the standard force the implementation of these operators, and could someone please give me an example where the (in)equality test, mixed iterator-scalar artithmetic (compound or not) operators and the offset dereference operator are not sufficient?

Answer 1

One common case where you need a difference between iterators is binary search: without knowing the distance, you would not know how much you need to add to the iterator on the left side in order to get to the midpoint in O(1) time. Once you know the distance, you could apply mixed iterator-scalar arithmetic to get to the middle, also in constant time.

Note that you could find the distance by repetitively incrementing one iterator until you get to the other one, but that would take O(n) time.

You also need the a < b comparison to know which iterator is on the left side, and which one is on the right. Without this comparison you would not be able to validate the input to your binary search algorithm.

I find confusing [that] the subtraction operator should return an int, and not an iterator, even though "logically" I would expect that an arithmetic operation between two objects of the same type returns an object of that type too.

Subtraction gives you the distance - the number of steps from one point to the other. This is a scalar number, independent of the type of the iterator. The symmetry here is straightforward: since

iteratorA + scalar = iteratorB

simple arithmetic rules tell us that

scalar = iteratorB - iteratorA