• 15
• 15
• 11
• 9
• 10

Works for list not for deque/vector

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

Recommended Posts

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 on other sites
When you erase from a vector or deque, the iterators to that vector/deque become invalid.

Share on other sites
Quote:
 Original post by NitageWhen 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 on other sites
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!

Conner McCloud beat me to it ;)

Share on other sites
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/dequemessage.erase( std::remove_if(message.begin(),message.end(),shouldEraseMessage) , message.end() );//for listmessage.remove_if(shouldEraseMessage);

Share on other sites
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 on other sites
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 on other sites
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 on other sites
Whos code is O(n^2) ?

Share on other sites
Quote:
 Original post by RDragon1Whos 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