By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,869 Members | 1,756 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,869 IT Pros & Developers. It's quick & easy.

std::map - erase+continue

P: n/a
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%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

Jul 23 '05 #1
Share this Question
Share on Google+
17 Replies


P: n/a

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

Jul 23 '05 #2

P: n/a

"Aslan Kral" <as**********@yahoo.com>, haber iletisinde şunları
yazdı:39*************@individual.net...

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}


Jul 23 '05 #3

P: n/a
"Aslan Kral" <as**********@yahoo.com> wrote in
news:39*************@individual.net:

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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.
Jul 23 '05 #4

P: n/a

"Andre Kostur" <nn******@kostur.net>, haber iletisinde şunları
yazdı:Xn*******************************@207.35.177 .134...
"Aslan Kral" <as**********@yahoo.com> wrote in
news:39*************@individual.net:

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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.
Jul 23 '05 #5

P: n/a
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;
}
Jul 23 '05 #6

P: n/a

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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.
Jul 23 '05 #7

P: n/a

"Aslan Kral" <as**********@yahoo.com> schrieb im Newsbeitrag
news:39*************@individual.net...

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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
Jul 23 '05 #8

P: n/a

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.net...

"Aslan Kral" <as**********@yahoo.com> schrieb im Newsbeitrag
news:39*************@individual.net...

"Gernot Frisch" <Me@Privacy.net>, haber iletisinde şunları
yazdı:39*************@individual.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.

Jul 23 '05 #9

P: n/a
"Gernot Frisch" <Me@Privacy.net> wrote in message
news:39*************@individual.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.
Jul 23 '05 #10

P: n/a
This version hangs by the thinnest of threads, but it does still
work.


I do not understand what you mean. :?
Jul 23 '05 #11

P: n/a

"Gernot Frisch" <Me@Privacy.net> schrieb im Newsbeitrag
news:39*************@individual.net...
This version hangs by the thinnest of threads, but it does still
work.


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?
Jul 23 '05 #12

P: n/a
On Tue, 8 Mar 2005 17:19:42 +0100
"Gernot Frisch" <Me@Privacy.net> wrote:
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.

--
Best regards from
Kamil Burzynski
Jul 23 '05 #13

P: n/a
> 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).
Jul 23 '05 #14

P: n/a

"Andre Kostur" <nn******@kostur.net> schrieb im Newsbeitrag
news:Xn*******************************@207.35.177. 135...
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).


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
Jul 23 '05 #15

P: n/a
"Gernot Frisch" <Me@Privacy.net> wrote in news:397qcfF5uq1i4U1
@individual.net:
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.

Jul 23 '05 #16

P: n/a
>> 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 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
Jul 23 '05 #17

P: n/a
Peter Gordon <petergo@_deleteme_.netspace.net.au> wrote in
news:Xn**********************************@203.10.1 10.105:
"Gernot Frisch" <Me@Privacy.net> wrote in news:397qcfF5uq1i4U1
@individual.net:
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?


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.

Jul 23 '05 #18

This discussion thread is closed

Replies have been disabled for this discussion.