How to sort TBB concurrent_vector or concurrent_queue?

Question

Now I have a solver in that I need to keep a set of self-defined data type objects in a concurrent_vector or queue. It has to be concurrent because the objects come from different threads.With this concurrent container, I hope to sort these objects, eliminate duplicates and send them back when other threads need them.

However, I know TBB offers concurrent_vector and concurrent_queue which can be read and written concurrently from different threads. But how to sort the objects inside a container? Does everyone know how to do that? Thanks.

Answer 1

I guess the producer threads should run concurrently with the consumer threads. So if the elements would not need to be sorted and made unique a simple concurrent_queue would suffice.

If you only need to make them unique, you could use a tbb::concurrent_hash_map for that.

However, if you really want to have the elements sorted, you need something like a concurrent_set (ordered) which is rather complicated and does not exist in tbb. So if you really need to have those elements sorted, i would propose to use a simple lock which must be aquired for putting elements to your container (e.g. std::set) and for retrieving them out of it.

Answer 2

I think you have some misunderstanding of TBB concurrent container. You can refer to TBB wiki

Do TBB concurrent containers use OS synchronization objects?

• No, they don’t. TBB concurrent containers utilize TBB user-level synchronization primitives and atomic operations.

Is it thread-safe to access and modify elements of tbb::concurrent_vector without locking?

• No, you have to use locks explicitly.

Therefore, concurrent_vector does not support thread-safe multi-thread read and write. I hope this help.

Answer 3

concurrent_vector works with std::sort and both tbb & ppl (in the sample pack) offer parallel sorts that can be used with this. A parallel version of std::unique would be even more useful for removing dupes, but you'd have to build your own.