Fast Erase on Map

[moleskyca1]

Hi,

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

map<int,double> m;
// 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?

 

[peter koch]

Hi,

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

map<int,double> m;
// 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

 

[Bernd Strieder]

Hello,

map<int,double> m;
// 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

 

[Victor Bazarov]

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

 

[Jerry Coffin]

Hi,

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

map<int,double> m;
// 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.

 

[Jerry Coffin]

[ ... ]

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.

 

[peter koch]

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

 

[Bronek Kozicki]

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.

 

[moleskyca1]

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.

 

[moleskyca1]

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?

 

[Pierre Barbier de Reuille]

(e-mail address removed) a écrit :

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.

 

[Alan Johnson]

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-lite/operator-overloading.html#faq-13.15