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?

Jeroboam

In search algorithms you might need the distance (a-b). After getting a-b in constant time you get <, >, too. – Feeble

Not intended to be -pedantic, but the correct term in this case is category, not interface. Also that differences are the hole point about duck typying vs inheritance approach. – Porett

@Porett See corrected post :) – Jeroboam

@DieterLücking So that is the first thing that I find confusing; 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. That is not to say I don't understand the need for std::distance of course. – Jeroboam

@Sh3ljohn: Why would finding the difference between two locations return a location rather than a distance? Subtracting two points gives an offset, and subtracting two timepoints gives a duration. – Wop

@Sh3ljohn the difference of two iterators is a difference_type (which is not an iterator) – Feeble

The difference between two points (maths) is a point (or vector, depending on the context). You may express the distance between them using this difference, but there is no reason why the difference between two locations should be a distance I think. – Jeroboam

@Sh3ljohn: The difference between two points is not a point. It may be a vector, but the vector represents an offset. A vector may only represent a point if you assume that it's an offset from the origin (adding a point and an offset gives a point). Assuming you're right: What location is the result of the location of my chair minus the location of your chair? – Wop

@Sh3ljohn In Math (!) the statement The difference between two points (maths) is a point is plain wrong – Feeble

The difference between two points in an Euclidian space is a vector. The difference between two points in the complex plane is a point. – Jeroboam

@Sh3ljohn: The usual statement is that the difference between two complex numbers is a complex number itself. But plenty of counterexamples: What's the difference between 27°C and 28°C ? And between 300K and 301K ? – Stomy

@Stomy I think we are running in circles with these arguments; the fact that the object and the quantity coincide in value in one-dimensional spaces doesn't mean that they are identical. This is almost a discussion on the topology of iterables; it's all about defining how the operations shape the structure of the code that will use iterators. Expecting that a difference between two objects of type T yields an object of type T is most certainly natural. – Jeroboam

@Sh3ljohn: It's not topology but algebra. Subtraction is the inverse of addition, and you're assuming addition on Abelian groups. Iterators do not form an Abelian group. – Stomy

@Stomy :) Where did I assume any structure of group, or talk about any inverse of addition? Topology means literally "study of spatial arrangement" (well, we could talk about the greek root topos, it's latin equivalent locus, and their usage in modern languages), which is precisely what I meant when I was talking about the structure of the code. The difference 300K - 301K is 1 Kelvin; using real numbers to represent temperatures in Kelvin doesn't allow you to ignore the unit. 1 is a number, 1K is an object, no? Would you like to continue in a chat perhaps? – Jeroboam

Ok - chat.stackoverflow.com/rooms/59222/… – Stomy

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

Rea

Thank you for your answer. I think it answers partially my question; I would still like to understand why the standard would include these constraints in the definition of a "random-access iterator" though. – Jeroboam

@Sh3ljohn The standard needed iterators capable of "abstracting out" the semantic of a pointer for the purposes of working with algorithms of the standard library, such as sorting and binary searching, without breaking the asymptotic timing of these algorithms. These algorithms need to find midpoints and compare locations within the same range. When they are implemented in terms of pointers, they subtract and compare pointers; the standard made it a requirement for random access iterators to be capable of doing the same, so that a single algorithm could work both on pointers and on iterators. – Rea

Alright, I think your answer is excellent even though I don't really agree yet with the fact that a random access iterator and a pointer should conceptually behave in the same way. But this would become an opinionated discussion and I guess this is not the place to have it :) Thanks again – Jeroboam