remove an item in a STL list

[Gunnar G]

Hello, I just want to make sure I got it right.

I have this code

list<int> L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
list<int>::iterator iter=L.begin()+1;

L.erase(iter);
L.erase(iter);

This is a problem since I can't be sure what iter is pointing to after the
first erase, right?

So I should instead do:
iter=L.erase(iter);
iter=L.erase(iter);

With a vector (V), I could get away with
V.erase(iter);
V.erase(iter);

since most likely the vector will not move around in the memory and the
deleted element will be replaced with the next one, so that iter will again
point to a valid element in the vector?

But I should use
iter=V.erase(iter);
iter=V.erase(iter);

here to, right?

Learning is fun.

 

[Victor Bazarov]

Hello, I just want to make sure I got it right.

I have this code

list<int> L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
list<int>::iterator iter=L.begin()+1;

I am not sure +1 works... Recommend doing ++iter as a precaution.

L.erase(iter);
L.erase(iter);

This is a problem since I can't be sure what iter is pointing to after the
first erase, right?
Right.


So I should instead do:
iter=L.erase(iter);
iter=L.erase(iter);

I'd do

list<int>::iterator iter = L.begin();
iter = L.erase(++iter);
iter = L.erase(iter);

With a vector (V), I could get away with
V.erase(iter);
V.erase(iter);

since most likely the vector will not move around in the memory and the
deleted element will be replaced with the next one, so that iter will again
point to a valid element in the vector?

No. With a vector you should have even less confidence about iterators.
Vectors tend to reallocate at will, so you should obtain iterators after
every deletion.

But I should use
iter=V.erase(iter);
iter=V.erase(iter);

here to, right?

Right.

V

 

[Karsten Baumgarten]

Hello, I just want to make sure I got it right.

I have this code

list<int> L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
list<int>::iterator iter=L.begin()+1;

L.erase(iter);
L.erase(iter);

This is a problem since I can't be sure what iter is pointing to after the
first erase, right?

So I should instead do:
iter=L.erase(iter);
iter=L.erase(iter);

With a vector (V), I could get away with
V.erase(iter);
V.erase(iter);

since most likely the vector will not move around in the memory and the
deleted element will be replaced with the next one, so that iter will again
point to a valid element in the vector?

But I should use
iter=V.erase(iter);
iter=V.erase(iter);

here to, right?

Any iterator pointing to an element between the erased and the end of
the sequence becomes invalid. The iterator returned by erase() points to
the element immediately following the erased element. If there is no
such element, the returned iterator is invalid. Note that erase() never
triggers reallocation, thus every iterator before the removed element
will remain valid. Generally it is better not to rely on these rules and
to create new iterators after any operation that changes the sequence in
any way.

 

[Andrew Koenig]

list<int> L;
L.push_back(1);
L.push_back(2);
L.push_back(3);
L.push_back(4);
list<int>::iterator iter=L.begin()+1;

This should not work, as list iterators are not random access iterators and
so do not support +.

L.erase(iter);
L.erase(iter);

This is a problem since I can't be sure what iter is pointing to after the
first erase, right?
Right.

So I should instead do:
iter=L.erase(iter);
iter=L.erase(iter);
Right.

With a vector (V), I could get away with
V.erase(iter);
V.erase(iter);

No you can't. Erasing an element from a vector is permitted to invalidate
all iterators referring to elements of the vector.

But I should use
iter=V.erase(iter);
iter=V.erase(iter);

here to, right?

Right.

 

[David Harmon]

On Tue, 08 Feb 2005 22:41:29 GMT in comp.lang.c++, "Andrew Koenig"

No you can't. Erasing an element from a vector is permitted to invalidate
all iterators referring to elements of the vector.

Is that a change? Last I looked it was only invalidates iterators
pointing to or after the point of the erase.

 

[Karsten Baumgarten]

On Tue, 08 Feb 2005 22:41:29 GMT in comp.lang.c++, "Andrew Koenig"



Is that a change? Last I looked it was only invalidates iterators
pointing to or after the point of the erase.

Andrew's answer is not correct. It would be, if erase() would trigger a
reallocation, but STL reference clearly says it does not. Thus only
iterators pointing to or after the erased element become invalid.

 

[msalters]

....
Erasing an element from a vector is permitted to invalidate

Andrew's answer is not correct. It would be, if erase() would trigger a
reallocation, but STL reference clearly says it does not. Thus only
iterators pointing to or after the erased element become invalid.

In fact, because we nowadays require vector to be contiguous, 23.2.4.3
is incorrect, even in the latest draft. References must remain valid
but will point to new values, if the shrunken vector still contains
sufficient elements. E.g. erasing the second element of a 100-element
container will not invalidate a reference to the third element, simply
because the reference to the first element must remain valid.
{ &v[2]==(&v[0])+2 }

Regards,
Michiel Salters

 

[Karsten Baumgarten]

In fact, because we nowadays require vector to be contiguous, 23.2.4.3
is incorrect, even in the latest draft. References must remain valid
but will point to new values, if the shrunken vector still contains
sufficient elements. E.g. erasing the second element of a 100-element
container will not invalidate a reference to the third element, simply
because the reference to the first element must remain valid.
{ &v[2]==(&v[0])+2 }

I just wrote some sample code and agree. But this leads to strange
results: If one erases the last element of the vector using a valid
iterator, it remains valid even though it now references an element
"outside" of the sequence. That is, it still references the - now erased
- element and happily returns it if you ask. I'd rather have my app
segfaulting instead of iterators returning "ghost elements"...

 

[Victor Bazarov]

[...]
I just wrote some sample code and agree. But this leads to strange
results: If one erases the last element of the vector using a valid
iterator, it remains valid even though it now references an element
"outside" of the sequence. That is, it still references the - now erased
- element and happily returns it if you ask. I'd rather have my app
segfaulting instead of iterators returning "ghost elements"...

You're jumping to wrong conclusions. Using an iterator that has become
invalid due to any operation that is said to invalidate it, produces
_undefined_behaviour_. Whatever it does is fine and you cannot expect
it to "segfault" instead of "happily returning" anything. Yes, we all
would rather prefer that our programs wrote themselves, don't we? There
are systems for which "segfaulting" is impossible. What should they do?
There is no way in C++ to require "segfaulting" because of those.

Imagine that your leg is broken and by standing on it in a certain way
you don't feel any pain. It doesn't mean it's OK to stand on it, or that
if you try standing on it again tomorrow, or somebody else tries to stand
on their broken leg, it will be exactly the same painless experience. So,
as the saying goes, DON'T DO IT(tm).

V

 

[Pete Becker]

In fact, because we nowadays require vector to be contiguous, 23.2.4.3
is incorrect, even in the latest draft. References must remain valid
but will point to new values, if the shrunken vector still contains

No, the requirement in the standard is correct. Implementations are not
required to make sense out of references beyond the point of the erase.
While it may well be possible to do that, it's not required, and that's
what the standard says.