Deleting STL list entry - are all iterators invalidated?

[Boltar]

Hello

I need to iterate through an STL list container and delete certain
entries in it. I realise if use erase() with the iterator it will
invalidate it but what if I store it beforehand? Ie: is the code below
using a 2nd iterator variable always guaranteed to work or could there
be come internal implementation magic going on inside the list that
could prevent it?

for(iter=objlist.begin();iter != objlist.end();++iter)
{
iter2 = iter;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
}

Thanks for any help.

B2003

 

[Boltar]

for(iter=objlist.begin();iter != objlist.end();++iter)
{
iter2 = iter;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
}

Sorry , that was some old code I cut and pasted , it should have read:

for(iter=objlist.begin();iter != objlist.end()
{
iter2 = iter
iter2++;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
else iter++;
}

B2003

 

[Greg]

Hello

I need to iterate through an STL list container and delete certain
entries in it. I realise if use erase() with the iterator it will
invalidate it but what if I store it beforehand? Ie: is the code below
using a 2nd iterator variable always guaranteed to work or could there
be come internal implementation magic going on inside the list that
could prevent it?

for(iter=objlist.begin();iter != objlist.end();++iter)
{
iter2 = iter;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
}

As long as the program calls std::list's own erase() routine (as the
sample code above does) to remove the element from the list, then only
the iterator that was passed to erase() will be invalidated. In
particular, all other iterators in that same list container remain
valid and will still reference the same list element as before.

Greg

 

[Rolf Magnus]

Sorry , that was some old code I cut and pasted , it should have read:

for(iter=objlist.begin();iter != objlist.end()
{
iter2 = iter
iter2++;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
else iter++;
}

It's not just the iterator that you used with erase() that's invalidated,
but rather all iterators to the erased element. Think about it: iter2
refers to an element that doesn't exist anymore. How could it be valid?
Hint: Have a look at the return value of erase().

 

[Greg]

Sorry , that was some old code I cut and pasted , it should have read:

for(iter=objlist.begin();iter != objlist.end()
{
iter2 = iter
iter2++;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
else iter++;
}

The second iterator is not necessary. Moreover, the loop could be
streamlined a bit:

iter = objlist.begin();

while ( iter != objlist.end())
{
(*iter)->run();

if ((*iter)->destroy_me)
{
objlist.erase( iter++ );
continue;
}
iter++;
}

Greg

 

[Greg]

It's not just the iterator that you used with erase() that's invalidated,
but rather all iterators to the erased element. Think about it: iter2
refers to an element that doesn't exist anymore. How could it be valid?

No, iter2 refers to the element after the one that is erased.

Hint: Have a look at the return value of erase().

Since a std::list's iterators are stable, the iterator that
std::list::erase() will return is known before erase() is ever called.
Therefore a program can just as easily erase the element at the
iterator's current postion and advance the iterator to the next element
like so:

objlist.erase( iter++ );

Greg

 

[Rolf Magnus]

No, iter2 refers to the element after the one that is erased.

Ah right. I've seen that the OP corrected his code, but I was still looking
at the first version that didn't have the increment.

Since a std::list's iterators are stable, the iterator that
std::list::erase() will return is known before erase() is ever called.
Therefore a program can just as easily erase the element at the
iterator's current postion and advance the iterator to the next element
like so:

objlist.erase( iter++ );

Yes. However, I'd still use the return value, like:

iter = objlist.erase(iter);

 

[Jim Langston]

Sorry , that was some old code I cut and pasted , it should have read:

for(iter=objlist.begin();iter != objlist.end()
{
iter2 = iter
iter2++;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
else iter++;
}

B2003

The "normal" way to handle this is like this:

for ( iter=objlist.begin(); iter != objlist.end(); )
{
obj->run();
if ( obj->destory_me )
iter = objlist.erase( iter );
else
++iter;
}

..erase() returns an iterator just past the one erased.
}

 

[Daniel T.]

for(iter=objlist.begin();iter != objlist.end()
{
iter2 = iter
iter2++;
obj = *iter;
obj->run();
if (obj->destroy_me)
{
objlist.erase(iter);
delete obj;
iter = iter2;
}
else iter++;
}

Something that should have been a member function of std::list:

template < typeanme T >
void remove_if( std::list<T>& li, Fn fn )
{
typename std::list<T>::iterator it = li.begin();
while ( it != li.end() )
if ( fn( *it ) )
li.erase( it++ );
}

Then you can:

bool should_destroy( MyClass* obj ) {
if ( obj->destroy_me ) {
delete obj;
return true;
}
return false;
}

for_each( objlist.begin(), objlist.end(), mem_fun( &MyClass::run ) );
remove_if( objlist, &should_destroy );

Or you can:

bool run_and_check_destroy( MyClass* obj ) {
obj->run();
if ( obj->destroy_me ) {
delete obj;
return true;
}
return false;
}

remove_if( objlist, &run_and_check_destroy );

 

[Greg]

Something that should have been a member function of std::list:

template < typeanme T >
void remove_if( std::list<T>& li, Fn fn )
{
typename std::list<T>::iterator it = li.begin();
while ( it != li.end() )
if ( fn( *it ) )
li.erase( it++ );
}

Actually, std::list does have a remove_if() member function.

Greg

 

[Daniel T.]

Actually, std::list does have a remove_if() member function.

Well, there you go:

bool should_destroy( MyClass* obj ) {
if ( obj->destroy_me ) {
delete obj;
return true;
}
return false;
}

for_each( objlist.begin(), objlist.end(), mem_fun( &MyClass::run ) );
objlist.remove_if( &should_destroy );