erase elements while iterating on a map

[jose luis fernandez diaz]

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.

 

[John Harrison]

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

 

[John Harrison]

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

 

[Derek]

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.