Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL std::map erase

Reply
Thread Tools

STL std::map erase

 
 
Pieter Thysebaert
Guest
Posts: n/a
 
      05-13-2004


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

 
Reply With Quote
 
 
 
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      05-13-2004
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
John Harrison
Guest
Posts: n/a
 
      05-13-2004

"Pieter Thysebaert" <(E-Mail Removed)> wrote in
message news:c8010s$a5l$(E-Mail Removed)...
>
>
> 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


 
Reply With Quote
 
Howard
Guest
Posts: n/a
 
      05-13-2004

"John Harrison" <(E-Mail Removed)> 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


 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      05-13-2004

"Howard" <(E-Mail Removed)> wrote in message
news:7cNoc.51315$(E-Mail Removed)...
>
> "John Harrison" <(E-Mail Removed)> 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


 
Reply With Quote
 
Howard
Guest
Posts: n/a
 
      05-13-2004

"John Harrison" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> "Howard" <(E-Mail Removed)> wrote in message
> news:7cNoc.51315$(E-Mail Removed)...
> >
> > "John Harrison" <(E-Mail Removed)> 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



>
>



 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      05-13-2004
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
(E-Mail Removed)
 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      05-13-2004
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
(E-Mail Removed)
 
Reply With Quote
 
John Harrison
Guest
Posts: n/a
 
      05-13-2004

"Karl Heinz Buchegger" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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


 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      05-13-2004
John Harrison wrote:
>
> "Karl Heinz Buchegger" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> > 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
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
erase vs. erase al.cpwn@gmail.com C++ 7 03-30-2006 11:45 AM
How do i erase all information in my orkut and erase the link to the orkut account? mountbatten@gmail.com Computer Support 1 10-31-2005 12:03 AM
Re: STL insert/erase behaviour Andrew Koenig C++ 0 08-13-2003 06:08 PM
Re: STL insert/erase behaviour John Harrison C++ 0 08-13-2003 05:51 PM
How do I erase a file that wont let me erase it? Dale Custer Computer Support 4 07-06-2003 09:48 AM



Advertisments