468,491 Members | 2,078 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,491 developers. It's quick & easy.

Fast Erase on Map

Hi,

I know if you call erase when you iterate through map you will crash.
Ex:

map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);

This will crash because erase() will corrupt iterator. Now what I do I
insert key into list and erase each key. After first loop. Is there way
to do this erase in the same search loop?

Aug 16 '06 #1
11 5180

mo********@yahoo.com wrote:
Hi,

I know if you call erase when you iterate through map you will crash.
Ex:

map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);

This will crash because erase() will corrupt iterator. Now what I do I
insert key into list and erase each key. After first loop. Is there way
to do this erase in the same search loop?
Do not increment the iterator after an erase - this is undefined.

for ( map<int, double>::iterator i = m.begin(); i != m.end(); /* NO
INCREMENT */ )
if ( i->second < 0 ) i = m.erase(i);
else
++i;
/Peter

Aug 16 '06 #2
peter koch wrote:
mo********@yahoo.com wrote:
>Hi,

I know if you call erase when you iterate through map you will crash.
Ex:

map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);

This will crash because erase() will corrupt iterator. Now what I do
I insert key into list and erase each key. After first loop. Is
there way to do this erase in the same search loop?

Do not increment the iterator after an erase - this is undefined.

for ( map<int, double>::iterator i = m.begin(); i != m.end(); /* NO
INCREMENT */ )
if ( i->second < 0 ) i = m.erase(i);
else
++i;
std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Aug 16 '06 #3
Hello,

mo********@yahoo.com wrote:
map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);
You have to increment before erase, e.g.

for ( map<int, double>::iterator i = m.begin(); i != m.end(); ) {
map<int, double>::iterator j = i++;
if ( j->second < 0 ) m.erase(j);
}

Bernd Strieder

Aug 16 '06 #4
In article <11**********************@m79g2000cwm.googlegroups .com>,
mo********@yahoo.com says...
Hi,

I know if you call erase when you iterate through map you will crash.
Ex:

map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);

This will crash because erase() will corrupt iterator. Now what I do I
insert key into list and erase each key. After first loop. Is there way
to do this erase in the same search loop?
I'm not sure I have straight what you're trying to accomplish.

From your code it looks like you want to copy only a subset of the items
from the map into a list and erase only those items from the map (I.e.
basically move each qualifying item from the map to the list).

If that's the case, then most of what you have is reasonable. The main
change you need is to use the return value from m.erase(). erase()
returns an iterator to the next item after the one you just erased, so
your loop could look something like:

i = m.begin();
while (i!=m.end())
if (i->second < 0) {
// your_list.push_back(*i);
i = m.erase(i);
}
else
++i;

OTOH, your description sounds like you're trying to copy all the
elements from a map into a list, and then basically destroy the map. If
that's the case, you're probably better off with something like:

std::copy(your_map.begin(), your_map.end(),
std::back_inserter(your_list));
your_map.clear();

If you remove the items from the map individually, it'll re-balance the
tree as your removals change the balance. Since you're removing all the
items, the time spent re-balancing the tree is wasted. clear() knows
it's going to produce an empty tree, so it can avoid re-balancing as it
removes nodes.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Aug 16 '06 #5
In article <eb**********@news.datemas.de>, v.********@comAcast.net
says...

[ ... ]
std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
Oops -- Victor is right. My earlier post should be ignored.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Aug 16 '06 #6

Victor Bazarov wrote:
peter koch wrote:
mo********@yahoo.com wrote:
Hi,

I know if you call erase when you iterate through map you will crash.
Ex:

map<int,doublem;
// insert something
for ( map<int, double>::iterator i = m.begin(); i != m.end(); i++ )
if ( i->second < 0 ) m.erase(i);

This will crash because erase() will corrupt iterator. Now what I do
I insert key into list and erase each key. After first loop. Is
there way to do this erase in the same search loop?
Do not increment the iterator after an erase - this is undefined.

for ( map<int, double>::iterator i = m.begin(); i != m.end(); /* NO
INCREMENT */ )
if ( i->second < 0 ) i = m.erase(i);
else
++i;

std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
Hi Victor

Thanks for the information. Actually, I believe I knew that:
unfortunately i just happened to unlearn it again.

/Peter

Aug 16 '06 #7
Victor Bazarov <v.********@comAcast.netwrote:
> if ( i->second < 0 ) i = m.erase(i);
else
++i;

std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
indeed, but above will result in UB if called on vector or deque (eg.
because someone nicely refactored std::map to typedef and then changed
type of the container). Thus I opt for using nonstandard but safe
extension instead, cited on top of this message
B.
--
Remove -trap- when replying. Usun -trap- gdy odpisujesz.

Aug 16 '06 #8

Victor Bazarov wrote:
std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
Ok, thanks. This work. But I am sorry to ask something stupid. I dont
know why it works?? IMHO m.erase(i++) is almost as if you said
m.erase(i); ++i; But your way works, so they must not be the same..
Sorry if I the only one who does not get it, but more explanation would
be good for me. Thank you.

Aug 16 '06 #9

mo********@yahoo.com wrote:
Victor Bazarov wrote:
std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
I think I know why this work. operator ++(int) for iterator does little
trick:
iterator operator++(int)
{ // postincrement
iterator _Tmp = *this;
++*this;
return (_Tmp);
}
It returns copy of itself "before" increment and return by value, not
reference. Is this correct? So maybe I should use ++i (preincrement)
always unless need postincrement because i++ is doing too much. Is it
true?

Aug 16 '06 #10
mo********@yahoo.com a écrit :
mo********@yahoo.com wrote:
>Victor Bazarov wrote:
>>std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:

if (i->second < 0) m.erase(i++);
else ++i;
I think I know why this work. operator ++(int) for iterator does little
trick:
iterator operator++(int)
{ // postincrement
iterator _Tmp = *this;
++*this;
return (_Tmp);
}
It returns copy of itself "before" increment and return by value, not
reference. Is this correct? So maybe I should use ++i (preincrement)
always unless need postincrement because i++ is doing too much. Is it
true?
Yes, it is true, but it is not a *little trick*, it is mandatory to get
the semantic of the postfix ++ operator.
Aug 16 '06 #11

mo********@yahoo.com wrote:
mo********@yahoo.com wrote:
Victor Bazarov wrote:
std::map::erase does NOT return an iterator (yet). Many current SL
implementations may actually have that, but it shouldn't be relied
upon. The idiom is to increment as part of the call to erase:
>
if (i->second < 0) m.erase(i++);
else ++i;
>
I think I know why this work. operator ++(int) for iterator does little
trick:
iterator operator++(int)
{ // postincrement
iterator _Tmp = *this;
++*this;
return (_Tmp);
}
It returns copy of itself "before" increment and return by value, not
reference. Is this correct? So maybe I should use ++i (preincrement)
always unless need postincrement because i++ is doing too much. Is it
true?
This is in this group's FAQ:
http://www.parashift.com/c++-faq-lit...html#faq-13.15

--
Alan Johnson

Aug 16 '06 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Angus Leeming | last post: by
7 posts views Thread by jose luis fernandez diaz | last post: by
3 posts views Thread by jose luis fernandez diaz | last post: by
6 posts views Thread by isaacyho | last post: by
20 posts views Thread by Tom van Stiphout | last post: by
8 posts views Thread by olanglois | last post: by
6 posts views Thread by catphive.lists | last post: by
3 posts views Thread by subramanian100in | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by theflame83 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.