tags:

views:

2241

answers:

6

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?

+8  A: 

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.

Konrad Rudolph
updating a set doesn't invalidates the iterators.....
Racer
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).
suszterpatt
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.
Konrad Rudolph
... 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.
Kieveli
@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.
Konrad Rudolph
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
@suszterpatt: But there are other implementations of such data structures, most notably hash tables (`std::unordered_set`). Changing the iterator requirement for these would be extremely strange because the interface is otherwise the same (minus the order of the elements, of course). On the other hand, keeping the iterators valid for hash tables after insertion/deletion can be *extremely* expensive.
Konrad Rudolph
@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.
suszterpatt
@suszterpatt: Thanks for looking that up. Good to know they use other requirements there, then.
Konrad Rudolph
@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.
Martin York
+12  A: 

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.

Vaibhav
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
@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...
David Rodríguez - dribeas
+6  A: 

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.

RED SOFT ADAIR
+1  A: 

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.

Michael Kohne
A: 

Yes. One way to handle this situation is to have each thread lock a shared mutex before accessing the same set object. Make sure you use RAII techniques to lock and unlock the mutex.

Brian Neal
+2  A: 

There is a good discussion about this on Scott Meyer's Effective STL.

dudewat