c++ - 无锁容器如何对并发分区和排序使用react？

Question

如何通过并发容器(例如 boost 或 tbb 实现)处理同时从 2 个不同线程执行的分区和排序等两种标准算法？

Answer 1

Boost 有无锁队列和堆栈。不对这些进行排序或分区。

从表面上看文档，TBB 有 concurrent_hash_map 和队列类。

只有 concurrent_vector TBB 会提出这个问题。文档描述如下:

A concurrent_vector<T> is a dynamically growable array of T

但是，只有存储(重新)分配是无锁线程安全的，而不是元素本身；

A concurrent_vector never moves an element until the array is cleared, which can be an advantage over the STL std::vector even for single-threaded code

和

Operations on concurrent_vector are concurrency safe with respect to growing, not for clearing or destroying a vector. Never invoke method clear() if there are other operations in flight on the concurrent_vector.

因此，如果你想对一个 concurrent_vector 进行排序，你可能会

• 想要互相排斥访问；如果延迟很重要，您可以使用原子自旋锁而不是成熟的互斥锁，但无论如何您都需要同步
• 想要考虑复制到一个排序的范围，而不修改源条目；这可以在没有进一步锁定的情况下完成(假设 vector 元素上的读取操作是线程安全的)，参见例如<强> std::partial_sort_copy