Jump to content
  • Advertisement
Sign in to follow this  
atimes

C++ iterator vs []

This topic is 3753 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This should be a simple enough question but I can't seem to find anything on the web or searching through the forums. If I have a vector and want to iterate through the members is it faster to use the "at" or "[]" function/operator or an iterator? Since the "at" and "[]" functions run in constant time do you gain anything from using an iterator? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
The most you gain from using an iterator is that your code is ready for nearly all STL-containers. So if you decide your vector should have been a list, you can simply switch the declaration, and need not touch all the places where you iterate through the list (especially if you used a typedef).

Share this post


Link to post
Share on other sites
You use an iterator when you want to iterate over your set.

If you know exactly where your element is, then simply index to that position using at() or operator[].

If you need to perform a search for example, supply an iterator range to std::find, std::find_if etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by fpsgamer
You use an iterator when you want to iterate over your set.

If you know exactly where your element is, then simply index to that position using at() or operator[].

If you need to perform a search for example, supply an iterator range to std::find, std::find_if etc.


However my question remains. If I want to loop over my list is it faster to use an iterator in a for loop or a for loop with vector?

Thanks.

Based on the first response it seems like it doesn't really matter which I do. . .

Share this post


Link to post
Share on other sites
Quote:
Original post by atimes
However my question remains. If I want to loop over my list is it faster to use an iterator in a for loop or a for loop with vector?

The iterators for std::vector are essentially pointers (possibly they are pointers). So no, there's no performance difference between [] and using iterators. At() of course incurs the penalty of bound checking.

Share this post


Link to post
Share on other sites
Quote:
Based on the first response it seems like it doesn't really matter which I do. . .


No it doesn't. Iteration mechanisms are more versatile and generic, though. You can abstract away all the underlying peculiarities with them, and for instance copy stuff using one function, regardless of the actual containers. Yeah, the STL exploits this a lot.

If you're interested, I suggest you look into some advanced iterator concepts (beyond the STL), such as separating traversal from access. Beyond this lie fiber bundles and sheafs, which separate containers into a base space (the container's topology) and fiber space (the values each container element can have). These things are very interesting especially for manipulating meshes, so its worth looking into them.

Share this post


Link to post
Share on other sites
Quote:

Since the "at" and "[]" functions run in constant time do you gain anything from using an iterator?

Yes. You gain clarity. You show exactly what it is your code is supposed to do.
When you use an iterator, it's a strong hint, to the compiler and to people reading your code, that you want to iterate over your container.

Making your intent clear is one of the most important things to strive for when programming. Both because it makes your code easier to maintain, and because it *may* make it faster.

Microsoft's Visual C++ compiler, for example, performs bounds-checking on std::vector's operator[], because it assumes that you want to perform a single lookup. So it can't make assumptions about what happened before, or what'll happen next.

When using iterators, it doesn't do bounds-checking (other than at the beginning and end of the standard algorithms). That's because if you're doing, say, std::for_each on an iterator range, it knows that if you're going to go out of bounds, it'll happen either at the beginning or the end of the range. So it only has to do a bounds-check in those two cases.

I don't entirely agree with their decision to do bounds-checking on vectors by default at all, but since they do it, at least they try to respect the intent of your code. If you're using iterators, they assume you want to iterate, and so they make shortcuts that are only valid when iterating. When you index directly into the vector, they assume that you're doing one single independent lookup, so they play it safe and perform a bounds-check every time.

So in at least one case, using iterators to iterate is the fastest option. Not because iterators are "better" or "faster" than operator[], but because they show the intent of your code, and the compiler/standard library *may* be able to then make assumptions that'll speed up your specific use case.

at() on the other hand will never be faster than the two other options. It's the only one that *requires* bounds-checking on every access.

But usually, a good rule of thumb is that if it's trivial for you to switch between two different options, then the compiler can probably do so as well. If, say, iterators were slower than operator[], don't you think the compiler would attempt to replace all use of iterators with operator[]?

Share this post


Link to post
Share on other sites
I guess it depends on the compiler.

You could do your own tests. I tried summing an enormous amount of random integers and found preformance-wise that with Mingw
1.-2. iterators, std::accumulate
3. indices

and with VC++
1. std::accumulate
2. iterators
3. indices

(Morale, use library algorithms if possible.)

There is no reason vector's iterators should be slower. They are very little more than plain pointers. However, using iterators instead makes your code a bit more "generic".

And in some loops performance might not be that important, so I'd use BOOST_FOREACH (sadly looks like a lot slower than the others). :)

Share this post


Link to post
Share on other sites
Quote:
Original post by atimes
Quote:
Original post by fpsgamer
You use an iterator when you want to iterate over your set.

If you know exactly where your element is, then simply index to that position using at() or operator[].

If you need to perform a search for example, supply an iterator range to std::find, std::find_if etc.


However my question remains. If I want to loop over my list


Quote:
Original post by fpsgamer
You use an iterator when you want to iterate over your {container}.


"Iterate" basically means "loop". Any further questions? :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!