30

Could anyone help me understand whether there's a big difference in != and < when it comes to talk about vector iterators within a for loop?

I mean, no matter whether you use != and <, the result should be the same?

for (vector<int>::iterator i = vec.begin(); i != vec.end(); i++)
    // DO STUFF

for (vector<int>::iterator i = vec.begin(); i < vec.end(); i++)
    // DO STUFF

I am aware that the most common way is to use !=, but would < be a big issue if used?

Toby Speight
  • 27,591
  • 48
  • 66
  • 103
TheDoomDestroyer
  • 2,434
  • 4
  • 24
  • 45

3 Answers3

40

operator< is only supported for random access iterators. std::vector::iterator is a random access iterator, so both i != vec.end() and i < vec.end() are supported and valid and make no difference in your example.

If you had a container that does not support random access iterators (e.g. std::list), i < list.end() would not compile.

The general recommendation is to use postfix increment only when it is necessary though because it may create an unnecessary copy when the iterator is non-trivial, so ++i is cleaner and may be faster.

Also, if the loop calls a function whose definition is not available in this translation unit vec.end() is going to be reloaded from memory on each loop iteration, which might cause an unnecessary cache miss. You can avoid that reload by saving the value into a local variable, so that the compiler is certain that the local variable is inaccessible to any other function:

for(vector<int>::iterator i = vec.begin(), j = vec.end(); i < j; ++i)
    // ...

Even better, you may like to use range-for loops that avoid these performance pitfalls for you:

for(auto const& elem : vec)
    // ...
Maxim Egorushkin
  • 131,725
  • 17
  • 180
  • 271
  • Can you provide an example of a container where vec.end would be recomputed every time? (I'm curious bc I don't want to write code that does that) – sudo rm -rf slash Jan 30 '18 at 13:51
  • 6
    @sudorm-rfslash https://godbolt.org/g/VyQMkH - in `slow` it reloads `end()` from memory, in `fast` it keeps it in a register. – Maxim Egorushkin Jan 30 '18 at 14:21
  • 1
    @sudorm-rfslash So, the thing is that the compiler has to *prove* that the vector is not modified if you invoke `.end()` to cache it, and proving that is often hard. If you cache it, it is up to *you* to prove that (or your code risks UB). Proving it is sometimes hard. Which of these two you prefer is a choice. – Yakk - Adam Nevraumont Jan 30 '18 at 16:37
  • It's sometimes worth iterating backwards just to avoid the reload of end() ... if you're indexing into the vector, you need the value of begin(), so you can just do `auto i = v.end(); while (i != v.begin()) { /* do something with *--i */ }` – Will Crawford Jan 31 '18 at 00:43
  • @MaximEgorushkin you're right, it was ~1am here and not thinking. Could we delete these comments and never speak of it? :o) – Will Crawford Jan 31 '18 at 12:02
11

The entire philosophy behind the STL part of the Standard Library (the containers, iterators and algorithms) is to minimize the programatic distinctions between the containers. They exhibit different properties but how you program them is designed to be as similar as possible.

This makes them easier to learn and easier to use generically. That means you can write one generic function (or algorithm) and have it apply to any other container (or as many as possible).

With that in mind it is beneficial to use syntax that is common to all containers and iterators where possible.

Only some containers' iterators allow < comparisons but all containers' iterators accept !=. For that reason I would recommend always using != as a matter of consistency and to facilitate your code being easily ported to a different container.

Galik
  • 47,303
  • 4
  • 80
  • 117
  • 2
    Concerning the last paragraph: more generally, only some iterator types allow `<` comparisons but all iterator types (other than simple output iterators) accept `!=`. Containers are one source of iterators, but they are not the only one. – Pete Becker Jan 30 '18 at 14:03
9

It does make a difference, although not for std::vector. All iterators are equality comparable, so != will always work. Only random access iterators are less than comparable, as is std::vector, so in your case it wouldn't be a big issue.

Demosthenes
  • 1,515
  • 10
  • 22
  • 2
    Not all iterators are equality comparable. Output iterators, for example. – Incomputable Jan 30 '18 at 13:35
  • @Incomputable This statement also appears in https://stackoverflow.com/a/6673775/3182664 - if it is wrong, then the answer there should be fixed (according to http://en.cppreference.com/w/cpp/concept/InputIterator it should be safe to say that "All **input** iterators are equality-comparable" - possibly with a link to this exact site) – Marco13 Jan 31 '18 at 03:14