Conditional erasing elements from list - in a loop

Discussion in 'C++' started by Tescobar, Jul 21, 2005.

  1. Tescobar

    Tescobar Guest

    Over one year ago somebody asked here: how to
    remove selected elements from list
    in a loop?. The answer was as follows:


    for( it = l.begin(); it != l.end; ) {
    if(...)
    it = l.erase(it);
    else
    ++it;
    }


    I use STL list, and I do the same like this:


    for( it = l.begin(); it != l.end; ++it ) {
    if(...) l.erase(it--);
    }


    Is that OK? Or does it depend on details
    of the list implementation ??
    Has it to be guaranteed that the operator --
    is called before invalidation of the itarator?

    regards -
    O.C.
     
    Tescobar, Jul 21, 2005
    #1
    1. Advertisements


  2. 'operator --' must be called before 'erase' is called, because the
    result of 'operator --' is passed to 'erase'. So I do not see why this
    would not be ok. Though the first version is clearer and at least as
    fast as the second version.

    regards
     
    Jakob Bieling, Jul 21, 2005
    #2
    1. Advertisements

  3. I hope you meant

    for( it = l.begin(); it != l.end(); ++it ) {
    No. If the first element is to be erased, you will make 'it' invalid
    by decrementing it past the 'l.begin()'. Incrementing it again does
    not necessarily bring it back to be valid -- undefined behaviour.

    V
     
    Victor Bazarov, Jul 21, 2005
    #3
  4. Think about what happens when the very first item in the list is being
    erased (you'll run off the beginning of the list). Additionally, if you
    can make the condition of your if() into a predicate, then you could
    reduce the whole thing down to:

    l.remove_if(predicate);
     
    Clark S. Cox III, Jul 21, 2005
    #4
  5. Don't you mean

    l.erase(l.remove_if(predicate));

    ??

    V
     
    Victor Bazarov, Jul 21, 2005
    #5
  6. remove_if returns void and already takes care of erasing.

    regards
     
    Jakob Bieling, Jul 21, 2005
    #6
  7. I must confuse it with std::remove_if ...

    V
     
    Victor Bazarov, Jul 21, 2005
    #7
  8. Nope, I mean just what I said.
     
    Clark S. Cox III, Jul 21, 2005
    #8
  9. It is not OK, because if it == l.begin(), then it-- causes undefined
    behavior.
     
    Andrew Koenig, Jul 22, 2005
    #9
  10. Tescobar

    Greg Guest

    The post decrement operator will be applied before the call to erase,
    but as others have pointed out there is an out-of-range problem with
    the iterator. A slight change does correct this problem


    for( it = l.begin(); it != l.end(); ++it ) {
    if(...) it = l.erase(it);
    }


    But the code is still messier than it need be. Abstracting the loop
    operation and hiding the specifics of its implementation, leads to more
    compact and more likely correct code in many cases.

    Assuming that a predicate (or a value) can serve as the test for
    deletion, I would recommend this idiom for iterating and deleting items
    from a container:


    it.erase( std::remove_if( it.begin(), it.end(), ...), it.end());


    Just insert the predicate or the value to be deleted in place of the
    ellipsis.

    Greg
     
    Greg, Jul 22, 2005
    #10
  11. No it doesn't. Well, it does, but it introduces another problem, which
    amounts to the same thing.

    In this version, after you execute

    it = l.erase(it);

    you still increment "it". The result is that the code will skip the element
    after each one erased.
     
    Andrew Koenig, Jul 22, 2005
    #11
  12. Tescobar

    Tescobar Guest

    my question was:
    Are you sure, that this behaviour is undefined
    by ANSI c++ ?
    I use GNU compilers, where STL is implemented
    by SGI. Here, as a matter of fact, list is
    implemented as the circular structure, i.e.:

    list<T> mylist;
    list<T>::iterator p=mylist.end();
    p++; assert(p==mylist.end());
    p--; assert(p==mylist.end());
    //now insert exactly one element:
    mylist.push_front(something_of_type_T);
    p=mylist.begin();
    p--; assert(p==mylist.end());
    p++; assert(p==mylist.begin());

    is a valid code - none of the asserts fail.
    In another words, one can traverse the same
    list infinitely many times by repetitive
    ++ only (or -- only). During this, the
    interator will be invalid only one time
    each cycle - when passing its end() value.
    I always thought, that such a behaviour
    of list::iterator is implementation-independend.
    Has anybody seen a counterexample, i.e. an
    implementation which is still ANSI c++ compliant,
    by does not obey "circularity" ?

    Best regards from Poland :)
    O.C.
     
    Tescobar, Jul 24, 2005
    #12
  13. I think more universal would be:
    for( it = l.begin(); it != l.end; ) {
    if(...)
    l.erase(it++);
    else
    ++it;
    }

    This should work with any STL container. Original would not work for
    map and set for example.

    Regards,
    Vyacheslav
     
    Vyacheslav Kononenko, Jul 25, 2005
    #13
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.