Deleting STL list entry - are all iterators invalidated?

Discussion in 'C++' started by Boltar, Jan 22, 2007.

  1. Boltar

    Boltar Guest

    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, Jan 22, 2007
    #1
    1. Advertising

  2. Boltar

    Boltar Guest

    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, Jan 22, 2007
    #2
    1. Advertising

  3. Boltar

    Greg Guest

    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
    Greg, Jan 22, 2007
    #3
  4. Boltar

    Rolf Magnus Guest

    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().
    Rolf Magnus, Jan 22, 2007
    #4
  5. Boltar

    Greg Guest

    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
    Greg, Jan 22, 2007
    #5
  6. Boltar

    Greg Guest

    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, Jan 22, 2007
    #6
  7. Boltar

    Rolf Magnus Guest

    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);
    Rolf Magnus, Jan 22, 2007
    #7
  8. Boltar

    Jim Langston Guest

    "Boltar" <> wrote in message
    news:...
    >
    > 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.
    }
    Jim Langston, Jan 22, 2007
    #8
  9. Boltar

    Daniel T. Guest

    "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., Jan 22, 2007
    #9
  10. Boltar

    Greg Guest

    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
    Greg, Jan 22, 2007
    #10
  11. Boltar

    Daniel T. Guest

    In article <>,
    "Greg" <> wrote:

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


    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 );
    Daniel T., Jan 22, 2007
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    9
    Views:
    11,114
    Silvio Bierman
    Dec 6, 2004
  2. Replies:
    1
    Views:
    1,140
    William Brogden
    Dec 6, 2004
  3. Replies:
    5
    Views:
    2,952
    Earl Purple
    Dec 18, 2005
  4. Replies:
    1
    Views:
    478
  5. Andy B.
    Replies:
    0
    Views:
    317
    Andy B.
    Jun 12, 2009
Loading...

Share This Page