Read safety of std::map / std::unordered_map

Question

I have a std::map (or std::unordered_map, as I assume they behave similarly) that I read and write to. I also have an associated mutex.

I will be both reading and writing (by inserting or deleting elements) to the map. I heard that STL containers were read-safe. If so, it is safe to only use the mutex for write operations?

I'm asking because I need to iterate over the values of the map at one point, and I'd like to only use my mutex when an element requires modification.

Answer 1

it is safe to only use the mutex for write operations?

You need to ensure you don't try to read from the map while it is being written to. So you don't need to lock a mutex while only reads are happening, but if any thread could be writing then all threads (even readers) need to use the mutex.

Answer 2

In general, no. Both reader and writer have to acquire the mutex.

Otherwise, you risk data races when there are concurrent reads and writes, which results in undefined behavior. In practice, the can resulting in crashes, or readers could get corrupted data which you have never put into the map. Even, if it seems to work, it confuses useful tools like race detectors (e.g., thread sanitizer, Helgrind). It also makes your code potentially non-portable.

Only if you can prove that there are no more writer to the map, and the changes are visible to all other threads, the situation has changed as now all accesses are readers. At this point, there cannot be any data races and it is safe to read from the map without any synchronization.

If there is still the possiblity of updates, you can use parallel data structures to avoid locks. C++11 (and C++17) do not provide one, but there are non-standard implementations available.

So, if you really need the performance, you can have a look at these concurrent hash map implementations (otherwise just use std::unordered_map in combination with a mutex for all accesses):

• Concurrent data structures in Intel Threading Building Blocks (TBB)
  • concurrent_unordered_map (similar to std::unorder_map, but does not support concurrent delete operations)
  • concurrent_hash_map (also supports delete operations, but the interface is different as it uses accessor objects)
• Junction (seems to be the fastest, but requires the threads to periodically call a cleanup operation when it is not using the map. This is done to reclaim memory without having to use a garbage collector, as described in "Safe Memory Reclamation" in the introducing blog post.)