Fast iteration over STL vector elements

The STL class std::vector is a great container for managing dynamic arrays. Unfortunately it introduces a slight overhead when iterating through it using an index. For example, the following code is not very efficient:

std::vector<int> data( /* some data */ );
for(int i = 0; i < data.size(); i++)
{
  foo(data[i]);
}

First, the size of the array is not stored explicitly in the array structure, therefore data.size() has to calculate the size on each call. Also, the index operator data[i] introduces some overhead such as checking for index-out-of-bounds and looking up the starting address of the array.

Using STL iterators, it's possible to get rid of these disadvantages:

for(std::vector<int>::const_iterator it = data.begin(); 
    it != data.end(); ++it)
{
  foo(*it);
}

data.begin() and data.end() just read a member element of the std::vector object and therefore are really fast. If you also need access the index in your for-loop, you can calculate it by calling index = it - data.begin().

The third alternative which gives you the fastest code for both element access and index it to transform the std::vector into a C-style array:

const int num = data.size();
const int* ptr = (num > 0) ? data.data() : nullptr;
for(int i = 0; i < num; i++)
{
  bar[i] = foo(ptr[i]);
}

Be sure to check that the array has at least one element, otherwise data.data() fails. This method is also useful if you need to pass a pointer to an array to a method which does not accept a std::vector without copying the data.

void someFunc(const int* p, int N);
/* ... */
const int num = data.size();
const int* ptr = (num > 0) ? data.data() : nullptr;
someFunc(ptr, num);

Last but not least, I would like to point out a beautiful and fast method to iterate over all elements of a std::vector: the C++ 11 range-based loop.

/* ... */
std::vector<int> data = /* ... */;
for( auto i : data )
{
  foo(i);
}

Besides a very simple syntax, the range-based for loop maximizes the speed for iterating over all elements. And that's exactly what I have found out myself. So I suggest, for simplicity and efficiency, use this feature whenever possible.

On older compilers, you could also use the BOOST_FOREACH loop from the Boost-Library.

#include <boost/foreach.hpp>
/* ... */
std::vector<int> data = /* ... */;
BOOST_FOREACH( int i, data )
{
  foo(i);
}