Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ iterators & loop optimization

I see a lot of c++ code that looks like this:

for( const_iterator it = list.begin(),
     const_iterator ite = list.end();
     it != ite; ++it)

As opposed to the more concise version:

for( const_iterator it = list.begin();
     it != list.end(); ++it)

Will there be any difference in speed between these two conventions? Naively the first will be slightly faster since list.end() is only called once. But since the iterator is const, it seems like the compiler will pull this test out of the loop, generating equivalent assembly for both.

like image 767
Quantum7 Avatar asked Apr 28 '09 02:04

Quantum7


People also ask

What are iterators in C?

An iterator is an object that allows you to step through the contents of another object, by providing convenient operations for getting the first element, testing when you are done, and getting the next element if you are not. In C, we try to design iterators to have operations that fit well in the top of a for loop.

What is the meaning of iterators?

An iterator is an object that contains a countable number of values. An iterator is an object that can be iterated upon, meaning that you can traverse through all the values.

Is an iterator a pointer?

The most obvious form of an iterator is a pointer. A pointer can point to elements in an array and can iterate through them using the increment operator (++). But, all iterators do not have similar functionality as that of pointers.

What are STL iterators?

An iterator is used to point to the memory address of the STL container classes. For better understanding, you can relate them with a pointer, to some extent. Iterators act as a bridge that connects algorithms to STL containers and allows the modifications of the data present inside the container.


3 Answers

The two versions are not the same though. In the second version it compares the iterator against list.end() every time, and what list.end() evaluates to might change over the course of the loop. Now of course, you cannot modify list through the const_iterator it; but nothing prevents code inside the loop from just calling methods on list directly and mutating it, which could (depending on what kind of data structure list is) change the end iterator. It might therefore be incorrect in some circumstances to store the end iterator beforehand, because that may no longer be the correct end iterator by the time you get to it.

like image 83
newacct Avatar answered Oct 17 '22 16:10

newacct


I'll just mention for the record that the C++ standard mandates that calling begin() and end() on any container type (be it vector, list, map etc.) must take only constant time. In practice, these calls will almost certainly be inlined to a single pointer comparison if you compile with optimisations turned on.

Note that this guarantee does not necessarily hold for additional vendor-supplied "containers" that do not actually obey the formal requirements of being a container laid out in the chapter 23 of the standard (e.g. the singly-linked list slist).

like image 43
j_random_hacker Avatar answered Oct 17 '22 15:10

j_random_hacker


The first one will probably almost always be faster, but if you think this will make a difference, always profile first to see which is faster and by how much.

The compiler will probably be able to inline the call to end() in both cases, although if end() is sufficiently complicated, it may opt not to inline it. However, the key optimization is whether or not the compiler can perform loop-invariant code motion. I would posit that in most cases, the compiler can't be certain that the value of end() won't change during the iteration of the loop, in which case it has no choice but to call end() after each iteration.

like image 11
Adam Rosenfield Avatar answered Oct 17 '22 15:10

Adam Rosenfield