Std::Map Thread-Safety

std::map thread-safety

The C++11 standard guarantees that const method access to containers is safe from different threads (ie, both use const methods).

In addition, [container.requirements.dataraces] states

implementations are required to avoid data races when the contents of
the contained object in different elements in the same sequence,
excepting vector<bool>

In other words, except for vector<bool> modifying distinct contents is not a data race.

Now, if one thread invalidates an iterator used by another thread, clearly this is a data race (and results in undefined behavior). If one thread does non-const access to a container, and another does const access, that is a data race (and undefined behavior). (Note: a number of functions are "considered const" for the purpose of multithreading, including begin, end and other functions (and methods) that are non-const simply because they return non-const iterators. [] is included in this set of pseudo-const for thread safety reasons, except for map and unordered_set etc -- 23.2.2.1).

However, it appears that if you have a reference to an element within the container, and engage in operations that do not invalidate that reference in another thread, and never write to that element in another thread, you can safely read from that reference. Similarly, if other threads never even read from the element, then writing to that element shouldn't result in undefined behavior.

For standards references, 17.6.5.9.5 seems to guarantee that functions from the standard library won't run away and read/write elements needlessly.

So the short answer: you are safe, so long as the other thread doesn't directly mess with that particular entry in the map.

What operations are thread-safe on std::map?

In theory no STL containers are threadsafe. In practice reading is safe if the container is not being concurrently modified. ie the standard makes no specifications about threads. The next version of the standard will and IIUC it will then guarantee safe readonly behaviour.

If you are really concerned, use a sorted array with binary search.

Thread-safety about `std::mapint, std::atomicT` under a special condition

Yes, this is safe.

Data races are best thought of as unsynchronized conflicting access (potential concurrent reads and writes).

std::thread construction imposes an order: the actions which preceded in code are guaranteed to come before the thread starts. So the map is completely populated before the concurrent accesses.

The library says standard types can only access the type itself, the function arguments, and the required properties of any container elements. std::map::find is non-const, but the standard requires that for the purposes of data races, it is treated as const. Operations on iterators are required to at most access (but not modify) the container. So the concurrent accesses to std::map are all non-modifying.

That leaves the load and store from the std::atomic<bool> which is race-free as well.

std::map thread-safety and iterator invalidation

You're right to be suspicious. You can't call myMap[k] and myMap.find(x) from different threads at the same time.

With containers, you can safely do one of the following at a time:

Call const member functions from any number of threads concurrently, or
Call a non-const member function from exactly one thread.

Since operator[] is not const, you have to guard it with a mutex or otherwise ensure that you're not calling any other member functions at the same time.

thread safety in std::map

It is safe as long as none of the threads are modifying the map. It is also safe if threads are modifying different elements of the map (provided the elements themselves don't cause race conditions by, for example, modifying some global state):

In 17.6.5.9 Data race avoidance, the standard library guarantees that concurrent const access to containers is safe (at least as far s the containers go. If the elements allow mutation via const access there could be data races at the element level.)

In 23.2.2 Container data races further guarantees are made: non-const concurrent access is safe if the modifications/reads are to different elements of the container¹.

As soon as you have one thread making modifications to the container or to the same element in the container while others read or write, you are open to race conditions and undefined behaviour.

^{1 With the exception of std::vector<bool>}

C++ thread safety - map reading

If you are talking about the standard std::map^† and no thread writes to it, no synchronization is required. Concurrent reads without writes are fine.

If however at least one thread performs writes on the map, you will indeed need some sort of protection like a mutex.

Be aware that std::map::operator[] counts as write, so use std::map::at (or std::map::find if the key may not exist in the map) instead. You can make the compiler protect you from accidental writes by only referring to the shared map via const map&.

^†Was clarified to be the case in the OP. For completeness' sake: Note that other classes may have mutable members. For those, even access through const& may introduce a race. If in doubt, check the documentation or use something else for parallel programming.

Thread safety of fixed sized stl map

No, you do not need to add extra synchronization to make this use of std::map thread-safe. You are only modifying the map nodes during initialization, and after that you are only reading the map. Concurrent reading of the map is no problem, because its structure does not change.

The fact that you are modifying the values in the map does not matter, because they don't contribute to the ordering and structure of the map.