Can a reference to an element inside an std::map be invalidated?

user_5470144 0
Viewed 1818

I have a multi-threaded application and a shared resource std::map<KeyType, ElementType>. I use a mutex to protect inserts, gets and removes.

My get method returns a reference to the stored element (unlocks on return), and then I do some work with that element.

Question: Is it possible that while working with the stored element reference, another thread may change the std::map so the element will be moved to a different address and the reference will no longer be valid? (I know there are certain ADT implementations which do rearrangement of the ADT on resize).

std c++11 multithreading c++
2 Answers

The iterator invalidation rule for associative containers (which std::map is) says at [associative.reqmts]/9:

The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

So if one thread inserts an element, it won't affect any references to existing elements. But if it removes something, other threads may be borked. Some form of element-wise locking is in order, I'd say.

user_8176430

Another thread may erase the element, or destroy the map, which would of course also invalidate the element.

Erasing an element only invalidates iterators and refewrences to this element. Insertion does not invalidate iterators or references into the map.

(that's what the second-hand documentation says, at least - and it's an assumption I hold that never was invalidated, if anecdotal evidence counts.)

Another problem remains: Manipulation of the element through the returned reference is not thread safe. You need to sync e.g. per element - and make sure you don't violate lock hierarchy.

peterchen_313170
Related