deleting entries in a list

[Christoff Pale]

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

 

[Alf P. Steinbach]

* 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:stream_iterator<std::string>( std::cout, "\n" )
);
}

 

[Mike Wahler]

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

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]

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

 

[David Hilsee]

* Christoff Pale:


#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:stream_iterator<std::string>( std::cout, "\n" )
);
}

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

 

[Alf P. Steinbach]

* 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?

 

[Alf P. Steinbach]

* Mike Wahler:

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?

 

[Mike Wahler]

* Mike Wahler:

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

 

[Heinz Ozwirk]

"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

 

[Alf P. Steinbach]

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

 

[Christoff Pale]

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


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


#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

 

[Mike Wahler]

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

 

[Rich Grise]

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