C++: Proper way to iterate over STL containers

Question

In my game engine project, I make extensive use of the STL, mostly of the std::string and std::vector classes.

In many cases, I have to iterate through them. Right now, the way I'm doing it is:

for( unsigned int i = 0; i < theContainer.size(); i ++ )
{

}

• Am I doing it the right way?

• If not, why, and what should I do instead?

• Is size() really executed every loop cycle with this implementation? Would the performance loss be negligible?

Solution 1

C++11 has a new container aware for loop syntax that can be used if your compiler supports the new standard.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() 
{
    vector<string> vs;
    vs.push_back("One");
    vs.push_back("Two");
    vs.push_back("Three");

    for (const auto &s : vs)
    {
        cout << s << endl;
    }

    return 0;
}

Solution 2

You might want to look at the standard algorithms.

For example

vector<mylass> myvec;

// some code where you add elements to your vector

for_each(myvec.begin(), myvec.end(), do_something_with_a_vector_element);

where do_something_with_a_vector_element is a function that does what goes in your loop

for example

void 
do_something_with_a_vector_element(const myclass& element)
{
 // I use my element here
}

The are lots of standard algorithms - see http://www.cplusplus.com/reference/algorithm/ - so most things are supported

Solution 3

STL containers support Iterators

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

size() would be re-computed every iteration.

Solution 4

• For random-access containers, it's not wrong.

• But you can use iterators instead.

  for (string::const_iterator it = theContainer.begin();
       it != theContainer.end(); ++it) {
      // do something with *it
  }
  

• There are some circumstances under which a compiler may optimize away the .size() (or .end() in the iterator case) calls (e.g. only const access, function is pure). But do not depend on it.

Solution 5

Usually the right way to "iterate" over a container is using "iterators". Something like

string myStr = "hello";
for(string::iterator i = myStr.begin(); i != myStr.end(); ++i){
    cout << "Current character: " << *i << endl;
}

Of course, if you aren't going to modify each element, it's best to use string::const_iterator.

And yes, size() gets called every time, and it's O(n), so in many cases the performance loss will be noticeable and it's O(1), but it's a good practice to calculate the size prior to the loop than calling size every time.

View more solutions

Comments

[genpfault]

Needs more const_iterator :)

[jamil ahmed]

I disagree. The complexity of size() is constant. See cplusplus.com/reference/stl/vector/size

[David Thornley]

for_each requires a function or functor to apply. It will be a lot nicer with the C++0x lambdas.

[James McNellis]

Well, it should be constant. Only in a braindead implementation would it not be constant, but technically there is no complexity requirement for the size() member function of containers (and some implementations of some containers, e.g. std::list in libstdc++, take advantage of this). C++0x adds the requirement that any container that supports size() must do so with constant time complexity.

[David Thornley]

Don't get .size() confused with strlen, which is O(n) and will automatically make loops requiring it at least O(n^2) complexity.

[José Tomás Tocino]

Edited to include your thoughts.

[Girish Rao]

v.end() is also updated although usually optimized. Modifying the container while iterating through the iterator is tricky business, depending on the exact operation one is performing on the container. For example calling erase on the container nullifies the iterator and the iterator returned by erase needs to be used. Here is some further info: bytes.com/topic/c/answers/…

[Martin York]

both end() and size() is also optimizeable so they do little to zero work.

[Girish Rao]

@Martin agreed. Using iterators in C++ is seen more as a "best practice" to achieve generalizable code (swap in other containers). Can also be helpful when one wants to touch every element and/or when indexing of the container, for example a tree, is not immediately obvious.

[Kyle C]

+1 for_each is the proper usage and as David said, this only gets sweeter when you use C++0x and lambdas.

[josesuero]

Usually, the point in iterators is that they enable you to use the standard library algorithms, instead of writing the loop yourself. This seems like only half an answer.

[ephemient]

It is often advised to use functor objects rather than function pointers, as the former are more likely to be inlined by the compiler. (There's other benefits too.)

[Tom]

@ephemient Thanks! I didn't know functors were better than functions in the standard algorithms. (do you have to hand somewhere I can read more)

[ephemient]

Just ask Stack Overflow. Using STL algorithms, is it better to pass a function pointer or a functor?

[Konrad Rudolph]

This is slightly misleading. The call to size or end will always be optimized away. The variable lookup won’t. So we no longer have to deal with the overhead of the call, but we still need to look up the memory.

[Vincent Robert]

C++11 also allows you to write vector<string> vs = { "One", "Two", "Three" };.