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

erase elements while iterating on a map

P: n/a
Hi,

Erase elements while iterating on a map don't invalidate the iterator
except the erased one, so the program below:

(1)

#include <map>

int main()
{
map<int, int> m1;

m1[1]=1;
m1[2]=2;
m1[3]=3;
m1[4]=4;
m1[5]=5;
map<int,int>::iterator it;
srandom(time(0));

for (it=m1.begin(); it!= m1.end();it++)
{
if (random()%2)
{
m1.erase(it->first);
}
}

return 0;
}
would be:

(2)

.. . .

for (it=m1.begin(); it!= m1.end();)
{
int erase_element = it->first;
++it;
if (random()%2)
{
m1.erase(erase_element);
}
}

.. . .

I think that the first program (1) is more intuitive and elegant that
the second (2).

Why the first program is not valid ?
Thanks,
Jose Luis.
Jul 22 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a

"jose luis fernandez diaz" <jo**********************@yahoo.es> wrote in
message news:c2**************************@posting.google.c om...
Hi,

Erase elements while iterating on a map don't invalidate the iterator
except the erased one, so the program below:

(1)

#include <map>

int main()
{
map<int, int> m1;

m1[1]=1;
m1[2]=2;
m1[3]=3;
m1[4]=4;
m1[5]=5;
map<int,int>::iterator it;
srandom(time(0));

for (it=m1.begin(); it!= m1.end();it++)
{
if (random()%2)
{
m1.erase(it->first);
}
}

return 0;
}
would be:

(2)

. . .

for (it=m1.begin(); it!= m1.end();)
{
int erase_element = it->first;
++it;
if (random()%2)
{
m1.erase(erase_element);
}
}

. . .

I think that the first program (1) is more intuitive and elegant that
the second (2).

Why the first program is not valid ?


Because you've invalidated the iterator by deleting the element it refers
to.

The second program is not only inelegant it a good deal less efficient that
the first, because you have to search through the map to find the element to
delete.

Here's how you should do it

for (it=m1.begin(); it!= m1.end();)
{
++it;
if (random()%2)
{
m1.erase(it++);
}
else
{
++it;
}
}

john
Jul 22 '05 #2

P: n/a
Typo

Here's how you should do it

for (it=m1.begin(); it!= m1.end();)
{
++it;
remove the above line
if (random()%2)
{
m1.erase(it++);
}
else
{
++it;
}
}

john


Apologies, John

Jul 22 '05 #3

P: n/a
> Erase elements while iterating on a map don't invalidate
the iterator except the erased one, so the program below:

(1)

#include <map>

int main()
{
map<int, int> m1;

m1[1]=1;
m1[2]=2;
m1[3]=3;
m1[4]=4;
m1[5]=5;

map<int,int>::iterator it;
srandom(time(0));

for (it=m1.begin(); it!= m1.end();it++)
{
if (random()%2)
{
m1.erase(it->first);
You just invalidated your iterator by calling erase(), so
when it++ is called, it increments an invalid iterator.
}
}

return 0;
}

would be:

(2)

. . .

for (it=m1.begin(); it!= m1.end();)
{
int erase_element = it->first;
++it;
if (random()%2)
{
m1.erase(erase_element);
}
}

. . .

I think that the first program (1) is more intuitive and
elegant that the second (2).

Why the first program is not valid?


See comments above.

Also note you should pass an iterator to erase(), not the
key. You know exactly which element you want to erase, so
there is no need to make erase() look it up from the key:

for (it=m1.begin(); it!= m1.end();)
{
map<int,int>::iterator erase_element = it++;

if (random()%2)
{
m1.erase(erase_element);
}
}

I prefer this version to John's because "it" is only
incremented once. I prefer not to do the same thing in
two places when one will suffice.
Jul 22 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.