C ++: the right way to iterate over STL containers

Question

In my engine project, I use STL extensively, mainly from the std::string and std::vector classes.

In many cases, I have to go through them. Right now, as I do it:

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

• Am I doing it right?

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

• Is there a loop loop every time with this implementation? Will the performance loss be negligible?

Answer 1

C ++ 11 has a new container designed for loop syntax, which 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; } 

Answer 2

STL containers support iterators

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

size () will reinstall on each iteration.

Answer 3

You can see 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 happens in your loop

eg

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

Many standard algorithms - see http://www.cplusplus.com/reference/algorithm/ - this is how most things are supported

Answer 4

• For containers with random access, this is not so.

• 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 in which the compiler can optimize .size() (or .end() requests in an iterator) (for example, only const access, pure function). But do not depend on it.

Answer 5

Usually the correct way to “iterate” over a container is to use “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 are not going to change each element, it is better to use string::const_iterator .

And yes, size() is called every time, and its O (n), so in many cases the performance loss will be noticeable and this is O (1), but it is good practice to calculate the size before the loop, and not to call the size every time.

Answer 6

No, this is not the right way to do this. For ::std::vector or ::std::string it works fine, but the problem is that if you ever use anything else, it won’t work that well. Also, this is not idiomatic.

And to answer your other question ... The size function is probably inline. This means that it most likely extracts the value from the internal elements ::std::string or ::std::vector . The compiler optimizes this and only retrieves 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 } 

++i very important. Again, for ::std:vector or ::std::string , where the iterator is basically a pointer, this is not so important. But for more complex data structures, this is so. i++ must make a copy and create a temporary one, because the old value must be adhered to. ++i does not have such a problem. Get in the habit of always using ++i unless you have a good reason not to.

Finally, theContainer.end() will also be generally optimized from existence. But you can make things 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 greatly simplifies all this thanks to the new syntax for for loops:

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

They will work with standard arrays of fixed sizes, as well as with any type that defines begin and end to return iterative things.

Answer 7

Native for-loop (especially index-based) is a C-shaped, not C ++ -based path.

Use BOOST_FOREACH for loops.

Compare for a 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 an ideal way. If you can do your job without a loop, you MUST do it without a loop. For example, with algorithms and Boost.Phoenix:

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

I understand that these solutions add additional dependencies to your code, but Boost is a must for modern C ++.

Answer 8

You are doing this normally for vectors, although this does not match the correct path for other containers.

More general way

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

which is more typing than I really like, but will become much more sensible with redefining auto in the upcoming Standard. This will work on all standard containers. Note that you refer to a separate foo as *i and use &*i if you want its address.

In your loop, .size() is executed every time. However, this is a constant time (standard, 23.1 / 5) for all standard containers, so it will not slow you down, if at all. Addition: The standard says that it must have constant complexity, so a particularly poor implementation may make it not permanent. If you use such a poor implementation, you will have to worry about other performance issues.