是否有一个并发的可变优先队列？理想情况下，我正在寻找一个C++实现，但是，首先指向算法的指针将非常有帮助。
明确一点，我正在寻找一个可以调整元素优先级的优先队列。特别是，TBB的concurrent_priority_queue没有提供必要的功能。(就算我们忽略并发性，STL的priority_queue也不提供必要的功能。) Boost.Heap库提供了我想要的串行功能，但没有并发性。自然地，我正在寻找比每个操作都锁定整个队列更精细的东西。
并发可变优先级队列
13
- foxcub
4
我怀疑这样的队列要么需要一个粗略的锁，要么需要非常多的细粒度锁定，但两者都不太高效。但是你的问题可能有另一种解决方法。你的使用情况是什么？ - Jan Hudec
是的...我无法快速地可靠地完成这样一件事。Futex /CriticalSection锁定是否如此重要？从树的一个地方移除指针并将其插入另一个地方（或者在您的优先级列表实现中执行所需的任何操作，例如将指针从一个集合移动到另一个集合）似乎不需要太长时间。 - Martin James
好吧，我真的希望有一种无锁数据结构。至于更新，对于通常的数据结构来说，它们非常复杂：你不仅需要将指针从一个位置移动到另一个位置，还需要重新平衡树或执行类似的操作。 - foxcub
@JanHudec，就我的使用情况而言，我有几个优先级队列正在同时处理（希望大部分时间是独立的）。但有时一个队列中的删除需要更新另一个队列中的优先级。 - foxcub
1个回答
10
并发优先级队列通常使用跳表实现，因此Facebook的ConcurrentSkipList可能符合您的要求。
- Ben Manes
1
非常好的建议。非常感谢您的指引。我只希望他们有一个关于这个类的文档页面。 - foxcub
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接