«

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 wrote:

> 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

Boltar wrote:
> 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

Boltar wrote:

>
> Boltar wrote:
>
>> 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++;
> }

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().

Boltar wrote:
> Boltar wrote:
>
> > 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++;
> }

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

Rolf Magnus wrote:
> Boltar wrote:
> > 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?

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

Greg wrote:

>
> Rolf Magnus wrote:
>> Boltar wrote:
>> > 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?
>
> 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.

>> 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++ );

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

iter = objlist.erase(iter);

"Boltar" <> wrote in message
news: ups.com...
>
> Boltar wrote:
>
>> 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

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.
}

"Boltar" <> wrote:
>
> 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 );

Daniel T. wrote:
> "Boltar" <> wrote:
> >
> > 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++ );
> }

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

Greg