By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,898 Members | 2,039 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,898 IT Pros & Developers. It's quick & easy.

STL std::map erase

P: n/a


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

Jul 22 '05 #1
Share this Question
Share on Google+
26 Replies


P: n/a
Pieter Thysebaert wrote:

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.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #2

P: n/a

"Pieter Thysebaert" <pi***************@toorug.muchac.spambe> wrote in
message news:c8**********@gaudi2.UGent.be...


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
Jul 22 '05 #3

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:2ghjh6F2s3b7U1@uni-> >
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.

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
Jul 22 '05 #4

P: n/a

"Howard" <al*****@hotmail.com> wrote in message
news:7c*********************@bgtnsc05-news.ops.worldnet.att.net...

"John Harrison" <jo*************@hotmail.com> wrote in message
news:2ghjh6F2s3b7U1@uni-> >
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.

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
Jul 22 '05 #5

P: n/a

"John Harrison" <jo*************@hotmail.com> wrote in message
news:2g************@uni-berlin.de...

"Howard" <al*****@hotmail.com> wrote in message
news:7c*********************@bgtnsc05-news.ops.worldnet.att.net...

"John Harrison" <jo*************@hotmail.com> wrote in message
news:2ghjh6F2s3b7U1@uni-> >
> 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.

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
Ahah! I understand now. Somehow I keep forgetting that ++ is actually a
function call (operator ++()). Thanks for the explanation.

-Howard

Jul 22 '05 #6

P: n/a
John Harrison wrote:


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
kb******@gascad.at
Jul 22 '05 #7

P: n/a
Howard wrote:


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.
--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #8

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:40***************@gascad.at...
John Harrison wrote:


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.

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
Jul 22 '05 #9

P: n/a
John Harrison wrote:

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:40***************@gascad.at...
John Harrison wrote:


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.


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.

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #10

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:40***************@gascad.at...
John Harrison wrote:

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:40***************@gascad.at...
John Harrison wrote:
>
>
> 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.

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.

--
Karl Heinz Buchegger
kb******@gascad.at

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



Jul 22 '05 #11

P: n/a
Howard wrote:
...
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.

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #12

P: n/a

"Andrey Tarasevich" <an**************@hotmail.com> wrote in message
news:10*************@news.supernews.com...
Howard wrote:
...
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.


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

Jul 22 '05 #13

P: n/a
Howard wrote:
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.)


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

--
Salu2
Jul 22 '05 #14

P: n/a
Pieter Thysebaert wrote:

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


Jul 22 '05 #15

P: n/a
joey tribbiani wrote:

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.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #16

P: n/a

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
joey tribbiani wrote:

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.


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
Jul 22 '05 #17

P: n/a
Pete Becker wrote:
joey tribbiani wrote:
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.

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

P: n/a

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
joey tribbiani wrote:

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.


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
Jul 22 '05 #19

P: n/a
Jeff Flinn wrote:

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
joey tribbiani wrote:

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.


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.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #20

P: n/a
Howard wrote:

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
joey tribbiani wrote:

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.


Even if it *did* return an iterator, the above code would only work if it


So tell the person who posted it.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #21

P: n/a

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
Jeff Flinn wrote:

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
joey tribbiani wrote:
>
> 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.


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.


Assuming this thread is important to the OP, I just did. ;)

I'm also telling someone googling down this thread a few years hence, when
the T::iterator is the standard, that this needs to be corrected.

Jeff F
Jul 22 '05 #22

P: n/a
Jeff Flinn wrote:
So tell the person who posted it.


Assuming this thread is important to the OP, I just did. ;)


Sigh. Okay. RESPOND TO THE PERSON WHO ORIGINALLY POSTED THE WORDS THAT
YOU THINK ARE INCORRECT. Is it really that hard to grasp?

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #23

P: n/a

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
Jeff Flinn wrote:
So tell the person who posted it.


Assuming this thread is important to the OP, I just did. ;)


Sigh. Okay. RESPOND TO THE PERSON WHO ORIGINALLY POSTED THE WORDS THAT
YOU THINK ARE INCORRECT. Is it really that hard to grasp?

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)


Why are you so upset??? So our responses fall under yours instead of
directly under joey's. So what? He should be perfectly capable of seeing
the whole conversation, and the context of the responses. (Aren't you?)
It's not like we sent emails to you personally. We posted them to the
newsgroup, as follow-ups to your response. There's no sense in now going
back and posting *again*, directly to joey's post, just so he (and everyone
else) can read the same answer for the third time. Relax a little. We're
not attacking you, just posting follow-up info to the conversation.

-Howard


Jul 22 '05 #24

P: n/a
Howard wrote:

"Pete Becker" <pe********@acm.org> wrote in message
news:40***************@acm.org...
Jeff Flinn wrote:

> So tell the person who posted it.

Assuming this thread is important to the OP, I just did. ;)

Sigh. Okay. RESPOND TO THE PERSON WHO ORIGINALLY POSTED THE WORDS THAT
YOU THINK ARE INCORRECT. Is it really that hard to grasp?

Why are you so upset??? So our responses fall under yours instead of
directly under joey's. So what?


So you confuse things when you respond to the wrong message. I really
don't see why that's so hard to grasp.
He should be perfectly capable of seeing
the whole conversation, and the context of the responses. (Aren't you?)
It's not like we sent emails to you personally. We posted them to the
newsgroup, as follow-ups to your response. There's no sense in now going
back and posting *again*, directly to joey's post, just so he (and everyone
else) can read the same answer for the third time.


Sigh. Nobody suggested posting *again*.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Jul 22 '05 #25

P: n/a
Howard wrote:
...
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.)


Yes, that's pretty much correct. Note that if you make an attempt to
pass it by non-constant reference, the code simply won't compile,
because post-increment normally returns an rvalue and non-constant
reference cannot be bound to an rvalue. But if the function is declared
with constant reference parameter, then everything will work as you
describe, i.e. the reference will be bound to a temporary object, which
holds the original (un-incremented) value.

--
Best regards,
Andrey Tarasevich

Jul 22 '05 #26

P: n/a

"Pieter Thysebaert" <pi***************@toorug.muchac.spambe> wrote in message news:c8**********@gaudi2.UGent.be...


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


I've run into that situation many times with maps, lists and other containers,
and the easiest solution, I've found, is to get a copy of i called j, decrement i,
then erase (*j). Like so:

map<K, V> mymap; // where K and V are types
map<K, V>::iterator i, j; // get some iterators
for (i = mymap.begin(); i != mymap.end(); i++)
{
if (test(i))
{
j = i; // get temp. copy of i
--i; // gonna kill place where i pointed, so back up!
mymap.erase(j); // erase element where i used to point
mymap.insert(newelement); // automatically sorted; where did it go?
}
}

If i was decremented and (*j) erased, then when execution resumes at the
top of the loop, i will be incremented to the next un-erased item.

Also be aware that there's no guarantee the inserted item went the same
place as the deleted one; map is automatically sorted by key, so the new
element could end up anywhere, depending on sort order.
--
Cheers,
Robbie Hatley
Tustin, CA, USA
email: lonewolfintj at pacbell dot net
web: home dot pacbell dot net slant earnur slant

----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Jul 22 '05 #27

This discussion thread is closed

Replies have been disabled for this discussion.