65

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?

10
  • 4
    It's not correct to use Iterator <= Foo.End(). I suppose you rather mean Iterator < Foo.End().
    – zneak
    Jul 13, 2011 at 3: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. Jul 13, 2011 at 3:38
  • 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, 2011 at 3: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. Jul 13, 2011 at 4:19
  • 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, 2011 at 8:07

2 Answers 2

92

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.

9
  • 11
    +1; as a concrete example supporting this answer, it'd be hard to implement operator< for std::list<T>::iterator in less than linear time, but operator!= can work in constant time.
    – zneak
    Jul 13, 2011 at 3:36
  • You also probably mean it < foo.end() instead of it <= foo.end().
    – zneak
    Jul 13, 2011 at 4: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, 2016 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. Dec 11, 2016 at 1: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. Dec 11, 2016 at 2:41
15

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.

4
  • 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, 2011 at 3: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<T> 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, 2011 at 3: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, 2011 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, 2012 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.