[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

std::map iteration safety

neilsolent

12/16/2008 8:41:00 PM

Hi

Is it valid to iterate over a std::map like this:

//////////////

map<string, msg*>::iterator it;

for (it = m_myMap.begin(); it != m_myMap.end(); it++)
(*it).second->Check();

////////////////

... where the function Check() may add or remove elements from m_myMap.

I am worried that this may cause a crash. Should I make a copy of
m_myMap first ?

thanks
Neil
3 Answers

Kai-Uwe Bux

12/16/2008 10:26:00 PM

0

neilsolent wrote:
> Is it valid to iterate over a std::map like this:
>
> //////////////
>
> map<string, msg*>::iterator it;
>
> for (it = m_myMap.begin(); it != m_myMap.end(); it++)
> (*it).second->Check();
>
> ////////////////
>
> .. where the function Check() may add or remove elements from m_myMap.
>
> I am worried that this may cause a crash. Should I make a copy of m_myMap
> first ?

Your program will have undefined behavior when and only when Check() removes
the item that the iterator it identifies. This is a consequence of std::map
being an associative container: erase only invalidates iterators pointing
to the removed element.

When Check() inserts items, those whose key are behind it->first will be
visited in the loop, those inserted before won't. Whether that is what you
want, I cannot say.


Best

Kai-Uwe Bux

neilsolent

12/17/2008 8:05:00 AM

0

Hi Kai-Uwe

Thanks for the reply.

> Your program will have undefined behavior when and only when Check() removes
> the item that the iterator it identifies. This is a consequence of std::map
> being an associative container: erase only invalidates iterators pointing
> to the removed element.

If the item that "it" points at is removed - the loop next runs "it++"
- I guess that's where the problem is?
I will check my code to see if the current item can ever get deleted
by Check(), and if so find another way.

> When Check() inserts items, those whose key are behind it->first will be
> visited in the loop, those inserted before won't. Whether that is what you
> want, I cannot say.

That behaviour is fine for my app, and I expected as much.

Kai-Uwe Bux

12/17/2008 9:00:00 AM

0

neilsolent wrote:

> Hi Kai-Uwe
>
> Thanks for the reply.
>
>> Your program will have undefined behavior when and only when Check()
>> removes the item that the iterator it identifies. This is a consequence
>> of std::map being an associative container: erase only invalidates
>> iterators pointing to the removed element.
>
> If the item that "it" points at is removed - the loop next runs "it++"
> - I guess that's where the problem is?

Yes.

More generally, any operation involving an invalid iterator yields undefined
behavior. That goes for dereferencing as well. Thus, if you increment the
iterator before the call to Check(), you just might get the same problem in
the next iteration (if Check() happens to remove the item behind the
current one).


Best

Kai-Uwe Bux