How to sort TBB concurrent_vector or concurrent_queue?

[Jakcie_Jin]

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.

[Dmitry_Vyukov]

It's impossible to sort items in presence of continuous additions.

[RafSchietekat]

It's all a matter of whether you want the scalability or the functionality, because, as Dmitriy indicates (if I interpreted correctly what he wrote), you can't have both, and the concurrent containers in TBB are about performance and scalability, ruthlessly sacrificing frivolous functionality that would stand in the way of that goal.

How about using the heap operations of C++, with appropriate use of locks of course?

[Jakcie_Jin]

How about at a time, I copy the contents of concurrent vector to a STL contanier and sort the copy? It is kind of troublesome but it may be possible.

In addition, what is the heap operations of C++?

[Anton_M_Intel]

You can sort concurrent_vector if there is no concurrent accesses (in general, though some might be possible with some restrictions). Another alternative may be concurrent_unordered_map which uses split-ordered-list algorithm, i.e. the list of items is always sorted by a bit-reversed hash value. So if you can zip your key into size_t, you may make use of it.

[Dmitry_Vyukov]

Quoting Anton Malakhov (Intel)

Another alternative may be concurrent_unordered_map which uses split-ordered-list algorithm

Is it that recursive split ordering with the second name "trash your cache" (consecutive nodes scattered as far as possible from each other)?.. Oh, never mind.

[alex_s_14]

I can't understand if I can use tbb:parallel_sort with tbb concurrent vector? 

tbb::concurrent_vector<int> tbb_vec;
// ...fill tbb_vec
// sort
tbb::parallel_sort(tbb_vec.begin(), tbb_vec.end());

[Alexei_K_Intel]

Hi Alex,

alex s. wrote:

I can't understand if I can use tbb:parallel_sort with tbb concurrent vector? 

tbb::concurrent_vector<int> tbb_vec;
// ...fill tbb_vec
// sort
tbb::parallel_sort(tbb_vec.begin(), tbb_vec.end());

I suppose it should work. Have you tried it? Have you faced some issues?

Regards, Alex