Sign in to follow this  

The correct way to remove elements from an STL vector?

This topic is 4581 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
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
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
Quote:
Original post by Couvillion
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.



// functor as before

template <typename Container, typename Predicate>
void filter(const Container& c, const Predicate& p) {
c.erase(remove_if(c.begin(), c.end(), p), c.end());
}

filter(ScreenEntityList, isTemporary());


? :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman

// functor as before

template <typename Container, typename Predicate>
void filter(const Container& c, const Predicate& p) {
c.erase(remove_if(c.begin(), c.end(), p), c.end());
}

filter(ScreenEntityList, isTemporary());


? :)


Minor issues, you wanna remove const modifier on the Container type parameter other-wise you can only invoke constant member functions which erase isn't [grin] and for genericity of C++ callable entities you wanna remove the constant reference on the Predicate type aswell, throw in some concept checking to prevent types that are not a model of a Sequence from being used and your sorted.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"Hello, I am currently using this loop to remove elements from a vector which meet certain criteria, i.e. they are flagged as temporary."

It doesn't sound like a job for vector in my ears...

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
"Hello, I am currently using this loop to remove elements from a vector which meet certain criteria, i.e. they are flagged as temporary."

It doesn't sound like a job for vector in my ears...
just to clarify, you probably want to be storing stuff in a list.

Share this post


Link to post
Share on other sites
Quote:
Original post by mrmrcoleman
Hello, I am currently using this loop to remove elements from a vector which meet certain criteria, i.e. they are flagged as temporary.

*** Source Snippet Removed ***

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


Functor happy version...

struct releasing_temporary_entity {
bool operator()( ScreenEntityBase * entity ) const {
if ( (entity->GetFlags() & SCREENENTITY_TEMPORARY) > 0 ) {
entity->Release();
return true;
}
return false;
}
};

ScreenEntityList.erase
( std::remove_if
( ScreenEntityList.begin()
, ScreenEntityList.end()
, releasing_temporary_entity()
)
, ScreenEntityList.end()
);


Preforms at O(N) instead of O(N*N).

Yours fails because:

1) you never increment "it"
2) the iterator "it" is invalidated after erasure, along with all iterators after it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"2) the iterator "it" is invalidated after erasure, along with all iterators after it."

As far as I can see in my cpp-reference, erase() only calls delete for the object that the pointer points to and then clears the pointer.

...and there is an example where you iterate through a vector and delete every object.

Anyway, vectors should not be used for dynamic purposes in this way...

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
"2) the iterator "it" is invalidated after erasure, along with all iterators after it."

As far as I can see in my cpp-reference, erase() only calls delete for the object that the pointer points to and then clears the pointer.


Quote:
From SGI's std::vector documentation:
[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. 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.


Can't seem to find similar warning in the MSDN. Then again, they don't even have a warning about iterator invalidation on resize() in there either (where I'm looking) so I'm not suprised.

Quote:
...and there is an example where you iterate through a vector and delete every object.


It's a bad idea preformance-wise on a vector (not so on a list), but is legal C++ with a defined effect if one sets the iterator to the return of erase() (which was not done) - however, erasing an object at an iterator most definately invalidates iterators pointing to that object. Also note that undefined behavior such as this can include "running just like you'd expect/hope" - but it's still best avoided, as this can also include "launching nuclear missiles at a cow ranch in Alaska".

Quote:
Anyway, vectors should not be used for dynamic purposes in this way...


Vectors can work just fine if your requirements include checking an entire range for dying elements - a list is prefered if you're going to do random willy nilly erasures( read: erase() a single element at a time ), but that's not what's happening here. The effects of cache-consistancy may very well make the vector version outpreform the list version, especially with POD types such as pointers, in which relocation of the item is a simple O(1) time algorithm consisting of moving a measly 4 bytes. Calling this sequence of remove_if and erase on a single range is still an O(N) complexity algorithm, just the same as with a list. Doing this with individual erases will be O(N) for lists, O(N*N) for vectors, which is exactly what I'm trying to point out and provide a sound alternative against.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by Zahlman

// functor as before

template <typename Container, typename Predicate>
void filter(const Container& c, const Predicate& p) {
c.erase(remove_if(c.begin(), c.end(), p), c.end());
}

filter(ScreenEntityList, isTemporary());


? :)


Minor issues, you wanna remove const modifier on the Container type parameter other-wise you can only invoke constant member functions which erase isn't [grin] and for genericity of C++ callable entities you wanna remove the constant reference on the Predicate type aswell,


You are of course correct, I didn't think that one through at all ^^; (There are plenty of good reasons for functors to be stateful, and thus mutable as a result of being applied.)

Quote:
throw in some concept checking to prevent types that are not a model of a Sequence from being used and your sorted.


And yes, of course, but I don't know how to do this :(

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
MaulingMonkey: Yep, I assumed that reserve() was used since I always use it when I use vectors. My bad... But if reserve() is not used than it's even more clear that he should use something besides a vector since he wants a dynamic behaviour.

Share this post


Link to post
Share on other sites
Quote:
Original post by mrmrcoleman
Hello, I am currently using this loop to remove elements from a vector which meet certain criteria, i.e. they are flagged as temporary.

*** Source Snippet Removed ***

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


Seems like your problem's been answered in a couple different ways, however if I might make a suggestion to anyone who's iterating through any of the stl containers. Use the preincrement operator instead of the postincrement whenever you can.

Why? Because the postincrement actually creates a copy of your iterator and returns that. If you're not erasing that iterator from the container, it's wasted cycles to make the copy. Revising your code, I would write it thusly:


// Remove all the temporary entities
for(vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();it != ScreenEntityList.end(); /* Note: Nothing here! */)
{
if(((*it)->GetFlags() & SCREENENTITY_TEMPORARY) > 0)
{
(*it)->Release();

// this works, as the postincrement operator returns a copy
// of the iterator, and then increments the original, which
// remains valid even after the erase.
// This is probably the only time you should use this operator
ScreenEntityList.erase(it++);
}
else
++it;
}





But now you've got a for loop without anything in the expression statement of the for loop. In these cases, I find it cleaner to re-write my for loop as a while.

I would also suggest placing constants in the left hand side of a comparison expression. ("while(0==nMyVar)" instead of "while(nMyVar==0)") This prevents things like "while(nMyVar=0)" from ever happening if you accidentally forget the second "=", plunging your app into an endless loop, and causing other nasty things. Some compilers will raise a warning if they see "while(nMyVar=0)", but many will not.


vector<ScreenEntityBase*>::iterator it = ScreenEntityList.begin();

while(ScreenEntityList.end() != it)
{
if(0 < ((*it)->GetFlags() & SCREENENTITY_TEMPORARY))
{
(*it)->Release();

ScreenEntityList.erase(it++);
}
else
++it; // much faster than it++
}


Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
MaulingMonkey: Yep, I assumed that reserve() was used since I always use it when I use vectors.


You're missing the point, which has nothing to do with reserve. If the insertion or removal is not at the very end of the container, iterators are invalidated. I was merely countering this:

Quote:
Original post by Anonymous Poster
"2) the iterator "it" is invalidated after erasure, along with all iterators after it."

As far as I can see in my cpp-reference, erase() only calls delete for the object that the pointer points to and then clears the pointer.


By providing the documentation which explicitly mentions the invalidation of pointers past that being erased.

Quote:
My bad... But if reserve() is not used than it's even more clear that he should use something besides a vector since he wants a dynamic behaviour.


You've also missed my other points:

1) The memory consistancy of a vector being able to in many situations outpreform other containers (especially std::list) and thus being the appropriate container for use.

2) We're not randomly erasing from the middle of the container, which is where std::list excells, but instead erasing a whole bunch of things at one time, which std::vector can handle on similar par with std::list depending on the situation, and may be better than std::list (again, depending on the situation).

Finally, not using reserve() does not automatically mean one should be using another container, as you seem to be implying. This is because std::vector kicks std::list's ass for random access and iterating through (memory consistancy vs cache-miss every advance).


Rather than giving essentially baseless advice, since you don't know the exact usage pattern of mrmrcoleman's ScreenEntityList, if you must advise on this, your comment should look something like so:

std::vector may be innapropriate here, as it can be faster to erase elements from a std::list, since erasing elements will not necessitate the relocation of following elements.

If, after profiling, this area of your code seems to be slow, you might try switching to a std::list or std::set or other container that has O(1) preformance for the erasure of single elements (which implies that the erasure of X elements in a container will of size N will probably be O(X) rather than O(N) in preformance).


My personal opinion is that, as long as you don't have that horrible O(N*N) algorithm as originally outlined, that std::vector is probably fine in this situation and will not be a preformance bottleneck. Suggesting std::list without suggesting profiling it against std::vector (and maybe other containers) in his situation, is really downright stupid very bad advice, at the very best.

Share this post


Link to post
Share on other sites

This topic is 4581 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.

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