STL std::map erase

[Pieter Thysebaert]

Hello,

I've got a question conerning erasing key-value pairs from a std::map while
iterating over it.

According to the STL docs, erasing an element in a map invalidates all
iterators pointing to that element

so

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
mymap.erase(i);
mymap.insert(newelement);
}
}

looks like bad practice, and it does crash when it gets executed, at least
on one machine i've run such code on.

So my question is, how do I conveniently erase the "current" element in a
map on the fly while I'm iterating over it? (I admit that this sounds as
weird in English as it sounds in C++)?

Thanx,

Pieter

 

[Karl Heinz Buchegger]

Hello,

I've got a question conerning erasing key-value pairs from a std::map while
iterating over it.

According to the STL docs, erasing an element in a map invalidates all
iterators pointing to that element

so

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
mymap.erase(i);
mymap.insert(newelement);
}
}

looks like bad practice, and it does crash when it gets executed, at least
on one machine i've run such code on.

So my question is, how do I conveniently erase the "current" element in a
map on the fly while I'm iterating over it? (I admit that this sounds as
weird in English as it sounds in C++)?

So what is the real problem?
The problem is, that after erasing the element with iterator i, you need
that iterator again, for the increment, to get at the next map element.
As you know this is not valid. So a possible solution is: get your hands
at an iterator for the next element, *before* you do the erase.

 

[John Harrison]

Hello,

I've got a question conerning erasing key-value pairs from a std::map while
iterating over it.

According to the STL docs, erasing an element in a map invalidates all
iterators pointing to that element

so

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
mymap.erase(i);
mymap.insert(newelement);
}
}

looks like bad practice, and it does crash when it gets executed, at least
on one machine i've run such code on.

So my question is, how do I conveniently erase the "current" element in a
map on the fly while I'm iterating over it? (I admit that this sounds as
weird in English as it sounds in C++)?

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
if (test(i)) {
mymap.erase(i++);
mymap.insert(newelement);
} else {
++i;
}
}

Understanding this code requires a proper understanding of how 'i++' works.

john

 

[Howard]

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); ) {
if (test(i)) {
mymap.erase(i++);
mymap.insert(newelement);
} else {
++i;
}
}

Understanding this code requires a proper understanding of how 'i++'

works.

Ok...so how about an explanation?

I don't see how this is any different. When the call to erase finishes, all
iterators pointing to that element are no longer valid. And isn't an
implementation allowed to wait until the erase call returns, and then
perform that increment? In that case, i cannot be incremented because it is
invalid already, right? For such an implementation, incrementing i in the
function parameter ought to be the same as incrementing it in the for
statement, as far as I can see.

Can't an implementation create identical code for both these cases?...

foo(i++);

vs.

f(i);
i++;

I could see that the implementation might not be *required* to make those
the same, but would it not be *allowed* to make them the same?

What am I missing here?

-Howard

 

[John Harrison]

in
works.

Ok...so how about an explanation?

I don't see how this is any different. When the call to erase finishes, all
iterators pointing to that element are no longer valid. And isn't an
implementation allowed to wait until the erase call returns, and then
perform that increment?

No, that's exactly the point. i++ is a function call, and that function must
happen before the call to erase. The function call returns the 'old' value
of the iterator (that gets passed to erase), and increments the iterator to
its 'new' value as a side effect. All this must happen before erase is
called.

john

 

[Howard]

sounds

No, that's exactly the point. i++ is a function call, and that function must
happen before the call to erase. The function call returns the 'old' value
of the iterator (that gets passed to erase), and increments the iterator to
its 'new' value as a side effect. All this must happen before erase is
called.

john

Ahah! I understand now. Somehow I keep forgetting that ++ is actually a
function call (operator ++()). Thanks for the explanation.

-Howard

 

[Karl Heinz Buchegger]

No, that's exactly the point. i++ is a function call, and that function must
happen before the call to erase.

Ahm.
Thats the wrong explanation.
The correct explanation is:
There is a sequence point immediatly after all arguments
to functions have been evaluated and just before the
function gets called.

So the compiler has no other choice: If there are side
effects during the evaluation of arguments, those side
effects have to be completed before the function gets
called.

That i++ in case of iterators is implemented as a function is
an implementation detail.

 

[Karl Heinz Buchegger]

Ahah! I understand now. Somehow I keep forgetting that ++ is actually a
function call (operator ++()).

It doens't matter.
Even if it were not, the increment has to happen before the
function actually gets called.

 

[John Harrison]

Ahm.
Thats the wrong explanation.
The correct explanation is:
There is a sequence point immediatly after all arguments
to functions have been evaluated and just before the
function gets called.

So the compiler has no other choice: If there are side
effects during the evaluation of arguments, those side
effects have to be completed before the function gets
called.

That i++ in case of iterators is implemented as a function is
an implementation detail.

I wasn't completely sure if the same rules applied to ++ on a built in type,
fairly sure but not completely sure. So I tried to avoid saying 'its because
its a function call' and just gave a descriptive answer.

Thanks for the clarification.

john

 

[Karl Heinz Buchegger]

I wasn't completely sure if the same rules applied to ++ on a built in type,

The ++ has nothing to do with it other then generating a side effect.

 

[Howard]

type,

The ++ has nothing to do with it other then generating a side effect.

So even if i were an int, it would still have to be incremented prior to
calling the function? That sure seems counter-intuitive to the notion of
"post-increment". Makes sense though, I guess.

Also, I guess that means that what is actually passed to the function is a
*copy* of the original iterator, since the original already has to point to
the next item, right?

This is very enlightening. It seems that I always have more to learn with
this language. Thanks...

-Howard

 

[Andrey Tarasevich]

...
So even if i were an int, it would still have to be incremented prior to
calling the function?
Yes.

That sure seems counter-intuitive to the notion of
"post-increment". Makes sense though, I guess.

The function will still receive the original value of 'i'. That's why it
is called "post-increment".

Also, I guess that means that what is actually passed to the function is a
*copy* of the original iterator, since the original already has to point to
the next item, right?

Since this function receives its parameter "by value" - yes, it actually
receives a copy of the original iterator.

 

[Howard]

The function will still receive the original value of 'i'. That's why it
is called "post-increment".


Since this function receives its parameter "by value" - yes, it actually
receives a copy of the original iterator.

Ok...but then, what if you were to pass the iterator *by reference* to some
function instead? What value would the function then get, (considering the
previously stated rule that the increment side-effect has to be completed
prior to the calling of the function)? Would a temporary (un-incremented)
copy be created, passed by reference, and then that copy destroyed after the
return of the function? (That seems to be the only way to maintain the
concept of post-increment without violating the side-effect rule.)

-Howard

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

Ok...but then, what if you were to pass the iterator *by reference* to
some
function instead? What value would the function then get, (considering
the previously stated rule that the increment side-effect has to be
completed
prior to the calling of the function)? Would a temporary (un-incremented)
copy be created, passed by reference, and then that copy destroyed after
the
return of the function? (That seems to be the only way to maintain the
concept of post-increment without violating the side-effect rule.)

That depends on how the iterator implements the pre and post ++ operators.
Habitually the post version returns a copy of the old value.

 

[joey tribbiani]

Hello,

According to the STL docs, erasing an element in a map invalidates all
iterators pointing to that element

so

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
mymap.erase(i);
mymap.insert(newelement);
}
}

Why not the following?

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
i = mymap.erase(i);
}
}

 

[Pete Becker]

Why not the following?

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); i++) {
if (test(i)) {
i = mymap.erase(i);
}
}

Because map::erase returns void according to the standard. Our
implementation returns an iterator, just like vector::erase. The next
version of the standard will probably make that change official.

 

[Jeff Flinn]

Because map::erase returns void according to the standard. Our
implementation returns an iterator, just like vector::erase. The next
version of the standard will probably make that change official.

Even with this extension/future std, the above is incorrect. 'i' will be
effectively incremented twice for each true 'test(i)'. 'i++' needs to be
moved from the for statement to an else clause.

Jeff F

 

[joey tribbiani]

Because map::erase returns void according to the standard. Our
implementation returns an iterator, just like vector::erase. The next
version of the standard will probably make that change official.

Oh, thanks, i didn't know - always thought you are the standard
(actually, never really thought about it)

 

[Howard]

Because map::erase returns void according to the standard. Our
implementation returns an iterator, just like vector::erase. The next
version of the standard will probably make that change official.

Even if it *did* return an iterator, the above code would only work if it
returned an iterator to the *previous* item, because the for loop is going
to increment i every time. The implementation I'm using returns an iterator
to the *next* item (or to end(), if there are none beyond the given item).
In that case, it would have to be writtien:

for (map<...>::iterator i = mymap.begin(); i != mymap.end(); )
{
if (test(i))
i = mymap.erase(i);
else
i++;
}

-Howard

 

[Pete Becker]

Even with this extension/future std, the above is incorrect. 'i' will be
effectively incremented twice for each true 'test(i)'. 'i++' needs to be
moved from the for statement to an else clause.

So tell the person who posted it.