The correct way to remove elements from an STL vector?

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

Recommended Posts

Hello, I am currently using this loop to remove elements from a vector which meet certain criteria, i.e. they are flagged as temporary.
// Remove all the temporary entities
for(vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();it != ScreenEntityList.end();walker++)
{
if(((*it)->GetFlags() & SCREENENTITY_TEMPORARY) > 0)
{
(*it)->Release();
ScreenEntityList.erase(it);
}
}


This seems to plunge me into am infinite loop. Could somebody please show me the correct way to do this and if possible explain why their's works and why mine doesn't. Thanks in advance. Mark Coleman

Share on other sites
for(vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();it != ScreenEntityList.end();it++)

walker should be it, I guess...

Share on other sites
When you erase an element from a vector, the iterator becomes invalid. Thus, trying to use it to continue iterating through the vector is bad. Fortunately, when you call erase() it returns an iterator that is valid, and that points to the next item after the erased one. However, if this is the case, then you don't want to increment the iterator, because it is already pointing at the next item. So you'll need to either A) not erase an element, and increment the iterator, or B) erase an element, and not increment the iterator. A while loop will look nicer in this case.
vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();while (it != ScreenEntityList.end()){	if(((*it)->GetFlags() & SCREENENTITY_TEMPORARY) > 0)	{		(*it)->Release();		it = ScreenEntityList.erase(it);	}	else	{		++it;	}}

Share on other sites
you do 'walker++'. Should be 'it++'.
But I think things might still go wrong. You are removing elements from the container you are iterating over. I'm not entirely sure, but I think 'it' will become invalid once you erase the element from the vector.

-edit: listen to Agony. He seems to know what he is talking about ;-)

Share on other sites
After you call erase, it is going to be a hanging pointer. I'm surprised it doesn't crash. Anyway, the reason it loops is that you increment walker, not it.

Share on other sites
4 replies in about 150 seconds, that's why I love Gamedev.net!

Thanks.

Mark Coleman

Share on other sites
Quote:
 Original post by mrmrcoleman4 replies in about 150 seconds, that's why I love Gamedev.net!

I don't. I thought I'd get to be the first response, but in the time I typed those couple of sentences, 3 people had already posted :P

Share on other sites
There's an STL algorithm you could use, remove_if:

//Make a functor for the removal criterionstruct isTemporary{  bool operator()(ScreenEntityBase* seb)  {     return (seb->GetFlags() & SCREENENTITY_TEMPORARY) > 0;  }};...vector<ScreenEntityBase*>::iterator chopped_end;chopped_end = remove_if(ScreenEntityList.begin(), ScreenEntityList.end(), isTemporary());ScreenEntityList.erase(chopped_end, ScreenEntityList.end());

Untested, of course.

Share on other sites
Also note that it might not be wise to do this often or with large vectors; the average O(n) complexity of each removal might have rather an adverse effect on efficiency. std::list might be a better choice, if you absolutely don't require random access.

Share on other sites
Oh, in addition (and in response to Sharlin's warning about efficiency), a speed improvement you can implement when removing items from a vector is to free whatever resources you need to on the item being removed, then copy the last item in the vector into the element that you're getting to remove, and then reduce the size of the vector by one. This way, there is only a single copy involved, instead of moving every element after the erased element over by one. This should be significantly more efficient if you have a large vector and/or erase a lot of items. However, this means that the order of the elements will not remain consistent. If you need them to remain sorted or consistent, then this method won't work. This is often not the case, though, so this might be a perfectly effective optimization.
vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();while (it != ScreenEntityList.end()){	if(((*it)->GetFlags() & SCREENENTITY_TEMPORARY) > 0)	{		(*it)->Release();		*it = ScreenEntityList.back();		ScreenEntityList.pop_back();	}	else	{		++it;	}}

1. 1
Rutin
26
2. 2
3. 3
4. 4
JoeJ
18
5. 5
gaxio
11

• 14
• 22
• 11
• 11
• 9
• Forum Statistics

• Total Topics
631763
• Total Posts
3002194
×