delete elements in associative container

74 views
Skip to first unread message

victor...@computer.org

unread,
Sep 4, 1999, 3:00:00 AM9/4/99
to
I found that there will cause runtime error when I iterate through and
delete the data in a map as shown below:

class Node
{
// something
};

map<string,Node> m;

// fill in the map

for(map<string,Node>::iterator i=m.begin();i!=m.end();++i)
{
m.erase(i); // delete map elements
}

My findings are:
1. No matter what key_type or data_type of the map, when the for loop
finish, the program will cause a runtime error.
2. Only got this problem if the code is compiled by Microsoft VC++ 6.
3. I'd compiled and run the same code by CodeWarrior (Win NT) and GCC
(Solaris) which show no problem.

First of all, I thought it should be a bug. But the documentation (SGI's
STL site) doesn't define precisely the behavior, or the state, of the
iterator passed into erase(iterator) member function in associative
containers. It only said that "the size is decrement by 1" and "destroys
the element the iterator pointed to, and removes it from the map". How
about the iterator itself? Is the iterator become invalid after erase()?


--

Victor Tsang

victor...@computer.org
http://home.netvigator.com/~vyftsang


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]

Howard Hinnant

unread,
Sep 5, 1999, 3:00:00 AM9/5/99
to
In article <7qov6o$mjf$1...@nnrp1.deja.com>, victor...@computer.org =
wrote:

> I found that there will cause runtime error when I iterate through and
> delete the data in a map as shown below:

>=20
> class Node
> {
> // something
> };
>=20
> map<string,Node> m;
>=20


> // fill in the map

>=20
> for(map<string,Node>::iterator i=3Dm.begin();i!=3Dm.end();++i)


> {
> m.erase(i); // delete map elements
> }

>=20


> My findings are:
> 1. No matter what key_type or data_type of the map, when the for loop
> finish, the program will cause a runtime error.
> 2. Only got this problem if the code is compiled by Microsoft VC++ 6.
> 3. I'd compiled and run the same code by CodeWarrior (Win NT) and GCC
> (Solaris) which show no problem.

>=20
> First of all, I thought it should be a bug. But the documentation =


(SGI's
> STL site) doesn't define precisely the behavior, or the state, of the
> iterator passed into erase(iterator) member function in associative

> containers. It only said that "the size is decrement by 1" and =


"destroys
> the element the iterator pointed to, and removes it from the map". How

> about the iterator itself? Is the iterator become invalid after =
erase()?

Speaking for CodeWarrior, we won't guarantee that the above is well
behaved. Once you erase i, the iterator is invalidated and incrementing
it is undefined behavior. You should do:

for(map<string,Node>::iterator i=3Dm.begin();i!=3Dm.end();)
{
m.erase(i++); // delete map elements
}

This way the iterator is incremented before it is erased.

-Howard

Darin Adler

unread,
Sep 5, 1999, 3:00:00 AM9/5/99
to
victor...@computer.org wrote:

> I found that there will cause runtime error when I iterate through and
> delete the data in a map as shown below:
>

> class Node
> {
> // something
> };
>
> map<string,Node> m;
>

> // fill in the map
>

> for(map<string,Node>::iterator i=3Dm.begin();i!=3Dm.end();++i)
> {
> m.erase(i); // delete map elements
> }
>

> [...]


>
> First of all, I thought it should be a bug. But the documentation =
(SGI's
> STL site) doesn't define precisely the behavior, or the state, of the
> iterator passed into erase(iterator) member function in associative
> containers. It only said that "the size is decrement by 1" and =
"destroys
> the element the iterator pointed to, and removes it from the map". How
> about the iterator itself? Is the iterator become invalid after =
erase()?

The standard says that the iterator becomes invalid after erase(). It
specifically says that iterators pointing to elements other than the one
erased are not made invalid. This is said in the standard in section =
23.1.2,
paragraph 8.

-- Darin

John Potter

unread,
Sep 5, 1999, 3:00:00 AM9/5/99
to
On 4 Sep 1999 17:52:33 -0400, victor...@computer.org wrote:

: I found that there will cause runtime error when I iterate through and
: delete the data in a map as shown below:

:
: for(map<string,Node>::iterator i=m.begin();i!=m.end();++i)


: {
: m.erase(i); // delete map elements

: }
:
: My findings are:


: 1. No matter what key_type or data_type of the map, when the for loop
: finish, the program will cause a runtime error.

I will assume that you know it happens at the end of the loop. It
could happen on the first ++.

: 2. Only got this problem if the code is compiled by Microsoft VC++ 6.

Not an MS problem, your code is bad.

: 3. I'd compiled and run the same code by CodeWarrior (Win NT) and GCC


: (Solaris) which show no problem.

You were lucky.

: First of all, I thought it should be a bug. But the documentation


(SGI's
: STL site) doesn't define precisely the behavior, or the state, of the
: iterator passed into erase(iterator) member function in associative
: containers. It only said that "the size is decrement by 1" and

"destroys
: the element the iterator pointed to, and removes it from the map". How
: about the iterator itself? Is the iterator become invalid after

erase()?

Yes. For associative containers and list, erase invalidates the
iterator(s) pointing to the erased item. For vector and deque, it
invalidates iterator(s) pointing to the erased item or anything to
the right of it.

In the above code, you erase the item invalidating the iterator and
then increment it. It points to an item which has been removed and
anything can happen on the increment.

Assuming a test for the erase since clear would erase everything.
The usual algorithm for associative containers and list is

for (Iter it = c.begin(); it != c.end();)
if (condition(*i))
c.erase(i ++);
else
++ i;

This doesn't work for vector and deque. The iterators are
invalidated because they now point to items other than the original
one (last would be off end). The usual algorithm here is

for (Iter it = c.begin(); it != c.end();)
if (condition(*i))
c.erase(i);
else
++ i;

It occurs that to me that there may be a common algorithm.

for (Iter it = c.end(); it != c.begin();) {
Iter pre(it);
-- pre;
if (condition(*pre)) {
c.erase(pre);
if (it != c.begin())
-- it;
}
else
-- it;
}

Of course, this problem motivated the standard remove_if for
sequences, but it does not apply to associative containers.

John

Siemel B. Naran

unread,
Sep 6, 1999, 3:00:00 AM9/6/99
to
On 4 Sep 1999 17:52:33 -0400, victor...@computer.org

>for(map<string,Node>::iterator i=m.begin();i!=m.end();++i)


>{
> m.erase(i); // delete map elements
>}

Recall the definition of the increment operator for list.

list::iterator& list::iterator::operator++()
{
d_iter=d_iter->next;
return *this;
}

The "m.erase(i)" deletes the Node. Hence the expression "d_iter->next"
is a memory access violation because it tries to access memory that has
already been deallocated. MSVC is right in giving a runtime error.

BTW, map::iterator is similar to list::iterator, just much more
complicated.


Would this work?

typedef std::map<std::string,Node>::iterator Iter;
Iter begin=m.begin();
const Iter end=m.end();
while (begin!=end)
{
Iter now=begin++;
m.erase(now);
}

--
--------------
siemel b naran
--------------

Tim W

unread,
Sep 6, 1999, 3:00:00 AM9/6/99
to
I have used this algorithm in the past for removing elements of any STL
container.

while ( ! container.empty() )
{
container.erase( container.begin() );
}


John Potter <jpo...@falcon.lhup.edu> wrote in message
news:37d238a7...@news.csrlink.net...
[snip]

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

James Briggs

unread,
Sep 6, 1999, 3:00:00 AM9/6/99
to
Howard Hinnant wrote:
>
> Speaking for CodeWarrior, we won't guarantee that the above is well
> behaved. Once you erase i, the iterator is invalidated and incrementing
> it is undefined behavior. You should do:
>
> for(map<string,Node>::iterator i=3Dm.begin();i!=3Dm.end();)
> {
> m.erase(i++); // delete map elements
> }
>
> This way the iterator is incremented before it is erased.
>

If all you are doing is erasing everything in the map try

map.clear();

which does

map.erase(map.begin(), map.end());

Siemel B. Naran

unread,
Sep 6, 1999, 3:00:00 AM9/6/99
to
On 5 Sep 1999 14:26:46 -0400, John Potter <jpo...@falcon.lhup.edu> wrote:

> for (Iter it = c.begin(); it != c.end();)
> if (condition(*i))
> c.erase(i ++);
> else
> ++ i;

BTW, are you missing some braces?

This method forces you to write the call to operator++ twice.
Not a big deal, but how about

Iter it=c.begin();
while (it!=c.end()) {
const Iter nx=it++;
if (condition(*nx)) c.erase(nx);
}


>This doesn't work for vector and deque. The iterators are
>invalidated because they now point to items other than the original
>one (last would be off end). The usual algorithm here is
>
> for (Iter it = c.begin(); it != c.end();)
> if (condition(*i))
> c.erase(i);
> else
> ++ i;

Good point.

Note that for the sequence containers, we can just do

Iter it=c.begin();
while (it!=c.end()) {
if (condition(*it)) it=c.erase(it);
else ++it;
}


>It occurs that to me that there may be a common algorithm.
>
> for (Iter it = c.end(); it != c.begin();) {
> Iter pre(it);
> -- pre;
> if (condition(*pre)) {
> c.erase(pre);
> if (it != c.begin())
> -- it;
> }
> else
> -- it;
> }

suppose c is a vector<int>.
'it' first points to one past the last element.
suppose we must remove the last element.
now 'it' points to two past the last element.
so using 'it' in "it!=c.end()" is undefined.


>Of course, this problem motivated the standard remove_if for
>sequences, but it does not apply to associative containers.

I don't know how to write a general algorithm that applies to
all containers. Well, one method does come to mind -- store
all the items to be removed in a std::deque<iterator>, then
for_each element in this container of iterators, apply
c.erase(element).

--
--------------
siemel b naran
--------------

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Andrew Koenig

unread,
Sep 6, 1999, 3:00:00 AM9/6/99
to
In article <hinnant-0409...@ith3-103.twcny.rr.com>,
Howard Hinnant <hinnant@anti-spam_metrowerks.com> wrote:

>Speaking for CodeWarrior, we won't guarantee that the above is well
>behaved. Once you erase i, the iterator is invalidated and incrementing
>it is undefined behavior. You should do:

>for(map<string,Node>::iterator i=m.begin();i!=m.end();)


>{
> m.erase(i++); // delete map elements
>}

>This way the iterator is incremented before it is erased.

The example hangs by a fine thread, but I think it's right.

The thread is fine because it relies on there being a sequence point
before the call. I have seen C compilers that, if i were a pointer,
would have incremented i *after* the call, but I believe that ISO C
doesn't offer that much latitude (this was before the C standard)
and there's no way that could happen for a class object anyway (because
the implementation can't possibly call a function until after it
has evaluated the arguments)
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark

John Potter

unread,
Sep 7, 1999, 3:00:00 AM9/7/99
to
On 6 Sep 1999 14:39:15 -0400, sbn...@uiuc.edu (Siemel B. Naran) wrote:

: On 5 Sep 1999 14:26:46 -0400, John Potter <jpo...@falcon.lhup.edu> wrote:
:
: > for (Iter it = c.begin(); it != c.end();)
: > if (condition(*i))
: > c.erase(i ++);
: > else
: > ++ i;
:
: BTW, are you missing some braces?

No. For gets one statement and if-else is a statement. Each branch
also gets one statement and has one. If else-if else-if ... else-if
else is still one statement.

: This method forces you to write the call to operator++ twice.


: Not a big deal, but how about
:
: Iter it=c.begin();
: while (it!=c.end()) {
: const Iter nx=it++;
: if (condition(*nx)) c.erase(nx);

: }

Forces you to use braces and a named temporary. Not a big deal, and
sure that is also fine.

: >This doesn't work for vector and deque. The iterators are


: >invalidated because they now point to items other than the original
: >one (last would be off end). The usual algorithm here is
: >
: > for (Iter it = c.begin(); it != c.end();)
: > if (condition(*i))
: > c.erase(i);
: > else
: > ++ i;
:
: Good point.

Thank you.

: Note that for the sequence containers, we can just do


:
: Iter it=c.begin();
: while (it!=c.end()) {
: if (condition(*it)) it=c.erase(it);
: else ++it;

: }

Yes. That works for list while the above does not. If the associative
containers also returned the iterator to next, it would work for
everything. Interesting to note that the associative algorithms also
work for list.

: >It occurs that to me that there may be a common algorithm.


: >
: > for (Iter it = c.end(); it != c.begin();) {
: > Iter pre(it);
: > -- pre;
: > if (condition(*pre)) {
: > c.erase(pre);
: > if (it != c.begin())
: > -- it;
: > }
: > else
: > -- it;
: > }
:
: suppose c is a vector<int>.
: 'it' first points to one past the last element.
: suppose we must remove the last element.
: now 'it' points to two past the last element.
: so using 'it' in "it!=c.end()" is undefined.

I'm not sure about that. Iterators are implementation defined things,
but if the == and != operators reduce to pointer comparisons, any two
pointers to the same type may be compared for equality. This holds in
the most common implementations.

More importantly, the algorithm is just plain wrong. Amazing how much
clearer the bugs are in the reader than in the composer. :) I have
been waiting for someone to find fault with it.

: >Of course, this problem motivated the standard remove_if for


: >sequences, but it does not apply to associative containers.
:
: I don't know how to write a general algorithm that applies to
: all containers. Well, one method does come to mind -- store
: all the items to be removed in a std::deque<iterator>, then
: for_each element in this container of iterators, apply
: c.erase(element).

Should work if you work right to left, otherwise vector/deque
iterators would be invalidated before they were used.

Here is a general purpose algorithm which assumes that invalid
iterators may still be compared as stated above. This time I
used two implementations to verify my composer. It doesn't
work for arrays, but then, nobody uses them. :)

template <class Container, class Predicate>
void erase_if (Container& c, Predicate condition) {
typedef typename Container::iterator Iter;


for (Iter it = c.begin(); it != c.end(); )

if (condition(*it)) {
Iter cur(it ++);
c.erase(cur);
Iter pre(it);
if (cur == c.end() // last of static, it past end
|| it != c.begin() // not first of dynamic, -- ok
&& -- pre == cur) // static
it = cur;
}
else
++ it;
}

The purpose of a general algorithm is to allow switching the type
of container without rewriting code. One of the goals of the
generic approach. I wonder if it is useful. List works with
either algorithm. What is the chance of having this kind of problem
and switching between vector/deque and set/map?

If efficiency comes into play, this algorithm is not efficient for
vector/deque. A misconception of mine on remove_if fostered by
uncorrected posts to this group (I have one now) was that it moved
the removed items to the end of the container. Given the items
0 1 2 3 4 5 6 7 8 9 10 and the predicate even, I thought that the
result would be 1 3 5 7 9 0 2 4 6 8 10. The actual result would
be 1 3 5 7 9 5 6 7 8 9 10. Remove_if is linear for vector/deque
while the above erase algorithms are quadratic. OTOH, remove_if
could be more expensive for list than the above algorithm if copies
are expensive, but still linear.

John

John Potter

unread,
Sep 7, 1999, 3:00:00 AM9/7/99
to
On 6 Sep 1999 14:01:15 -0400, "Tim W" <timi...@stny.rr.com> wrote:

: I have used this algorithm in the past for removing elements of any STL


: container.
:
: while ( ! container.empty() )
: {
: container.erase( container.begin() );

: }

Well yes, but

container.clear();

is much more efficient for both the coder and the computer. You must
have missed the first line that you quoted.

Interesting that containers do not require clear, but sequences and
associative containers do require clear. Are there any standard
containers which are not one of those?

John
:
:
: John Potter <jpo...@falcon.lhup.edu> wrote in message


: news:37d238a7...@news.csrlink.net...
: [snip]
: > Assuming a test for the erase since clear would erase everything.

Siemel B. Naran

unread,
Sep 7, 1999, 3:00:00 AM9/7/99
to
On 6 Sep 1999 14:01:15 -0400, Tim W <timi...@stny.rr.com> wrote:

>I have used this algorithm in the past for removing elements of any STL
>container.
>
>while ( ! container.empty() )
>{
> container.erase( container.begin() );
>}

For a vector or deque, this is inefficient.

To erase all the elements but not release all the memory do
container.erase(container.begin(),container.end());

To erase all the elements and release all the memory do
Container().swap(container);

--
--------------
siemel b naran
--------------

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

Siemel B. Naran

unread,
Sep 7, 1999, 3:00:00 AM9/7/99
to
On 6 Sep 1999 14:11:44 -0400, James Briggs


>If all you are doing is erasing everything in the map try
>
>map.clear();
>
>which does
>
>map.erase(map.begin(), map.end());

To really clear the memory the map is using (ie, give the memory to
other processes to use), do this

Map().swap(map);

where Map is a typedef for std::map<std::string,int>.

Tim W

unread,
Sep 8, 1999, 3:00:00 AM9/8/99
to
Sorry I wasn't more clear. I use this method when I need to do some sort of
processing on each item before it's removed:

while ( ! container.empty() )
{

// ... Do something with container.begin()
// ...

container.erase( container.begin() );
}

John Potter <jpo...@falcon.lhup.edu> wrote in message

news:37d42d73...@news.csrlink.net...


> On 6 Sep 1999 14:01:15 -0400, "Tim W" <timi...@stny.rr.com> wrote:
>
> : I have used this algorithm in the past for removing elements of any STL
> : container.
> :
> : while ( ! container.empty() )
> : {
> : container.erase( container.begin() );

> : }
>
> Well yes, but
>
> container.clear();
>
> is much more efficient for both the coder and the computer. You must
> have missed the first line that you quoted.
>

Carl Barron

unread,
Sep 8, 1999, 3:00:00 AM9/8/99
to
John Potter <jpo...@falcon.lhup.edu> wrote:

>=20


> template <class Container, class Predicate>
> void erase_if (Container& c, Predicate condition) {
> typedef typename Container::iterator Iter;

> for (Iter it =3D c.begin(); it !=3D c.end(); )


> if (condition(*it)) {
> Iter cur(it ++);
> c.erase(cur);
> Iter pre(it);

> if (cur =3D=3D c.end() // last of static, it past end
> || it !=3D c.begin() // not first of dynamic, -- ok
> && -- pre =3D=3D cur) // static
> it =3D cur;
> }
> else
> ++ it;
> }
>=20

well iterator erase(iterator) is a member of every STL container
the return value refers to the 'next' element of the container after
that to which the argument 'points'. therefore
template <class C,class P)
void erase_if(C & container,P &pred)
{
for(typename C::iterator it =3D container.begin(),
it!=3Dcontainer.end(), )
{
if(pred(*it))
it =3D container.erase(it);
else
++it;
}
}
should not need to worry about invalid iterators at all. And should
also be more efficient. In fact it can even be called remove_if as
there are no STL remove_if's with such arguments....

John Potter

unread,
Sep 9, 1999, 3:00:00 AM9/9/99
to
On 8 Sep 1999 19:06:21 -0400, cbar...@ix.netcom.com (Carl Barron)
wrote:

: John Potter <jpo...@falcon.lhup.edu> wrote:
:
: >
: > template <class Container, class Predicate>


: > void erase_if (Container& c, Predicate condition) {
: > typedef typename Container::iterator Iter;
: > for (Iter it = c.begin(); it != c.end(); )
: > if (condition(*it)) {
: > Iter cur(it ++);
: > c.erase(cur);
: > Iter pre(it);
: > if (cur == c.end() // last of static, it past end
: > || it != c.begin() // not first of dynamic, -- ok
: > && -- pre == cur) // static
: > it = cur;
: > }
: > else
: > ++ it;

: > }
: >
:
: well iterator erase(iterator) is a member of every STL container


: the return value refers to the 'next' element of the container after
: that to which the argument 'points'.

I didn't know that (quickly pulls up the standard to check:). Table
66 containers, no such function. Table 67 sequences, contains that
function. Table 69 associative containers, contains void
erase(iterator).

: therefore

The following only works for sequences. If you check earlier in that
article, you will find that Siemel posted that algorithm noting that
it was for sequences, and I commented that it would work for all if
associative containers returned the next iterator also.

: template <class C,class P)


: void erase_if(C & container,P &pred)
: {

: for(typename C::iterator it = container.begin(),
: it!=3Dcontainer.end(), )
: {
: if(pred(*it))
: it = container.erase(it);


: else
: ++it;
: }
: }
: should not need to worry about invalid iterators at all. And should
: also be more efficient.

Yes slightly, for sequences; however, remove_if is more efficient
(linear) for vector and deque where this algorithm is quadratic.

: In fact it can even be called remove_if as


: there are no STL remove_if's with such arguments....

No, please don't make that mistake. Remove does not change the size
of the container. When the container size changes, it is called
erase. See remove, remove_if which must be followed by erase to
finish the job and compare to erase(key) for associative containers
which does the whole job.

Carl Barron

unread,
Sep 13, 1999, 3:00:00 AM9/13/99
to

> : template <class C,class P)
> : void erase_if(C & container,P &pred)
> : {
> : /*a*/

> : for(typename C::iterator it = container.begin(),
> : it!=container.end(), )
> : {
> : /* b */

> : if(pred(*it))
> : it = container.erase(it);
> : else
> : ++it;
> : }
> : }
> : should not need to worry about invalid iterators at all. And
should
> : also be more efficient.
>
I stand corrected. Don't see why the standard is as it is but it is.

template <class C,class P>
void erase_if(C &container,P &pred)
{
typename C::iterator jt;

for(typename C::iterator it= container.begin();
it!=container.end();)
{
if(pred(*jt))
{
jt = it;++it;
container.erase(jt);
}
else
++it;
}
}
But it probably is not much better than using erase(it++); etc.
It is now valid for the standard containers. It probably does save some
temporaries on a dumb compiler. It might not result in a creation of a
new temporary iterator once each time the erase occurs. [operator = ,
may be faster than a copy constructor, it is probably not much worse as
the temp needs to be destructed each time it is created. It appears to
be nit picking

Carl Barron

unread,
Sep 13, 1999, 3:00:00 AM9/13/99
to
I did some quicktests with vector<int>,list<int>,and multiset<int> with
a general predicate that deletes all x0' from a container of 5 copies of
the set of integers 0-19, 10,000 times for each and timed the results of
erase if using post increwment and a hold iterater, [see my other very
recent posting in this thread, its posted but not cleared at this time.]

Codewarrior pro 5 on a ppc603e gives the following where 200 clock_ticks
== 1 second.

erasing from a vector without i++ takes 538 clock_ticks
erassing from a vector with i++ takes523 clock_ticks
erasing from a list without i++ takes 307 clock ticks
erasing from a list with i++ takes 321 clock_ticks
erasing from a set without i++ takes 985 cloxk_ticks
erasing from a set with i++ takes 1156 clock_ticks
Done!!

results are not too suprising as vector<T>::iterator is a T *, in this
implimentation, and list does not move other elenents on a erase of one,
and a mutliset iterator is probably the most complicated iterator
tested. Same algorithm's applied via templates. I conclude that the
latest offering works with sequence and associative containers, and
generally proform better if C::iterator != C::iterator::value_type *.
then they are close as its only about 15 micro seconds difference on a
100 element container with duplicates.

John Potter

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
On 13 Sep 1999 23:40:08 -0400, cbar...@ix.netcom.com (Carl Barron)
wrote:

: I stand corrected. Don't see why the standard is as it is but it is.


:
: template <class C,class P>
: void erase_if(C &container,P &pred)
: {
: typename C::iterator jt;
:
: for(typename C::iterator it= container.begin();
: it!=container.end();)
: {
: if(pred(*jt))
: {
: jt = it;++it;
: container.erase(jt);

This does not work for vector/deque. Consider:

1 2 3 4 5

i

j = i; ++ i;

1 2 3 4 5

j i
erase(j)

1 2 4 5
i

You have skipped the value 4. That is why the standard says that
all iterators to the right of the erase are invalidated.

: }
: else
: ++it;
: }
: }

The times in the other article don't mean much. Try the standard
erase(remove_if(..)..) version on vector to see why.

Reply all
Reply to author
Forward
0 new messages