Sign in to follow this  
Boder

Works for list not for deque/vector

Recommended Posts

Boder    938
Well I was debuggin' one day (or maybe late at night) and I happened upon a bug that warse crashing me program. I was using a deque for a change, not too familiar with it. I would iterate over the elements and erase some of them, and it would crash. I changed it to a std::list and it worked. Changed to a vector and it failed. Here is the code.
	for( MessageItr itr = message.begin(); itr != message.end(); ++itr)
	{
		itr->time -= ElapsedTime;
		if( itr->time < 0.0 )
		{
			//std::cout << "Erasing" << std::endl;
			itr = message.erase( itr );
		}
	}

Maybe you can help me explain this phenomenon.

Share this post


Link to post
Share on other sites
Conner McCloud    1135
Quote:
Original post by Nitage
When you erase from a vector or deque, the iterators to that vector/deque become invalid.

Isn't that the point of erase returning a new iterator?

This leads directly to the problem: erase returns a new iterator. The iterator is the element *after* the one you just deleted. You then end your loop, and that iterator is automatically incremented. If you have to erase the last element, message.erase(i) returns message.end(), which you then proceed to increment.


#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<int> v;
for(int i = 0; i < 10; i++)
v.push_back(i);

vector<int>::iterator i = v.begin() + 5;
cout << "Before erase: " << *i << endl;
i = v.erase(i);
cout << "After erase: " << *i << endl;
i += 3;
cout << "Last element: " << *i << endl;
i = v.erase(i);
cout << ((i == v.end()) ? "We're at the end" : "We're not at the end")<< endl;

system("PAUSE");
return 0;
}


CM

Share this post


Link to post
Share on other sites
Pro-XeX    130
yep, in this case you might use sthg. like :


int size = message.size();
for( int i = 0; i < size; i++)
{
itr->time -= ElapsedTime;
if( itr->time < 0.0 )
{
message.erase( message.begin() + i );
brake;
}
}






actually, you should make use of ::find() to find and remove the element!

[edit]
Conner McCloud beat me to it ;)

Share this post


Link to post
Share on other sites
Nitage    1107
Quote:
you should make use of ::find() to find and remove the element!


If you want to do this with std library functions:

bool shouldEraseMessage(const StoredType& object)
{
return object.time < 0.0;
}

//then to erase
//for vector/deque
message.erase( std::remove_if(message.begin(),message.end(),shouldEraseMessage) , message.end() );

//for list
message.remove_if(shouldEraseMessage);


Share this post


Link to post
Share on other sites
Boder    938
Thanks for all the help and the nice solutions.

So I guess this means it is safe to increment std::list::back() but not std::vector::back().

I know I am never going to have more than five elements and I don't need random access, so I think I will use a list. But might the code crash on another compiler?

Share this post


Link to post
Share on other sites
RDragon1    1205
Nah, it's even simpler than that. Just don't increment the iterator unless you don't erase.


for( MessageItr itr = message.begin(); itr != message.end(); )
{
itr->time -= ElapsedTime;
if( itr->time < 0.0 )
{
//std::cout << "Erasing" << std::endl;
itr = message.erase( itr );
}
else ++itr;
}




Of course, you could (and should, in this example) do this with library functions. First use std::transform to do the subtraction, then apply erase/remove to erase the expired elements.

Quote:

So I guess this means it is safe to increment std::list::back() but not std::vector::back().


That's not what it means - it just means that you were able to do it without noticing. Yes, it might crash in a different environment.

Share this post


Link to post
Share on other sites
Fruny    1658
You shouldn't both grab the return value of erase and increment. Increment only when not erasing. Otherwise, you may very well advance your iterator beyond the end of the container (if you happen to erase the last element, erase returns end() and you increment that... ooops).

For performance, consider combining erase with remove_if. Your code is O(n^2) when it could easily be O(n). That's horribly inefficient.

Share this post


Link to post
Share on other sites
Boder    938
Quote:
Original post by RDragon1
Whos code is O(n^2) ?


I was wondering that too.

I thought about it. It is because erase() runs in O(n) for vector/deque

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