c++ - 高度并行的双端队列

Question

是否有高度并行双端队列的实现( boost 或其他)？特别是，我希望能够说出这样的话(伪代码):

parallel.for(deque.erase, list<locations>);

换句话说，并行删除所有传入的项目，例如双端队列中的位置列表。同时，我不希望这个操作阻塞其他与本次删除/插入无关的删除或插入。

因此，例如，线程 1 可能(并行)删除位置 1、3、7、9 处的项目，线程 2(并行)插入双端队列(并行插入可以是 push_back 并且看起来很容易，除非尝试插入旧的删除位置)，线程三可以(并行)删除位置 2、4、8 [请注意，不同的线程删除永远不会与删除位置相交]。试图删除一个已经被删除的位置(持有一个标记值)是一个错误。这可能意味着位置是有状态的，直到发生一些压缩(这需要一个锁)。被删除的位置可以保存一个哨兵值，告诉其他线程你可以插入我...所以接口(interface)可能不是 push_back，而是 push_available。

大声思考，我意识到双端队列可能变得支离 splinter 并增长(内存泄漏)，因为 push_backs 不填充已删除的值(？)，但某种压缩似乎最终是可能的。

paralell_deque 还应该允许在锁被移除之前不允许插入或删除的地方进行锁定。例如，当打印双端队列的状态(内容)时...

deque 可以有多种实现策略，有些可能比其他的更适合这种并行性。

我也意识到这个问题可能过于模糊，在给出有趣的答案之前就被否决了。

Answer 1

听起来您真的想要一个基于节点的容器(它不会使迭代器失效)但具有连续存储。

我建议使用 Boost Intrusive 在连续存储的元素之上构建一个链表。

但是，在此之前，我会使用您能想到的最简单的数据结构，直到您知道您到底想要什么以及为什么。