Is the C++ std::set thread-safe?

Question

I've a question about the thread safety of std::set.

As far as I know I can iterate over a set and add/erase members and that doesn't invalidate the iterators.

But consider following scenario:

• thread 'A' iterates over a set of shared_ptr<Type>
• thread 'B' occasionally adds items to this set.

I've experienced segfaults as the program runs and I'm not sure why this happens. Is lack of thread safety the cause?

Solution 1

STL has no built in thread support, so you'll have to extend the STL code with your own synchronization mechanisms to use STL in a multithreaded environment.

For example look here: link text

Since set is a container class MSDN has following to say about the thread safety of the containers.

A single object is thread safe for reading from multiple threads. For example, given an object A, it is safe to read A from thread 1 and from thread 2 simultaneously.

If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected. For example, given an object A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

It is safe to read and write to one instance of a type even if another thread is reading or writing to a different instance of the same type. For example, given objects A and B of the same type, it is safe if A is being written in thread 1 and B is being read in thread 2.

Solution 2

The Dinkumware STL-Documentation contains the follwing paragraph about that topic. Its probably (as indicated in the text) valid for most implementations.

For the container objects defined in the Standard C++ Library, such as STL Containers and objects of template class basic_string, this implementation follows the widely adopted practices spelled out for SGI STL:

Multiple threads can safely read the same container object. (There are nunprotected mutable subobjects within a container object.)

Two threads can safely manipulate different container objects of the same type. (There are no unprotected shared static objects within a container type.)

You must protect against simultaneous access to a container object if at least one thread is modifying the object. (The obvious synchronization primitives, such as those in the Dinkum Threads Library, will not be subverted by the container object.)

Thus, no attempt is made to ensure that atomic operations on container objects are thread safe; but it is easy enough to make shared container objects that are thread safe at the appropriate level of granularity.

Solution 3

None of the STL containers is thread safe, so std::set in particular isn’t.

In your case, the issue isn’t even really thread safety, though: You simply share an object across multiple threads (fine) and modify it in one thread (fine as well). But as you’ve already said, modifying the container invalidates its iterators. Whether this happens in the same thread or in a different thread is of no consequence since it’s still the same container.

D'oh! §23.1.2.8 states that inserting doesn’t invalidate iterators.

Solution 4

Performing an insertion can cause the vector to reallocate its underlying memory while iterator may still point to the previous (but invalid) memory address, leading to segment fault.

Solution 5

Simple explanation: If thread A is moving iterators through the container, it's looking at container internals. If thread B modifies the container (even an operation that doesn't invalidate the iterator that A has), thread A can run into trouble because B is fooling with the container internals, possibly having them in a (temporarily) invalid state. This causes crashes in thread A.

The problem ISN'T the iterators themselves. It when they need the container's data structures in order to find the position that you get into trouble.

Simple as that.

View more solutions

Comments

[suszterpatt]

Actually, the standard states that adding to or deleting from an std::set doesn't invalidate any of its iterators (with iterators pointing to an object to be deleted being the obvious exception).

[Konrad Rudolph]

Thanks for the comment, I completely botched that. Although I’ve got to say, from an implementer’s point of view this is a really strange requirement.

[Kieveli]

Actually, you'll find it easier to create a thread safe class that contains an std::set rather than extending the set itself. WAY less work.

[Kieveli]

... Even if the iteraters weren't invalidated, I wouldn't trust the insertions and deletions to leave the set in a usable state when being used by two threads.

[Konrad Rudolph]

@Kieveli: that’s the whole point of the question, isn’t it? Why isn’t it in a stable state? Does the compiler see that no iterator exists to the container (on the current thread) and optimizes accordingly? If so, kudos. That is some serious control flow analysis.

[suszterpatt]

Doesn't seem so strange to me: sets and maps are (typically) implemented with linked trees, and iterators with pointers. Inserting and removing only changes the local "neighborhood" (in a logical sense) of the element in question, and even then there's no need to reallocate any of the other nodes: thus, iterators pointing to them remain valid without any extra effort.

[suszterpatt]

@Konrad: 23.1.2.8 only applies to set, map, multiset and multimap. TR1 specifies its own rules in terms of insertion/deletion and iterator validity with respect to unordered_* (§6.3.1.12-13 in the version I'm looking at). These requirements are indeed weaker than those for the ordered counterparts.

[Konrad Rudolph]

@suszterpatt: Thanks for looking that up. Good to know they use other requirements there, then.

[David Rodríguez - dribeas]

@Kieveli +1, but you must be careful not to provide backdoors into the set (returning set iterators) and that can imply having to write your own set of iterators on top of the set iterators so that the increments/decrements are thread safe. Neither implementing a thread safe set nor a wrapper are simple tasks...

[Martin York]

@suszterpatt. Inserting may not invalidate the iterators. But if thread A is half way through an insert is the internal state of the set valid (it will be valid when the insert is complete, but there is no requirement to be valid at any other point). Now if you increment a valid iterator in a seprate thread does that iterator interact with the set? If so then the outcome is probably undefined.

[Johannes Gerer]

Can you provide the link to the MSDN citation? NEVERMIND: msdn.microsoft.com/en-us/library/c9ceah3b(v=VS.100).aspx