Subtraction and comparison of random access iterators: why and where?

Question

I am developing a small library for my work, and I have deduced several classes from the standard category of random access iterators . This allows me to use things like iterator properties and not have to worry too much, for example when I use standard libraries like algorithm . Of course, I know that I do not need, and that I could either choose a bi-directional category , or even implement my own. But this is not the point.

IMO, the “gap” between bidirectional and random access categories is too large, and I do not understand the need for subtraction and comparison operators between iterators, that is: ab , a<b and a>b (and its free options).

Why is the standard implementation power of these operators, and can someone please give me an example where the equality test (in), mixed iterator-scalar arithmetic (compound or not) operators and the markup offset operator are insufficient?

Answer 1

One of the common cases when you need the difference between iterators is a binary search: without knowing the distance, you do not know how much you need to add to the iterator on the left side to get to the middle in O(1) time. Once you know the distance, you can apply the mixed arithmetic of an iterator-scalar to get to the middle, also in constant time.

Note that you can find the distance by repeating the increment of one iterator until you reach another, but it will take O(n) .

You will also need a < b comparison to find out which iterator is on the left side and which is on the right. Without this comparison, you will not be able to verify the input data for your binary search algorithm.

I am confused [that] the subtraction operator should return an int, not an iterator, although “logically” I would expect that an arithmetic operation between two objects of the same type would also return an object of this type.

Subtraction gives you the distance — the number of steps from one point to another. This is a scalar number that does not depend on the type of iterator. The symmetry here is simple: since

 iteratorA + scalar = iteratorB 

simple arithmetic rules tell us that

 scalar = iteratorB - iteratorA