std::map and multithreaded access

[Dilip]

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.

 

[Pete Becker]

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.

 

[Victor Bazarov]

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

 

[Pete Becker]

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.

 

[Victor Bazarov]

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

 

[Pete Becker]

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.