Sign in to follow this  
51mon

Erase elements correctly when traverse a vector?

Recommended Posts

51mon    342
I’m currently porting from VS 2003 to 2005 and I find that it behaves different in some contents. In the code (below) I got run time errors. How do I make it right? I think the iterator get out of range.
for(itrForward = vecActiveLights.begin(); itrForward != vecActiveLights.end(); itrForward++)
{
	if(bCondition)
	{
		// Do some computation
		itrForward = vecActiveLights.erase(itrForward);
	}
}
Thanks

Share this post


Link to post
Share on other sites
Palidine    1315
what you have is almost correct.

for this i find it more intuitive to use a while loop


itrForward = vecActiveLights.begin();
while( itrForward != vecActiveLights.end() )
{
if(bCondition)
{
// Do some computation
itrForward = vecActiveLights.erase(itrForward);
}
else
{
++itrForward;
}
}





when the "itrForward = vecActiveLights.erase(itrForward);" line is executed you are not supposed to increment the iterator (which is what happens with your current implementation).

the erase() method returns the _next_ iterator in the sequence, not the current.

-me

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Palidine is correct in what he says, but I would prefer this method or just plain std::swap and deferencing the iters.

itrForward = vecActiveLights.begin();
while( itrForward != vecActiveLights.end() )
{
if(bCondition)
{
// Do some computation
std::iter_swap(itrForward,vecActiveLights.end()-1);
vecActiveLights.pop_back();
}
else
{
++itrForward;
}
}

Share this post


Link to post
Share on other sites
Palidine    1315
AP, what happens when the swap does nothing (i.e. bCondition is true for the last element in the array). Doesn't the pop_back method then invalidate the itrForward iterator?

Otherwise, yea, a swap -> pop_back will end up being faster in the case of a vector b/c it won't invoke a memcpy to collapse the array.

-me

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Good question Palidine, thats what I get for copy and pasting your code.
Would it invalidate it or would it be equal to the end iter? hmm

Share this post


Link to post
Share on other sites
Palidine    1315
Yeah, might just be equal to end. From the SGI STL site:

Quote:

It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.


So since this is a deletion at the end that would suggest that the iterator is perhaps fine. I'm not sure of the inner workings of iterators, but in a vector i'd assume there is just some pointer offset stuff going on. Assuming .end() is sizeof(T) greater than the last valid element, should be ok. Don't know how your method would fare if the container being iterated were not a vector though...

*goes to learn more about STL =)

-me

Share this post


Link to post
Share on other sites
51mon    342
Thanks guys :) Palidines suggestion worked just fine. But I didn’t manage to get the other one to work; wouldn't I need to set the itrForward focus somehow (after the swap and pop)?

Share this post


Link to post
Share on other sites
Enigma    1410
vecActiveLights.erase(std::remove_if(vecActiveLights.begin(), vecActiveLights.end(), ConditionFunctor()), vecActiveLights.end());
Safe, efficient, idiomatic.

Σnigma

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Enigma
vecActiveLights.erase(std::remove_if(vecActiveLights.begin(), vecActiveLights.end(), ConditionFunctor()), vecActiveLights.end());
Safe, efficient, idiomatic.

Σnigma


So idiomatic that I even wrap it in a function and grumble at the design of <algorithm> a little bit. (Having a function does provide benefit in terms of code duplication in addition to readability: you avoid mentioning .end() twice, and the container three times.)

Oh, and please reconsider your use of Hungarian notation, and declare your for-loop variables in-line. This is modern C++; we have a real type system and fully baked scoping rules now.

Share this post


Link to post
Share on other sites
51mon    342
I have another question about STL.

When I refer to elements outside the domain of an iterator, for example itrForward+1 when itrForward == vecExample.end(), the application automatically prone and I got error messages. This is a good feature most of the time but I would like to turn that off, can I do that somehow?

Share this post


Link to post
Share on other sites
ToohrVyk    1595
Quote:
Original post by 51mon
When I refer to elements outside the domain of an iterator, for example itrForward+1 when itrForward == vecExample.end(), the application automatically prone and I got error messages. This is a good feature most of the time but I would like to turn that off, can I do that somehow?


There are two different aspects here. The error messages are a feature of your implementation of the SC++L that you might be able to turn off. However, the fact that the application stops, crashes, or misbehaves, is a consequence of the standard, which makes incrementing iterators past the end result in undefined behavior.

So, even if you did manage to remove the helpful error messages, your code would still be prone to crashes (only they would happen at random or do more insidious things, like memory corruption).

In short, don't iterate past the end of containers.

Share this post


Link to post
Share on other sites
51mon    342
Quote:
Original post by ToohrVyk
Quote:
Original post by 51mon
When I refer to elements outside the domain of an iterator, for example itrForward+1 when itrForward == vecExample.end(), the application automatically prone and I got error messages. This is a good feature most of the time but I would like to turn that off, can I do that somehow?


There are two different aspects here. The error messages are a feature of your implementation of the SC++L that you might be able to turn off. However, the fact that the application stops, crashes, or misbehaves, is a consequence of the standard, which makes incrementing iterators past the end result in undefined behavior.

So, even if you did manage to remove the helpful error messages, your code would still be prone to crashes (only they would happen at random or do more insidious things, like memory corruption).

In short, don't iterate past the end of containers.


Ok, I can see that but on this line for example:

while(w < (itrThis-1)->vScreenCenter.x && itrThis != vecActiveLights.begin())

Wouldn't it be safe? I can solve it with other arrangement but it save some lines and it's a real time application so time is an issue. I happen to have several locations in the code where it would be nice if I could refer to outside the domain.

Share this post


Link to post
Share on other sites
Enigma    1410
while (itrThis != vecActiveLights.begin() && w < (itrThis-1)->vScreenCenter.x)

is fine assuming itrThis is valid at the start of the loop (also assuming you haven't overloaded a bunch of operators with unusual return types).

while (w < (itrThis-1)->vScreenCenter.x && itrThis != vecActiveLights.begin())

is not fine. If itrThis is vecActiveLights.begin() then (itrThis-1) points at random memory. You cannot dereference an invalid iterator and expect anything sensible. The iterator may be pointing at random memory which is not owned by your process, which is why code like this sometimes crashes.

Σnigma

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Hungarian notation makes my poo runny, and the compiler will fix my for-loop variables if it decides to. This is modern computing, we have a real compiler and optimizer now.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this