std::map - erase+continue

[Gernot Frisch]

restart:
for (std::map<x,y>: :iterator it = m.begin(); it!=m.end(); ++it)
{
if( it->second.isbad () )
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
// goto restart;
}
}

this does not remove all bad ones... If I insert a "goto restart" it
works...

What am I doing wrong?
--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%c gl%ssic%ccom%c" , "ma", 58, 'g', 64, "ba", 46, 10);}

[Aslan Kral]

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

restart:
for (std::map<x,y>: :iterator it = m.begin(); it!=m.end(); ++it)
{
if( it->second.isbad () )
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
// goto restart;
}
}

this does not remove all bad ones... If I insert a "goto restart" it
works...

What am I doing wrong?

When you call "m.erase(it )", next is also invalidated. I guess the following
would fix it.

++next;
x nextkey = next->first;
m.erase(it);
it = m.find(nextkey) ; // instead of it=next

--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%c gl%ssic%ccom%c" , "ma", 58, 'g', 64, "ba", 46, 10);}

[Aslan Kral]

"Aslan Kral" <as**********@y ahoo.com>, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

restart:
for (std::map<x,y>: :iterator it = m.begin(); it!=m.end(); ++it)
{
if( it->second.isbad () )
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
// goto restart;
}
}

this does not remove all bad ones... If I insert a "goto restart" it
works...

What am I doing wrong?

When you call "m.erase(it )", next is also invalidated. I guess the

following would fix it.

++next;
x nextkey = next->first;
m.erase(it);
it = m.find(nextkey) ; // instead of it=next I just realized that it might also be because you increment the iterator
after ++next. Maybe you should do it in a while loop. You see what I mean?

while (it != m.end())
{
if (..)
{
....
++next; // you have already positioned to next
}
else
{
++it; //next
}
}

--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%c gl%ssic%ccom%c" , "ma", 58, 'g', 64, "ba", 46, 10);}

[Andre Kostur]

"Aslan Kral" <as**********@y ahoo.com> wrote in
news:39******** *****@individua l.net:

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

restart:
for (std::map<x,y>: :iterator it = m.begin(); it!=m.end(); ++it)
{
if( it->second.isbad () )
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
// goto restart;
}
}

this does not remove all bad ones... If I insert a "goto restart" it
works...

What am I doing wrong?

When you call "m.erase(it )", next is also invalidated. I guess the
following would fix it.

Not in a map it isn't (granted, it is invalidated in a vector...). When
'it' is erased, only iterators to the same element are invalidated.
'next' has already been incremented to the next item (before 'it' has
been erased), so 'next' is safe from being invalidated in this manner.
However, as you point out in your next message, this code is happening
within a for loop, so there are two possible issues that crop up:
1) Adjacent bad items won't get erased, since the second one will be
skipped over.
2) If the last item in the map is bad, undefined behaviour is invoked by
causing the iterator to be incremented past the end() iterator in the
map.

++next;
x nextkey = next->first;
m.erase(it);
it = m.find(nextkey) ; // instead of it=next

This would probably be less efficient (in terms of time) than the
original code (after correcting for the double increment of the iterator)
as the original code only increments the iterator, this "corrected" code
would require the system to search the entire map again.

[Aslan Kral]

"Andre Kostur" <nn******@kostu r.net>, haber iletisinde þunlarý
yazdý:Xn******* *************** *********@207.3 5.177.134...

"Aslan Kral" <as**********@y ahoo.com> wrote in
news:39******** *****@individua l.net:

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

restart:
for (std::map<x,y>: :iterator it = m.begin(); it!=m.end(); ++it)
{
if( it->second.isbad () )
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
// goto restart;
}
}

this does not remove all bad ones... If I insert a "goto restart" it
works...

What am I doing wrong?

When you call "m.erase(it )", next is also invalidated. I guess the
following would fix it.

Not in a map it isn't (granted, it is invalidated in a vector...). When
'it' is erased, only iterators to the same element are invalidated.
'next' has already been incremented to the next item (before 'it' has
been erased), so 'next' is safe from being invalidated in this manner.

OK.
However, as you point out in your next message, this code is happening
within a for loop, so there are two possible issues that crop up:
1) Adjacent bad items won't get erased, since the second one will be
skipped over.
2) If the last item in the map is bad, undefined behaviour is invoked by
causing the iterator to be incremented past the end() iterator in the
map.

++next;
x nextkey = next->first;
m.erase(it);
it = m.find(nextkey) ; // instead of it=next

This would probably be less efficient (in terms of time) than the
original code (after correcting for the double increment of the iterator)
as the original code only increments the iterator, this "corrected" code
would require the system to search the entire map again.

Right. That was because I thought there might a problem there but later I
realized that was not the case.

[Gernot Frisch]

so... this ins the best: ?

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
}
else
++it;
}

[Aslan Kral]

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

so... this ins the best: ?

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
}
else
++it;
}

Maybe. Does it now work the way you want it to? Personally I like "while"
and you seem to prefer "for". No problem.

[Gernot Frisch]

"Aslan Kral" <as**********@y ahoo.com> schrieb im Newsbeitrag
news:39******** *****@individua l.net...

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

so... this ins the best: ?

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
}
else
++it;
}

Maybe. Does it now work the way you want it to? Personally I like
"while"
and you seem to prefer "for". No problem.

Yes, it works now. Thank you.
BTW: Does a std::map re-allocate memory for items when
inserting/removing, or does it behave like a std::list?
-Gernot

[Aslan Kral]

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

"Aslan Kral" <as**********@y ahoo.com> schrieb im Newsbeitrag
news:39******** *****@individua l.net...

"Gernot Frisch" <[e-mail] >, haber iletisinde þunlarý
yazdý:39******* ******@individu al.net...

so... this ins the best: ?

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
}
else
++it;
}

Maybe. Does it now work the way you want it to? Personally I like
"while"
and you seem to prefer "for". No problem.

Yes, it works now. Thank you.
BTW: Does a std::map re-allocate memory for items when
inserting/removing, or does it behave like a std::list?
-Gernot

map/multimap/set/multiset are based on tree structures and they allocate
when you call insert and free when you call erase/clear. So they don't have
a member function like resize() as in list/vector.

[Andrew Koenig]

"Gernot Frisch" <[e-mail] > wrote in message
news:39******** *****@individua l.net...

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
{
std::map<x,y>:: iterator next = it;
++next;
m.erase(it);
it=next;
}
else
++it;
}

You can simplify it:

for(std::map<x, y>::iterator it = m.begin(); it!=m.end(); )
{
if(...)
m.erase(it++);
else
++it;
}

This version hangs by the thinnest of threads, but it does still work.