std::map and multithreaded access

Discussion in 'C++' started by Dilip, Sep 5, 2006.

  1. Dilip

    Dilip Guest

    Hi Folks

    I know the C++ standard doesn't talk about threads. However I am a
    little bit curious as to what might or might not happen with a
    particular scenario I encountered in my project. Its w.r.t to STL
    containers so I didn't know where else to post. insights appreciated:

    my application iterates over a stl::map to do some processing on its
    elements:

    typedef std::map<std::string, SomeComplexStructure* scs> str2structMap;
    str2structMap themap;

    str2structMap::const_iterator itr;
    str2structMap::const_iterator itrbegin = themap.begin();
    str2structMap::const_iterator itrend = themap.end();
    //DebugBreak();
    for (itr = itrbegin; itr != itrend; ++itr)
    {
    // At this point if another thread elsewhere adds a new element to
    'themap', does this
    // iteration get affected?
    }

    Pls note that I am *only* bothered about the case where a new element
    is INSERTED.
    I have already handled cases where elements could be deleted or
    modified while the iteration is happening.
    Dilip, Sep 5, 2006
    #1
    1. Advertising

  2. Dilip

    Pete Becker Guest

    Dilip wrote:
    >
    > my application iterates over a stl::map to do some processing on its
    > elements:
    >
    > typedef std::map<std::string, SomeComplexStructure* scs> str2structMap;
    > str2structMap themap;
    >
    > str2structMap::const_iterator itr;
    > str2structMap::const_iterator itrbegin = themap.begin();
    > str2structMap::const_iterator itrend = themap.end();
    > //DebugBreak();
    > for (itr = itrbegin; itr != itrend; ++itr)
    > {
    > // At this point if another thread elsewhere adds a new element to
    > 'themap', does this
    > // iteration get affected?
    > }
    >
    > Pls note that I am *only* bothered about the case where a new element
    > is INSERTED.
    > I have already handled cases where elements could be deleted or
    > modified while the iteration is happening.
    >


    ++itr gets to the next element by following pointers in the map's nodes.
    Inserting or removing an element modifies pointers in the map's nodes.
    That's a classic data race.

    In general, you can safely read from the same container in multiple
    threads, but when you modify it (either by adding or removing elements)
    you must exclude all readers and all other modifiers. For more details,
    see Appendix C in my book, "The Standard C++ Library Extensions: a
    Tutorial and Reference."

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and Reference."
    For more information about this book, see www.petebecker.com/tr1book.
    Pete Becker, Sep 5, 2006
    #2
    1. Advertising

  3. Dilip wrote:
    > I know the C++ standard doesn't talk about threads. However I am a
    > little bit curious as to what might or might not happen with a
    > particular scenario I encountered in my project. Its w.r.t to STL
    > containers so I didn't know where else to post. insights appreciated:
    >
    > my application iterates over a stl::map to do some processing on its
    > elements:
    >
    > typedef std::map<std::string, SomeComplexStructure* scs>
    > str2structMap; str2structMap themap;
    >
    > str2structMap::const_iterator itr;
    > str2structMap::const_iterator itrbegin = themap.begin();
    > str2structMap::const_iterator itrend = themap.end();
    > //DebugBreak();
    > for (itr = itrbegin; itr != itrend; ++itr)
    > {
    > // At this point if another thread elsewhere adds a new element to
    > 'themap', does this
    > // iteration get affected?
    > }
    >
    > Pls note that I am *only* bothered about the case where a new element
    > is INSERTED.
    > I have already handled cases where elements could be deleted or
    > modified while the iteration is happening.


    Threading shouldn't play any role here. The same problem would exist
    (or not) when during your iteration you call some function which would,
    having access to 'themap', add an element to it. The Standard is quite
    clear - no [existing] iterators or references are affected by an insert
    operation.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 5, 2006
    #3
  4. Dilip

    Pete Becker Guest

    Victor Bazarov wrote:
    >
    > Threading shouldn't play any role here. The same problem would exist
    > (or not) when during your iteration you call some function which would,
    > having access to 'themap', add an element to it. The Standard is quite
    > clear - no [existing] iterators or references are affected by an insert
    > operation.
    >


    The validity of the iterator isn't affected by inserts, but the details
    of the map's structure do change. If the insert happens to change the
    contents of a pointer at the same time that an iterator increment is
    reading that pointer the value that the increment sees may be corrupted.
    In addition, if there are multiple pointer modifications needed to
    insert an element (usually to rebalance the tree), adjusting an iterator
    at the same time could lead to seeing inconsistent pointer values, with
    disastrous results.

    The map and its iterators all guarantee that their invariants are true
    when you're outside of any member functions. Accessing the same data
    structure from multiple threads means that you may end up accessing its
    internals while another member function is running. In that case, the
    invariants may not hold, and all bets are off.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and Reference."
    For more information about this book, see www.petebecker.com/tr1book.
    Pete Becker, Sep 5, 2006
    #4
  5. Pete Becker wrote:
    > Victor Bazarov wrote:
    >>
    >> Threading shouldn't play any role here. The same problem would exist
    >> (or not) when during your iteration you call some function which
    >> would, having access to 'themap', add an element to it. The
    >> Standard is quite clear - no [existing] iterators or references are
    >> affected by an insert operation.
    >>

    >
    > The validity of the iterator isn't affected by inserts, but the
    > details of the map's structure do change. If the insert happens to
    > change the contents of a pointer at the same time [...]


    But this cannot happen in a C++ program. There is no "same time", at
    least according to C++ Standard, is there?

    Threading, data access, race conditions, have nothing to do with any of
    C++ containers, just like iterator invalidation due to insertions to the
    container have nothing to do with threading. Those are *orthogonal*
    problems, and the task of the programmer is to tackle them both. At the
    same time, so to speak. :)

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 5, 2006
    #5
  6. Dilip

    Pete Becker Guest

    Victor Bazarov wrote:
    > Pete Becker wrote:
    >
    >>
    >>The validity of the iterator isn't affected by inserts, but the
    >>details of the map's structure do change. If the insert happens to
    >>change the contents of a pointer at the same time [...]

    >
    >
    > But this cannot happen in a C++ program. There is no "same time", at
    > least according to C++ Standard, is there?
    >
    > Threading, data access, race conditions, have nothing to do with any of
    > C++ containers, just like iterator invalidation due to insertions to the
    > container have nothing to do with threading. Those are *orthogonal*
    > problems, and the task of the programmer is to tackle them both. At the
    > same time, so to speak. :)
    >


    The original question was about doing this in a multi-threaded program.
    It can, and does, happen in C++ programs. Just not in well-formed
    programs under the current standard. But the well-formedness of these
    programs will change with the next version of the standard.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and Reference."
    For more information about this book, see www.petebecker.com/tr1book.
    Pete Becker, Sep 5, 2006
    #6
    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. Dilip
    Replies:
    20
    Views:
    919
    Pete Becker
    Jun 15, 2006
  2. Christopher Pisz
    Replies:
    10
    Views:
    1,508
    CodeCracker
    Jan 29, 2008
  3. Replies:
    1
    Views:
    420
    red floyd
    Dec 21, 2008
  4. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,020
    James Kanze
    Dec 22, 2008
  5. James Kanze
    Replies:
    0
    Views:
    1,999
    James Kanze
    Dec 21, 2008
Loading...

Share This Page