Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > std::map and multithreaded access

Reply
Thread Tools

std::map and multithreaded access

 
 
Dilip
Guest
Posts: n/a
 
      09-05-2006

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.

 
Reply With Quote
 
 
 
 
Pete Becker
Guest
Posts: n/a
 
      09-05-2006
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.
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      09-05-2006
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


 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      09-05-2006
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.
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      09-05-2006
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


 
Reply With Quote
 
Pete Becker
Guest
Posts: n/a
 
      09-05-2006
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
std::map multithreaded access, lock needed? Christopher Pisz C++ 10 01-29-2008 09:49 AM
multithreaded file access Matias Surdi Ruby 12 12-28-2005 01:50 PM
CSharpCorner Just Published My Article : Multithreaded XML Documentfor Read/Write Access Praxis Happenstance ASP .Net Web Services 4 07-23-2004 03:25 PM
Re: Sessions variable access in multithreaded asp.net Natty Gur ASP .Net 3 08-05-2003 12:55 PM
Re: Sessions variable access in multithreaded asp.net David Browne ASP .Net 1 07-29-2003 03:59 AM



Advertisments