CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 12 of 12
  1. #1
    Join Date
    Aug 2010
    Posts
    5

    multimap and multithreading

    Hi,

    Greatly appreciate your help;
    Imagine that I have a multimap. in a for loop I assign values to different elements of this multimap,
    But I know that each iteration assign value to a particular element in a way that is independent from other elements of that multimap.
    and that never during the loop we work on the same element twice.
    Do I have to still implement a locking mechanism if I want to do this loop in a multi-threaded fashion?
    I'm intending to do this using Open-MP but I guess that wouldn't make any difference in how the mechanics of it should work.

    Thanks

  2. #2
    Join Date
    Feb 2002
    Posts
    4,640

    Re: multimap and multithreading

    I would say yes. Theoretically, if you could be 100% sure that (a) the item(s) exist in the map, and (b) you'll never, ever, work on the same item at the same time in two different threads, then you probably don't need synchronization. However, the minute you add something new to the map, then you'll definitely need to synchronize! I would synchronize access just to be safe.

    Viggy

  3. #3
    Arjay's Avatar
    Arjay is offline Moderator / EX MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    13,490

    Re: multimap and multithreading

    You can also synchronize at two different levels: 1) syncronize the map for insertions/deletions. 2) Synchronize each object in the map.

    That way, individual objects can be modified with out impacting other objects and the map management operations are independent as well.

  4. #4
    Join Date
    Feb 2002
    Posts
    4,640

    Re: multimap and multithreading

    Quote Originally Posted by Arjay View Post
    You can also synchronize at two different levels: 1) syncronize the map for insertions/deletions. 2) Synchronize each object in the map.

    That way, individual objects can be modified with out impacting other objects and the map management operations are independent as well.
    Ahh, good point.

    Viggy

  5. #5
    Join Date
    Aug 2010
    Posts
    5

    Re: multimap and multithreading

    Thanks for the answers.

    Quote Originally Posted by MrViggy View Post
    However, the minute you add something new to the map, then you'll definitely need to synchronize!

    Viggy

    Why?

  6. #6
    Join Date
    Feb 2002
    Posts
    4,640

    Re: multimap and multithreading

    Adding members to a map invalidates all iterators. If you look up an item in one thread (getting an iterator), then context switch to another thread that adds to the map, the iterator in the first thread has just become invalid, and you'll never know it.

    Viggy
    Last edited by MrViggy; August 25th, 2010 at 04:20 PM.

  7. #7
    Join Date
    Aug 2010
    Posts
    5

    Re: multimap and multithreading

    for multimap I don't understand why inserting new element should invalidate iterators?
    Removing element could potentially invalidate iterators of multimap. But Not Insertion I would have thought.

  8. #8
    Join Date
    Feb 2002
    Posts
    4,640

    Re: multimap and multithreading

    Most maps (and multimaps) are implemented as red-black binary trees. Any insertion could force a re-balance of the tree. If that happens, any iterators you have may be referring to a different element (or no element at all) in the tree.

    Viggy

  9. #9
    Join Date
    Aug 2010
    Posts
    5

    Re: multimap and multithreading

    Right. Thank you very much, this was really helpful.

    Regards

  10. #10
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: multimap and multithreading

    Quote Originally Posted by MrViggy View Post
    Adding members to a map invalidates all iterators. If you look up an item in one thread (getting an iterator), then context switch to another thread that adds to the map, the iterator in the first thread has just become invalid, and you'll never know it.
    I don't think that's correct.
    From http://www.sgi.com/tech/stl/Multimap.html
    Multimap has the important property that inserting a new element into a multimap does not invalidate iterators that point to existing elements. Erasing an element from a multimap also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
    Remember, however, that C++03 does not consider multi-threading, so this doesn't mean that you don't need synchronization. I think you do, because it seems logical that an insertion and incrementing an iterator could cause a race condition.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  11. #11
    Join Date
    Nov 2003
    Posts
    1,902

  12. #12
    Join Date
    Aug 2010
    Posts
    5

    Re: multimap and multithreading

    OK, It seems that I need to use synchronization after all.
    I haven't looked into Docs, But Regarding Balanced tree and iterator invalidation; one can implement a Balanced tree and yet do not move the actual nodes around but only their pointers, so that iterators remain valid. and perhaps this is the way in which this is implemented.
    Thanks everyone for the replies.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured