Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there difference between two for form in C++?

Tags:

c++

vector<int> a;

1.

for(vector<int>::iterator it = a.begin(); it != a.end(); ++it)

2.

vector<int>::iterator end = a.end();
for(vector<int>::iterator it = a.begin(); it != end; ++it)

which is more efficient?or the same?

like image 480
lixiang Avatar asked Apr 27 '12 07:04

lixiang


2 Answers

Initial criticisms:

1/ Typical tutorial example

for(vector<int>::iterator it = a.begin(); it != a.end(); ++it)

There is no magic, but it brings up a question: is a ever modified in the loop that the end bound may vary ?

2/ Improved

vector<int>::iterator end = a.end();
for(vector<int>::iterator it = a.begin(); it != end; ++it)

a.end() is only executed once, it seems. However since end is not const, it may be modified inside the loop.

Furthermore, it introduces the end identifier in the outer scope, polluting it.

So there is a potential gain in performance, but not much in clarity. Also, it's far more verbose.


I would propose several other ways:

3/ Best Manual

for(vector<int>::iterator it = a.begin(), end = a.end(); it != end; ++it)

Combines the advantages of v1 (quite terse, no outer scope pollution) and v2 (performance), however it is still unclear if end is ever modified within the loop body.

4/ Boost-powered

BOOST_FOREACH(int& i, a)

Even terser than v1, immediately identifiable at a glance, no outer scope leak, and guarantee of full iteration (it's not possible to modify the bounds).

Unfortunately:

  • there are issues with commas in the type of the variable (because it relies on the preprocessor)
  • compile-time errors are completely cryptic (because it relies on the preprocessor)

Note: in theory, one could make the case of the std::foreach algorithm here, but honestly... there is too much effort involved in defining a predicate outside and it breaks code locality.

5/ C++11 range-for statement

for (int& i: a)

All the advantages:

  • Extremely Terse
  • As performant as the best C++ hand-written loop
  • Guaranteed full iteration, no questions asked

And none of the issues (scope leak, preprocessor magic).


Personally, I use C++11 range-for whenever I can (hobby projects) and BOOST_FOREACH otherwise (at work).

I avoid like the plague modifying the container I am iterating on, preferring to rely on STL algorithms when I need to filter/remove elements... It's too easy to mess up with the boundary conditions and iterator invalidations otherwise.

like image 138
Matthieu M. Avatar answered Sep 29 '22 08:09

Matthieu M.


2nd is more efficient as it only requires creating the end iterator once.

A smart compiler may optimize the first one to be the second, but you cannot be guaranteed that that will happen.

It would actually be a bit of a complicated optimization because the compiler would need to be 100% certain that any subsequent call to end() will have no additional effects or return anything different. Basically, it would need to know that at least over the loop, end() always returns something such that end() == previous call to end(). Whether or not compilers do that optimization is not guaranteed.

like image 36
Corbin Avatar answered Sep 29 '22 07:09

Corbin