Jump to content
  • Advertisement
Sign in to follow this  
mrmrcoleman

The correct way to remove elements from an STL vector?

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

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 this post


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

walker should be it, I guess...

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by mrmrcoleman
4 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 this post


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


//Make a functor for the removal criterion

struct 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 this post


Link to post
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 this post


Link to post
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;
}
}



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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!