Jump to content
  • Advertisement
Sign in to follow this  
Obbedemus

Iterators vs. size ()

This topic is 3775 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

Been thinking, is there any of these two ways that are better to iterate through a vector than the other?
//1
//v is a vector
for (vector::iterator i = v.begin (); i != v.end (); i++)
	//Do something

//2
//v is a vector
for (int i = 0; i < v.size (); i++)
	//Do something

Fully possible that my code is incorrect, but hopefully the point is made.

Share this post


Link to post
Share on other sites
Advertisement
The better way:
std::for_each(v.begin(), v.end(), &doSomething);


Other than that, your second example should be (note the loop variable type):

for (vector<T>::size_type = 0; i < v.size(); ++i) 
// do something

Share this post


Link to post
Share on other sites
You can't use size() and the random access operator when iterating over all containers from the standard library, not all containers support the random access functionality. This is why i personally always use iterators because it is the same paradigm throughout your application. Also, taking ToohrVyks first code snippet, if you had the iterator type typedef'd away, like so:

typdef std::vector< T >::iterator SomeCollectionIterator;

Then you can swap the vector for another container and leave your iteration code as is.

Share this post


Link to post
Share on other sites
When you use the random access operator, the address of what you're trying to access has to be calculated (i * dataSize), but incrementing an integer is incredibly fast.

Iterators probably point directly to the object, so no calculation is needed and it just needs to add the size of the data type to the pointer to increment.

My bet is iterators are a billionth of a second quicker. You should use them more.

But, for_each is probably just as good, if not better. But, then again, not everything need be turned into a function pointer.

Share this post


Link to post
Share on other sites
Quote:
Original post by Splinter of Chaos
When you use the random access operator, the address of what you're trying to access has to be calculated (i * dataSize), but incrementing an integer is incredibly fast.

Iterators probably point directly to the object, so no calculation is needed and it just needs to add the size of the data type to the pointer to increment.

My bet is iterators are a billionth of a second quicker. You should use them more.

But, for_each is probably just as good, if not better. But, then again, not everything need be turned into a function pointer.


There is not a preexisting set if iterators which already point to the elements in the container, they have to be constructed. When youc all begin() you are being given an iterator that points to the first element. When you iterate throug, the increment operator on the iterator intelligent alters its internal pointer to the next element.

The reason we have iterators is so that we can iterate effortlessly over non-trivial containers, like a tree. It takes alot more know-how to iterate over a binary tree and it is something that the client code should never do manually. So an iterator is provided.

Also note that another good reason to use iterators is because the containers provided rbegin() and rend() so you can reverse iterate over the container. This is cleaner than working out your own begin and end points using size.

Share this post


Link to post
Share on other sites
Quote:
Original post by DaedalusOwnsYou
Quote:
Original post by DevFred
You should prefer ++i to i++, especially when dealing with iterators.


Just out of curiosity, why?


Because i++ has to return the current value, and then increment it, and is usually implemented as:

postincrement(iterator &it)
{
iterator copy = it;
preincrement(it);
return copy;
}


A non-optimizing compiler will therefore have to create and return a copy, even if it isn't used.

Share this post


Link to post
Share on other sites
std::for_each is capable of choosing the most optimal method of iteration by using static iterator dispatching.

In the case of a vector's random access iterators it's likely to use a different operator in the loop's termination condition, so instead of the usual:

iter != end;

It can use something more similar to:

iter < end;

This is usage safe for iterators of a vector, or other contiguous array, and makes things easier for the compiler if it were to apply a loop unrolling optimisation.

Share this post


Link to post
Share on other sites
I am probably in the minority here, but I think this is perfectly fine:
for(unsigned i=0; i<v.size(); ++i) // unsigned because v.size() is unsigned

The main strength of this option is that I find it easier to read. If you find the iterator notation more clear, use it.

Using iterators has one disadvantage that hasn't been mentioned: They are invalidated if you push a new element at the end of the vector, while accessing by index always works. There are certain algorithms that are very naturally expressed by looping through a vector and adding new things at the end, which you will deal with once you get there. The best example I can think of right now is Buchberger's algorithm.

for_each has the obvious disadvantages that you have to write the body of the loop somewhere else or write a horrible expression in place (neither of which is very readable), and you can't easily break out of the loop. The readability issue (which should trump every other consideration in most situations) can be made much better by using lambda expressions, but I think a simple loop doesn't deserve this much complexity.


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!