Conditional erasing elements from list - in a loop

[Tescobar]

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.

 

[Jakob Bieling]

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?

'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

 

[Victor Bazarov]

[..]
for( it = l.begin(); it != l.end; ++it ) {

I hope you meant

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

if(...) l.erase(it--);
}


Is that OK? [...]

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

 

[Clark S. Cox III]

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?

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

 

[Victor Bazarov]

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

Don't you mean

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

??

V

 

[Jakob Bieling]

Clark S. Cox III wrote:

Don't you mean

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

??

remove_if returns void and already takes care of erasing.

regards

 

[Victor Bazarov]

remove_if returns void and already takes care of erasing.

I must confuse it with std::remove_if ...

V

 

[Clark S. Cox III]

Don't you mean

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

Nope, I mean just what I said.

 

[Andrew Koenig]

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

It is not OK, because if it == l.begin(), then it-- causes undefined
behavior.

 

[Greg]

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?

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

 

[Andrew Koenig]

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

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.

 

[Tescobar]

my question was:

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


Is that OK? [...]

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.

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.

 

[Vyacheslav Kononenko]

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