CODEWITHSUNDEEP
c++data-structuresstlthread-safety
Tarek
Tarek

Reputation: 1090

Which STL container has a thread-safe insertion process?

Which STL container has a thread safe insertion process? I want several threads to simultaneously insert in the same container. Any implementation other than STL (i.e., Boost) is welcome!

Upvotes: 6

Views: 5066

Answers (6)

James Moore
James Moore

Reputation: 9026

Take a look at Boost.Lockfree (http://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html). It provides threadsafe implementations of:

boost::lockfree::queue
  a lock-free multi-produced/multi-consumer queue
boost::lockfree::stack
  a lock-free multi-produced/multi-consumer stack
boost::lockfree::spsc_queue
  a wait-free single-producer/single-consumer queue (commonly known as ringbuffer)

Upvotes: 2

Chad
Chad

Reputation: 19032

Since you said any other (non-STL) implementation is welcome, I suggest Intel's Thread Building Blocks. They have thread safe concurrent containers that have really good performance characteristics.

Upvotes: 1

Max Lybbert
Max Lybbert

Reputation: 20039

The Standard does not require any STL containers to be thread safe. An implementation could be thread safe, although I'm not sure how they could pull it off with the current API; and changing the API would make them no longer compatible with the Standard.

If the LGPL is acceptable, Intel TBB has thread safe containers (these containers use locks internally, which does affect their performance).

Upvotes: 3

Hans Passant
Hans Passant

Reputation: 941545

I am trying to avoid the critical region in multi-threading because it deteriorates the performance !

On the contrary, it improves performance. Because the kind of locking a container class can do is only the very fine-grained kind, having to acquire the lock for each simple operation. That's expensive. When you take care of locking, you have the luxury of acquiring the lock and perform many operations. That does not improve the odds for concurrency but greatly reduces the locking overhead. You can choose the strategy that makes most sense for your app, it isn't forced on you.

Add to this that it is next to impossible to write a thread-safe container implementation that isn't either prone to deadlock or very expensive. Iterators are the problem. The library writer has to choose between taking a lock for the life time of the iterator (risking deadlock) or needs to update all live iterators when another thread changes the collection (expensive). Only the expensive choice is safe. Again, you choose the strategy that makes most sense, the expensive choice is not forced on you.

Upvotes: 6

Dialecticus
Dialecticus

Reputation: 16761

Containers follow KISS principle (Keep It Simple) and therefore do not have synchronization features. Most of the time this hypothetical embedded synchronization is not enough because most of the time access to some other objects must be synchronized with the access to the container. Combine your container with one lock, and that's it really.

Upvotes: 1

David Heffernan
David Heffernan

Reputation: 612993

The STL containers are not thread safe. You have to impose that yourself, should you so wish, with your own synchronisation.

Upvotes: 6

Related Questions