63

I'm used to writing loops like this:

for (std::size_t index = 0; index < foo.size(); index++)
{
    // Do stuff with foo[index].
}

But when I see iterator loops in others' code, they look like this:

for (Foo::Iterator iterator = foo.begin(); iterator != foo.end(); iterator++)
{
    // Do stuff with *Iterator.
}

I find the iterator != foo.end() to be offputting. It can also be dangerous if iterator is incremented by more than one.

It seems more "correct" to use iterator < foo.end(), but I never see that in real code. Why not?

smci
  • 32,567
  • 20
  • 113
  • 146
Maxpm
  • 24,113
  • 33
  • 111
  • 170
  • 4
    It's not correct to use `Iterator <= Foo.End()`. I suppose you rather mean `Iterator < Foo.End()`. – zneak Jul 13 '11 at 03:37
  • 17
    `It can also be dangerous if Iterator is incremented by more than one.` <-- Not really. If the iterator ever goes past `end` you already have undefined behavior. – Billy ONeal Jul 13 '11 at 03:38
  • @zneak It's my understanding that `Foo.End()` equates to the last *index*, whereas `Foo.Size()` equates to the *size* (which is one greater than the last index). So, no, I'm pretty sure `Foo.End()` is still a valid thing to dereference. – Maxpm Jul 13 '11 at 03:40
  • 7
    @Maxpm, in the STL collections, `end()` is one element past the last object of the sequence. It's not a valid thing to dereference. It's also why you can safely use `iter != sequence.end()` without fear of missing the last object of the sequence. – zneak Jul 13 '11 at 03:41
  • 21
    @Maxpm: I'm not talking about dereferencing at all. **Incrementing any iterator past `end` is undefined behavior, whether you dereference it or not**. – Billy ONeal Jul 13 '11 at 04:19
  • @Billy Wait, if any iterator going past the valid range invokes undefined behavior whether you dereference it or not, how is `.end()` even implemented in STL containers? – Maxpm Jul 13 '11 at 07:51
  • 4
    @Maxpm: Which container? It's trivial for a linked-list, for example, just have a null pointer inside the iterator, instead of a valid pointer to a node. For a vector, just one past the end of the internally allocated array is fine. – GManNickG Jul 13 '11 at 08:07
  • @Gman According to the answers to [this](http://stackoverflow.com/questions/3838855/is-storing-an-invalid-pointer-automatically-undefined-behavior) question, simply storing a pointer to an invalid location is undefined. – Maxpm Jul 13 '11 at 08:20
  • 4
    @Maxpm: Yes, but nowhere in my example implementations do I say to point to an invalid location. One past the end of an array is okay. – GManNickG Jul 13 '11 at 08:36
  • @GMan Ah, right. Of course. Sorry, I forgot about that little quirk. – Maxpm Jul 13 '11 at 08:41

2 Answers2

91

All iterators are equality comparable. Only random access iterators are relationally comparable. Input iterators, forward iterators, and bidirectional iterators are not relationally comparable.

Thus, the comparison using != is more generic and flexible than the comparison using <.

There are different categories of iterators because not all ranges of elements have the same access properties. For example,

  • if you have an iterators into an array (a contiguous sequence of elements), it's trivial to relationally compare them; you just have to compare the indices of the pointed to elements (or the pointers to them, since the iterators likely just contain pointers to the elements);

  • if you have iterators into a linked list and you want to test whether one iterator is "less than" another iterator, you have to walk the nodes of the linked list from the one iterator until either you reach the other iterator or you reach the end of the list.

The rule is that all operations on an iterator should have constant time complexity (or, at a minimum, sublinear time complexity). You can always perform an equality comparison in constant time since you just have to compare whether the iterators point to the same object. So, all iterators are equality comparable.

Further, you aren't allowed to increment an iterator past the end of the range into which it points. So, if you end up in a scenario where it != foo.end() does not do the same thing as it < foo.end(), you already have undefined behavior because you've iterated past the end of the range.

The same is true for pointers into an array: you aren't allowed to increment a pointer beyond one-past-the-end of the array; a program that does so exhibits undefined behavior. (The same is obviously not true for indices, since indices are just integers.)

Some Standard Library implementations (like the Visual C++ Standard Library implementation) have helpful debug code that will raise an assertion when you do something illegal with an iterator like this.

James McNellis
  • 348,265
  • 75
  • 913
  • 977
  • 11
    +1; as a concrete example supporting this answer, it'd be hard to implement `operator<` for `std::list::iterator` in less than linear time, but `operator!=` can work in constant time. – zneak Jul 13 '11 at 03:36
  • You also probably mean `it < foo.end()` instead of `it <= foo.end()`. – zneak Jul 13 '11 at 04:00
  • 2
    _Further, you aren't allowed to increment an iterator past the end of the range into which it points. So, if you end up in a scenario where it != foo.end() does not do the same thing as it < foo.end(), you already have undefined behavior because you've iterated past the end of the range._ Is this really the case even if you wouldn't dereference the iterator, but just compared it against end() with "<"? – khuttun Feb 25 '16 at 10:26
  • 2
    @khuttun: You can always advance an iterator to the "past-the-end" iterator, but only *once*. You cannot advance a "past-the-end" iterator; that leads to UB. – Nicol Bolas Dec 11 '16 at 01:30
  • @JamesMcNellis: It's "at most" or "in the worst case", not "at minimum" or "at maximum". Disclaimer: not native English speaker. But right now, with "minimum", the *concept* is wrong. I'm not sure the requirement is there in the standard, but an iterator with higher time complexity would be impractical. – Cheers and hth. - Alf Dec 11 '16 at 02:41
  • @zneak I tested both operators (`!=` and `<`) and I found `!=0` faster than `<`!! – Rishabh Agrahari Aug 12 '17 at 20:09
  • @khuttun: Yes, it is really the case. – Lightness Races in Orbit May 08 '18 at 11:11
  • `you aren't allowed to increment an iterator past the end of the range into which it points` is there any standard reference which confirms this statement? cc @NicolBolas, @Billy ONeal – The Dreams Wind Aug 26 '22 at 16:52
  • @TheDreamsWind: That's what an iterator range *means*. I mean, it is possible for more values to exist past the end point of the range; you can provide subranges and the like. But if your function is given an iterator range to do something with, the inherent expectation is that it is not allowed to access beyond this range. – Nicol Bolas Aug 26 '22 at 16:56
14

Short answer: Because Iterator is not a number, it's an object.

Longer answer: There are more collections than linear arrays. Trees and hashes, for example, don't really lend themselves to "this index is before this other index". For a tree, two indices that live on separate branches, for example. Or, any two indices in a hash -- they have no order at all, so any order you impose on them is arbitrary.

You don't have to worry about "missing" End(). It is also not a number, it is an object that represents the end of the collection. It doesn't make sense to have an iterator that goes past it, and indeed it cannot.

Mike Caron
  • 14,351
  • 4
  • 49
  • 77
  • 1
    But if a structure's elements can't be represented as "before" or "after" each other, does it even make sense to have an iterator for it at all? After all, you wouldn't be able to do `Iterator++`, and the whole point of an iterator is to *iterate*. – Maxpm Jul 13 '11 at 03:45
  • 5
    @Maxpm, iterators are also useful for just enumerating objects. As a concrete example, you cannot fix the order of elements inside an `std::set` to your liking, but it's still iterable. Also, it's not that it's _impossible_ to tell which element comes first; it might be rather that the complexity required is greater than expected (using the tree example, the worst-case scenario for telling which node comes first is much worse than a few comparisons); and as such, it can be better to not implement the feature and have users fall into a sad performance trap. – zneak Jul 13 '11 at 03:47
  • 2
    @Maxpm, Sure, every collection has a physical order as a necessity of being represented in finite space on non-quantum computers. However, that order is completely arbitrary, and not necessarily related to the _logical_ ordering of the collection, if it even has one. So, even if you can iterate (via the physical order), that order doesn't necessarily make sense. – Mike Caron Jul 13 '11 at 16:12
  • 1
    This answer is off the mark. @zneak is right, the problem not that there is no sensible way of implementing `operator<` on collections like `std::set` (which is ordered, after all), the problem is that it would take higher than constant complexity. – Fred Foo Jun 14 '12 at 14:15