9

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?

3
  • You should probably use size_t instead of unsigned int.
    – Maxpm
    Feb 7, 2011 at 18:59
  • 3
    @Maxpm - Or, better yet, ::std::vector<Foo>::size_type. Feb 7, 2011 at 19:07
  • 1
    begin() and end() have a guaranteed complexity of O(1). While size only has a guarantee of O(n) on general containers (though string and vector may have additional guarantees over the generic). Feb 7, 2011 at 19:38

8 Answers 8

15

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;
}
1
  • 4
    C++11 also allows you to write vector<string> vs = { "One", "Two", "Three" };. May 30, 2014 at 21:39
7

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

5
  • 1
    for_each requires a function or functor to apply. It will be a lot nicer with the C++0x lambdas. Feb 7, 2011 at 18:57
  • +1 for_each is the proper usage and as David said, this only gets sweeter when you use C++0x and lambdas.
    – Kyle C
    Feb 7, 2011 at 22:49
  • 1
    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.)
    – ephemient
    Feb 10, 2011 at 4:39
  • @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)
    – Tom
    Feb 10, 2011 at 8:27
  • 1
4

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.

4
  • 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/…
    – Girish Rao
    Feb 7, 2011 at 19:27
  • 2
    both end() and size() is also optimizeable so they do little to zero work. Feb 7, 2011 at 19:35
  • @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.
    – Girish Rao
    Feb 7, 2011 at 19:47
  • 1
    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.
    – jalf
    Feb 8, 2011 at 3:02
2
  • 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.

1
  • 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. Feb 16, 2011 at 18:18
2

No, this is not the correct way to do it. For a ::std::vector or a ::std::string it works fine, but the problem is that if you ever use anything else, it won't work so well. Additionally, it isn't idiomatic.

And, to answer your other question... The size function is probably inline. This means it likely just fetches a value from the internals of ::std::string or ::std::vector. The compiler will optimize this away and only fetch it once in most cases.

But, here is the idiomatic way:

for (::std::vector<Foo>::iterator i = theContainer.begin();
     i != theContainer.end();
     ++i)
{
    Foo &cur_element = *i;
    // Do stuff
}

The ++i is very important. Again, for ::std:vector or ::std::string where the iterator is basically a pointer, it's not so important. But for more complicated data structures it is. i++ has to make a copy and create a temporary because the old value needs to stick around. ++i has no such issue. Get into the habit of always using ++i unless you have a compelling reason not to.

Lastly, theContainer.end() will also be generally optimized out of existence. But you can force things to be a little better by doing this:

const ::std::vector<Foo>::iterator theEnd = theContainer.end();

for (::std::vector<Foo>::iterator i = theContainer.begin(); i != theEnd; ++i)
{
    Foo &cur_element = *i;
    // Do stuff
}

Of course, C++0x simplifies all of this considerably with a new syntax for for loops:

for (Foo &i: theContainer)
{
     // Do stuff with i
}

These will work on standard fix-sized arrays as well as any type that defines begin and end to return iterator-like things.

1

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.

5
  • 3
    Needs more const_iterator :)
    – genpfault
    Feb 7, 2011 at 18:52
  • 5
    I disagree. The complexity of size() is constant. See cplusplus.com/reference/stl/vector/size
    – i_am_jorf
    Feb 7, 2011 at 18:53
  • 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. Feb 7, 2011 at 18:58
  • Don't get .size() confused with strlen, which is O(n) and will automatically make loops requiring it at least O(n^2) complexity. Feb 7, 2011 at 18:58
  • Edited to include your thoughts. Feb 7, 2011 at 18:59
1

Native for-loop (especially index-based) - it's C-way, not C++-way.

Use BOOST_FOREACH for loops.

Compare, for container of integers:

typedef theContainer::const_iterator It;
for( It it = theContainer.begin(); it != theContainer.end(); ++it ) {
    std::cout << *it << std::endl;
}

and

BOOST_FOREACH ( int i, theContainer ) {
    std::cout << i << std::endl;
}

But this is not perfect way. If you can do your work without loop - you MUST do it without loop. For example, with algorithms and Boost.Phoenix:

boost::range::for_each( theContainer, std::cout << arg1 << std::endl );

I understand that these solutions bring additional dependencies in your code, but Boost is 'must-have' for modern C++.

0

You're doing it OK for vectors, although that doesn't translate into the right way for other containers.

The more general way is

for(std::vector<foo>::const_iterator i = theContainer.begin(); i != theContainer.end; ++i)

which is more typing than I really like, but will become a lot more reasonable with the redefinition of auto in the forthcoming Standard. This will work on all standard containers. Note that you refer to the individual foo as *i, and use &*i if you want its address.

In your loop, .size() is executed every time. However, it's constant time (Standard, 23.1/5) for all standard containers, so it won't slow you down much if at all. Addition: the Standard says "should" have constant complexity, so a particularly bad implementation could make it not constant. If you're using such a bad implementation, you've got other performance issues to worry about.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.