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

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

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.

Quote:

---

Originally Posted by Arjay

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

Thanks for the answers.

Quote:

---

Originally Posted by MrViggy

However, the minute you add something new to the map, then you'll definitely need to synchronize!

Viggy

---

Why?

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

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.

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

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

Regards

Quote:

---

Originally Posted by MrViggy

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

Quote:

---

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.

You need to read the documentation from your STL provider:
http://msdn.microsoft.com/en-us/library/c9ceah3b.aspx
http://www.stlport.org/doc/sgi_stl.html#thread_safety
http://www.sgi.com/tech/stl/thread_safety.html
http://developers.sun.com/solaris/articles/stl-new.html
http://www.dinkumware.com/manuals/?m...ad_safety.html

gg

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.