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?

 

[Aslan Kral]

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

 

[Aslan Kral]

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

 

[Andre Kostur]

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]

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.


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]

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]

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]

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]

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.

 

[Gernot Frisch]

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

I do not understand what you mean. :?

 

[Gernot Frisch]

I do not understand what you mean. :?

I _do_ understand now, but I don't understand how it can be working
now

m.erase(it++); is the same as:
m_erase(it); it++;
right?
But after deleting at 'it', I can't '++' it anymore, can I? Does the
std say so?

 

[Kamil Burzynski]

m.erase(it++); is the same as:
m_erase(it); it++;
right?
But after deleting at 'it', I can't '++' it anymore, can I? Does the
std say so?

No, it is rather like this:

SomeIiterator tmp = it;
++it;
m.erase(tmp);

There is sequence point before erase() call, so it is already
incremented before call starts. Additionally, the erase() call gets old
(i.e. non-incremented) value as an argument.

 

[Andre Kostur]

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.

list has a resize?! Oh wait.. resize(), not reserve(). I think the OP was
more concerned as to whether list keeps "dead" nodes around (ie: if you
erase() an element from the list, does the capacity() (assuming list had a
capacity() member) remain constant, or does it go down by 1). No, list
doesn't keep dead nodes around. (Is that mandated by Standard, I'm not
sure).

 

[Gernot Frisch]

list has a resize?! Oh wait.. resize(), not reserve(). I think the
OP was
more concerned as to whether list keeps "dead" nodes around (ie: if
you
erase() an element from the list, does the capacity() (assuming list
had a
capacity() member) remain constant, or does it go down by 1). No,
list
doesn't keep dead nodes around. (Is that mandated by Standard, I'm
not
sure).

Actually my question was: will pointers to other elements stay when I
remove/insert an element. (vector won't, list will keep pointers
valid)
-Gernot

 

[Peter Gordon]

Actually my question was: will pointers to other elements stay when I
remove/insert an element. (vector won't, list will keep pointers
valid)
-Gernot

Are you sure? In the following code fragment:

list::iterator itr;
list mylist;
for(itr = mylist.begin(); itr != mylist.end(); ++itr) {
// delete the last elemant in the list
}

What happens to the "itr != mylist.end()" test?

BTW, I'm not being smart, I don't know, but suspect
that it is highly compiler dependent.

 

[Gernot Frisch]

Actually my question was: will pointers to other elements stay when

Are you sure? In the following code fragment:

list::iterator itr;
list mylist;
for(itr = mylist.begin(); itr != mylist.end(); ++itr) {
// delete the last element in the list
}

What happens to the "itr != mylist.end()" test?

BTW, I'm not being smart, I don't know, but suspect
that it is highly compiler dependent.

What I meant is:

X* pX = &mylist.first();
mylist.push_back(some_X); // Add some more data
mylist.erase(++mylist.begin() ); // Remove the 2nd item

pX -> DoSomething(); // valid if 'mylist' is std::list, propably
invalid it it's std::vector

-Gernot

 

[Andre Kostur]

Are you sure? In the following code fragment:

list::iterator itr;
list mylist;
for(itr = mylist.begin(); itr != mylist.end(); ++itr) {
// delete the last elemant in the list
}

What happens to the "itr != mylist.end()" test?

mylist.end() points to the one-past-the-end element. In this particular
case, it doesn't really matter since .end() is reevaluated every time you
go through the loop.

Nitpick, if you happen to be on the last element when you delete the last
element in the list, this loop will exhibit undefined behaviour since when
you delete the last element, the itr variable becomes an invalidated
iterator. Then you try to increment it, which is undefined behaviour.