deleting entries in a list

Discussion in 'C++' started by Christoff Pale, Sep 2, 2004.

  1. Hi,
    suppose I have a list of strings;
    I have to iterate of the strings and delete certain entries.
    I and not sure how to do this?

    for example:
    #include<list>
    #include<string>
    #include<iostream>
    int main(){
    list<string> l;
    l.push_back("first");
    l.push_back("second");
    l.push_back("deleteme");
    l.push_back("fourth");
    l.push_back("deleteme");
    l.push_back("sixth");
    // I want to erase entries that say "deleteme"

    I can get and iterator, but that screws up things
    list<string>::iterator it=l.begin();
    for( ; it!=l.end(); it++){
    if( (*it).compare("deleteme")==0){
    l.erase(it);
    }
    }
    }

    This gives me segmentation fault

    I think that when I delete the first "deleteme" the
    it now points to "fourth";

    Basically, this is what I want.
    I will have a huge list of some object.
    I want to traverse it all the way and delete
    objects that meet a certain criteria.
    any help will be much appreciated.
    thanks
     
    Christoff Pale, Sep 2, 2004
    #1
    1. Advertising

  2. * Christoff Pale:
    >
    > suppose I have a list of strings;
    > I have to iterate of the strings and delete certain entries.
    > I and not sure how to do this?
    >
    > for example:
    > #include<list>
    > #include<string>
    > #include<iostream>
    > int main(){
    > list<string> l;
    > l.push_back("first");
    > l.push_back("second");
    > l.push_back("deleteme");
    > l.push_back("fourth");
    > l.push_back("deleteme");
    > l.push_back("sixth");
    > // I want to erase entries that say "deleteme"
    >
    > I can get and iterator, but that screws up things
    > list<string>::iterator it=l.begin();
    > for( ; it!=l.end(); it++){
    > if( (*it).compare("deleteme")==0){
    > l.erase(it);
    > }
    > }
    > }
    >
    > This gives me segmentation fault
    >



    #include <algorithm>
    #include <iostream>
    #include <list>
    #include <string>

    int main()
    {
    typedef std::list<std::string> StringList;
    typedef StringList::iterator Iterator;

    StringList l;
    l.push_back( "first" );
    l.push_back( "second" );
    l.push_back( "deleteme" );
    l.push_back( "fourth" );
    l.push_back( "deleteme" );
    l.push_back( "sixth" );

    for( Iterator it = l.begin(); it != l.end(); )
    {
    it->compare( "deleteme" ) == 0? it = l.erase( it ) : ++it;
    }

    std::copy(
    l.begin(), l.end(),
    std::eek:stream_iterator<std::string>( std::cout, "\n" )
    );
    }

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 2, 2004
    #2
    1. Advertising

  3. Christoff Pale

    Mike Wahler Guest

    "Christoff Pale" <> wrote in message
    news:...
    > Hi,
    > suppose I have a list of strings;
    > I have to iterate of the strings and delete certain entries.
    > I and not sure how to do this?
    >
    > for example:
    > #include<list>
    > #include<string>
    > #include<iostream>
    > int main(){
    > list<string> l;


    std::list<std::string> l; /* I *hate* that identifier! :) */

    > l.push_back("first");
    > l.push_back("second");
    > l.push_back("deleteme");
    > l.push_back("fourth");
    > l.push_back("deleteme");
    > l.push_back("sixth");
    > // I want to erase entries that say "deleteme"
    >
    > I can get and iterator, but that screws up things
    > list<string>::iterator it=l.begin();


    std::list<std::string>::iterator it = l.begin();

    > for( ; it!=l.end(); it++){
    > if( (*it).compare("deleteme")==0){
    > l.erase(it);
    > }
    > }
    > }
    >
    > This gives me segmentation fault


    When you delete an element to which the iterator points,
    that iterator becomes invalidated. Then you try to increment
    that invalid iterator. Undefined behavior.

    >
    > I think that when I delete the first "deleteme" the
    > it now points to "fourth";


    No it points to the outer moon of sixth planet circling
    Alpha Seti. But that's just today. Tomorrow it would
    point somewhere else.

    std::list::erase() returns an iterator that designates
    the first element remaining beyond any elements removed,
    or end() if no such element exists. So when you erase,
    don't increment 'it', assign it the return value from
    'erase()'.

    >
    > Basically, this is what I want.
    > I will have a huge list of some object.
    > I want to traverse it all the way and delete
    > objects that meet a certain criteria.
    > any help will be much appreciated.


    #include<iostream>
    #include<list>
    #include<string>

    int main()
    {
    std::list<std::string> l;
    l.push_back("first");
    l.push_back("second");
    l.push_back("deleteme");
    l.push_back("fourth");
    l.push_back("deleteme");
    l.push_back("sixth");

    std::cout << l.size() << '\n'; // prints 6

    for(std::list<std::string>::iterator it = l.begin(); it!=l.end(); it++)
    if((*it).compare("deleteme") == 0)
    it = l.erase(it);

    std::cout << l.size() << '\n'; // prints 4
    return 0;
    }

    Also look up 'std::list::remove_if()'

    -Mike
     
    Mike Wahler, Sep 2, 2004
    #3
  4. Christoff Pale

    Mike Wahler Guest

    Re: [corr] deleting entries in a list

    "Mike Wahler" <> wrote in message
    news:TRvZc.5045$w%...
    >
    > for(std::list<std::string>::iterator it = l.begin(); it!=l.end();

    it++)
    > if((*it).compare("deleteme") == 0)
    > it = l.erase(it);


    This isn't quite right. It produces a valid iterator,
    but the 'for' loop increments it, which will skip
    over the item after the erased one. See Alf's post
    for a proper way to do this.

    Sorry for the mistake.

    -Mike
     
    Mike Wahler, Sep 2, 2004
    #4
  5. Christoff Pale

    David Hilsee Guest

    "Alf P. Steinbach" <> wrote in message
    news:...
    > * Christoff Pale:
    > >
    > > suppose I have a list of strings;
    > > I have to iterate of the strings and delete certain entries.
    > > I and not sure how to do this?
    > >
    > > for example:
    > > #include<list>
    > > #include<string>
    > > #include<iostream>
    > > int main(){
    > > list<string> l;
    > > l.push_back("first");
    > > l.push_back("second");
    > > l.push_back("deleteme");
    > > l.push_back("fourth");
    > > l.push_back("deleteme");
    > > l.push_back("sixth");
    > > // I want to erase entries that say "deleteme"
    > >
    > > I can get and iterator, but that screws up things
    > > list<string>::iterator it=l.begin();
    > > for( ; it!=l.end(); it++){
    > > if( (*it).compare("deleteme")==0){
    > > l.erase(it);
    > > }
    > > }
    > > }
    > >
    > > This gives me segmentation fault
    > >

    >
    >
    > #include <algorithm>
    > #include <iostream>
    > #include <list>
    > #include <string>
    >
    > int main()
    > {
    > typedef std::list<std::string> StringList;
    > typedef StringList::iterator Iterator;
    >
    > StringList l;
    > l.push_back( "first" );
    > l.push_back( "second" );
    > l.push_back( "deleteme" );
    > l.push_back( "fourth" );
    > l.push_back( "deleteme" );
    > l.push_back( "sixth" );
    >
    > for( Iterator it = l.begin(); it != l.end(); )
    > {
    > it->compare( "deleteme" ) == 0? it = l.erase( it ) : ++it;
    > }
    >
    > std::copy(
    > l.begin(), l.end(),
    > std::eek:stream_iterator<std::string>( std::cout, "\n" )
    > );
    > }


    Whoah, that's giving me Perl flashbacks! Is there something wrong with
    if/else? ;-)

    --
    David Hilsee
     
    David Hilsee, Sep 2, 2004
    #5
  6. * Mike Wahler:
    >
    > for(std::list<std::string>::iterator it = l.begin(); it!=l.end(); it++)
    > if((*it).compare("deleteme") == 0)
    > it = l.erase(it);


    What happens here if there are two "deleteme" items in sequence, or
    if there is a "deleteme" item at the end of the list?

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 2, 2004
    #6
  7. Re: [corr] deleting entries in a list

    * Mike Wahler:
    > "Mike Wahler" <> wrote in message
    > news:TRvZc.5045$w%...
    > >
    > > for(std::list<std::string>::iterator it = l.begin(); it!=l.end();

    > it++)
    > > if((*it).compare("deleteme") == 0)
    > > it = l.erase(it);

    >
    > This isn't quite right. It produces a valid iterator,
    > but the 'for' loop increments it, which will skip
    > over the item after the erased one. See Alf's post
    > for a proper way to do this.


    I'm sorry for already responding to your previous posting before
    reading this. Grr. When shall I learn to read _everything_ first?

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 2, 2004
    #7
  8. Christoff Pale

    Mike Wahler Guest

    Re: [corr] deleting entries in a list

    "Alf P. Steinbach" <> wrote in message
    news:...
    > * Mike Wahler:
    > > "Mike Wahler" <> wrote in message
    > > news:TRvZc.5045$w%...
    > > >
    > > > for(std::list<std::string>::iterator it = l.begin(); it!=l.end();

    > > it++)
    > > > if((*it).compare("deleteme") == 0)
    > > > it = l.erase(it);

    > >
    > > This isn't quite right. It produces a valid iterator,
    > > but the 'for' loop increments it, which will skip
    > > over the item after the erased one. See Alf's post
    > > for a proper way to do this.

    >
    > I'm sorry for already responding to your previous posting before
    > reading this. Grr. When shall I learn to read _everything_ first?


    No problem. I sometimes do the same thing myself.

    -Mike
     
    Mike Wahler, Sep 2, 2004
    #8
  9. Christoff Pale

    Heinz Ozwirk Guest

    "Alf P. Steinbach"
    > * Christoff Pale:

    [...]
    > for( Iterator it = l.begin(); it != l.end(); )
    > {
    > it->compare( "deleteme" ) == 0? it = l.erase( it ) : ++it;


    it->compare( "deleteme" ) == 0? it = l.erase( it/*!*/++/*!*/ ) : ++it;

    > }


    Heinz
     
    Heinz Ozwirk, Sep 2, 2004
    #9
  10. * Heinz Ozwirk:
    >
    > "Alf P. Steinbach"
    > > * Christoff Pale:

    > [...]
    > > for( Iterator it =3D l.begin(); it !=3D l.end(); )
    > > {
    > > it->compare( "deleteme" ) =3D=3D 0? it =3D l.erase( it ) : =

    > ++it;
    > =20
    > it->compare( "deleteme" ) =3D=3D 0? it =3D l.erase( it/*!*/++/*!*/ ) =
    > : ++it;
    >
    > > }


    If (and here I'm guessing) that is supposed to mean


    it = l.erase( it++ )


    then that's wrong.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Sep 2, 2004
    #10
  11. "Mike Wahler" <> wrote in message
    >
    > When you delete an element to which the iterator points,
    > that iterator becomes invalidated. Then you try to increment
    > that invalid iterator. Undefined behavior.
    >
    > >
    > > I think that when I delete the first "deleteme" the
    > > it now points to "fourth";

    >
    > No it points to the outer moon of sixth planet circling
    > Alpha Seti. But that's just today. Tomorrow it would
    > point somewhere else.
    >
    > std::list::erase() returns an iterator that designates
    > the first element remaining beyond any elements removed,
    > or end() if no such element exists. So when you erase,
    > don't increment 'it', assign it the return value from
    > 'erase()'.
    >
    > >
    > > Basically, this is what I want.
    > > I will have a huge list of some object.
    > > I want to traverse it all the way and delete
    > > objects that meet a certain criteria.
    > > any help will be much appreciated.

    >
    > #include<iostream>
    > #include<list>
    > #include<string>
    >
    > int main()
    > {
    > std::list<std::string> l;
    > l.push_back("first");
    > l.push_back("second");
    > l.push_back("deleteme");
    > l.push_back("fourth");
    > l.push_back("deleteme");
    > l.push_back("sixth");
    >
    > std::cout << l.size() << '\n'; // prints 6
    >
    > for(std::list<std::string>::iterator it = l.begin(); it!=l.end(); it++)
    > if((*it).compare("deleteme") == 0)
    > it = l.erase(it);
    >
    > std::cout << l.size() << '\n'; // prints 4
    > return 0;
    > }
    >
    > Also look up 'std::list::remove_if()'
    >
    > -Mike


    There is something strange about this which I don't understand:
    Consider the output of the following program:
    #include<string>
    #include<iostream>
    using namespace std;

    int main(){
    list<string> l;
    l.push_back("first");
    l.push_back("second");
    l.push_back("deleteme");
    l.push_back("deleteme");
    l.push_back("deleteme");
    l.push_back("third");
    l.push_back("fourth");

    l.push_back("fifth");
    l.push_back("deleteme");
    list<string>::iterator it;
    for(it=l.begin(); it!=l.end(); it++)
    cout << (*it) << endl;
    cout << "=================\n";
    for( it=l.begin(); it != l.end(); it++){
    cout << "It points to:" << *it <<endl;
    if ((*it).compare("deleteme")==0)
    it=l.erase(it);

    }
    cout << "++++++++++++++++\n";
    for(it=l.begin(); it!=l.end(); it++)
    cout << (*it) << endl;

    }
    ===================== OUTPUT
    $ ./test_iterators.cc.exe
    first
    second
    deleteme
    deleteme
    deleteme
    third
    fourth
    fifth
    deleteme
    =================
    It points to:first
    It points to:second
    It points to:deleteme
    It points to:deleteme
    It points to:fourth
    It points to:fifth
    It points to:deleteme
    It points to:first
    It points to:second
    It points to:deleteme
    It points to:fourth
    It points to:fifth
    ++++++++++++++++
    first
    second
    third
    fourth
    fifth
    $
    ==============================
    I have 2 questions:
    1) why does iterator never pointed to the element "third"?
    2) why is the list traversed twice? (and the element "third" is missed both times)
    thanks
     
    Christoff Pale, Sep 2, 2004
    #11
  12. Christoff Pale

    Mike Wahler Guest

    "Christoff Pale" <> wrote in message
    news:...
    >
    > There is something strange about this which I don't understand:
    > for( it=l.begin(); it != l.end(); it++){
    > cout << "It points to:" << *it <<endl;
    > if ((*it).compare("deleteme")==0)
    > it=l.erase(it);
    >
    > }


    See my followup post where I point out the error I made
    in my example, and see Alf's post for something that actually
    works correctly.


    -Mike
     
    Mike Wahler, Sep 2, 2004
    #12
  13. Christoff Pale

    Rich Grise Guest

    On Thursday 02 September 2004 09:35 am, Christoff Pale did deign to grace us
    with the following:

    > "Mike Wahler" <> wrote in message
    >>
    >> When you delete an element to which the iterator points,
    >> that iterator becomes invalidated. Then you try to increment
    >> that invalid iterator. Undefined behavior.

    >
    > There is something strange about this which I don't understand:
    > Consider the output of the following program:

    ....
    > $
    > ==============================
    > I have 2 questions:
    > 1) why does iterator never pointed to the element "third"?


    You're doing the cout before the delete. At that time, 'it' points
    at the first "deleteme." 'it' gets assigned the next value, which in
    this case happens to be the second "deleteme", which it dutifully
    shows you next pass. It's still there because the iterator has
    already been assigned to the following one and incremented.

    > 2) why is the list traversed twice? (and the element "third" is missed
    > both times) thanks


    Presumably, the computer remembers that when it went through the
    first time, it left a "deleteme" behind. In this pass, you see
    "deleteme" again, but when this one is deleted _and 'it' assigned
    to point to "third"_, you don't see "third", because 'it' gets incremented
    at the top of the loop.

    Try it with a cout on either side of the delete, and see what happens. :)

    Cheers!
    Rich
     
    Rich Grise, Sep 9, 2004
    #13
    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. Rhino

    Adding/deleting Jar entries?

    Rhino, Feb 4, 2005, in forum: Java
    Replies:
    4
    Views:
    16,605
    Rhino
    Feb 4, 2005
  2. Patrick von Harsdorf

    iterating over collection, deleting entries

    Patrick von Harsdorf, Apr 25, 2004, in forum: Python
    Replies:
    3
    Views:
    292
    Larry Bates
    Apr 26, 2004
  3. Prafulla T
    Replies:
    8
    Views:
    691
    Joe Greer
    Mar 7, 2009
  4. Robert Kern
    Replies:
    1
    Views:
    1,539
    Robert Kern
    Jul 2, 2009
  5. Don Bruder
    Replies:
    3
    Views:
    1,020
    spikeysnack
    Aug 3, 2010
Loading...

Share This Page