std::map iteration safety

Discussion in 'C++' started by neilsolent, Dec 16, 2008.

  1. neilsolent

    neilsolent Guest

    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
     
    neilsolent, Dec 16, 2008
    #1
    1. Advertising

  2. neilsolent

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Dec 16, 2008
    #2
    1. Advertising

  3. neilsolent

    neilsolent Guest

    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.
     
    neilsolent, Dec 17, 2008
    #3
  4. neilsolent

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Dec 17, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,397
    Ivan Vecerina
    Mar 17, 2005
  2. digz
    Replies:
    2
    Views:
    2,136
  3. Replies:
    1
    Views:
    443
    red floyd
    Dec 21, 2008
  4. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,039
    James Kanze
    Dec 22, 2008
  5. James Kanze
    Replies:
    0
    Views:
    2,050
    James Kanze
    Dec 21, 2008
Loading...

Share This Page