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

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; ... */

Solution 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.

Solution 2:

Prefer iterators over indices/keys.

While for vector or array there should be no difference between either form¹, it is a good habit to get into for other containers.

_{¹As long as you use [] instead of .at() for accesssing by index, of course.}

Memorize the end-bound.

Recomputing the end-bound at each iteration is inefficient for two reasons:

In general: a local variable is not aliased, which is more optimizer-friendly.
On containers other than vector: computing the end/size could be a bit more expensive.

You can do so as a one-liner:

for (auto it = vec.begin(), end = vec.end(); it != end; ++it) { ... }

(This is an exception to the general prohibition on declaring a single variable at a time.)

Use the for-each loop form.

The for-each loop form will automatically:

Use iterators.
Memorize the end-bound.

Thus:

for (/*...*/ value : vec) { ... }

Take built-in types by values, other types by reference.

There is a non-obvious trade-off between taking an element by value and taking an element by reference:

Taking an element by reference avoids a copy, which can be an expensive operation.
Taking an element by value is more optimizer-friendly¹.

At the extremes, the choice should be obvious:

Built-in types (int, std::int64_t, void*, ...) should be taken by value.
Potentially allocating types (std::string, ...) should be taken by reference.

In the middle, or when faced with generic code, I would recommend starting with references: it's better to avoid a performance cliff than attempting to squeeze out the last cycle.

Thus, the general form is:

for (auto& element : vec) { ... }

And if you are dealing with a built-in:

for (int element : vec) { ... }

_{¹This is a general principle of optimization, actually: local variables are friendlier than pointers/references because the optimizer knows all the potential aliases (or absence, thereof) of the local variable.}