What is the most effective way of iterating a std::vector and why?

Question

In terms of space-time complexity which of the following is best way to iterate over a std::vector and why?

Way 1:

for(std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {     /* std::cout << *it; ... */ } 

Way 2:

for(std::vector<int>::size_type i = 0; i != v.size(); i++) {     /* std::cout << v[i]; ... */ } 

Way 3:

for(size_t i = 0; i != v.size(); i++) {     /* std::cout << v[i]; ... */ } 

Way 4:

for(auto const& value: a) {      /* std::cout << value; ... */ 

Answer 1

First of all, Way 2 and Way 3 are identical in practically all standard library implementations.

Apart from that, the options you posted are almost equivalent. The only notable difference is that in Way 1 and Way 2/3, you rely on the compiler to optimize the call to v.end() and v.size() out. If that assumption is correct, there is no performance difference between the loops.

If it's not, Way 4 is the most efficient. Recall how a range based for loop expands to

{    auto && __range = range_expression ;    auto __begin = begin_expr ;    auto __end = end_expr ;    for ( ; __begin != __end; ++__begin) {       range_declaration = *__begin;       loop_statement    } } 

The important part here is that this guarantees the end_expr to be evaluated only once. Also note that for the range based for loop to be the most efficient iteration, you must not change how the dereferencing of the iterator is handled, e.g.

for (auto value: a) { /* ... */ } 

this copies each element of the vector into the loop variable value, which is likely to be slower than for (const auto& value : a), depending on the size of the elements in the vector.

Note that with the parallel algorithm facilities in C++17, you can also try out

#include <algorithm> #include <execution>  std::for_each(std::par_unseq, a.cbegin(), a.cend(),    [](const auto& e) { /* do stuff... */ }); 

but whether this is faster than an ordinary loop depends on may circumstantial details.