具有经常更改优先级的作业的优先级队列的数据结构

我有一个工人班,我可以向工人提交工作。worker保留这些作业并按优先级顺序顺序运行它们(优先级基本上可以是任何无符号int)。对于STD::PrimyIySype队列,甚至STD::SET/MAP可以用来存储按优先级排序的作业,然后工人可以在O(1)中按顺序提取它们。添加作业将是o(log n)。

现在,我的要求是能够改变提交工作的优先级。在STD::SET/MAP,我需要删除和添加回不同优先级的作业。这将是O(log n),在上面使用SET/MAP,它将在内部重新分配节点(这可能是用C++ 17避免的)。不寻常的是,在我的情况下,我会更频繁地更新工作优先级,而不是调度或执行它们。基本上,我可能会安排一次作业,在它执行之前,我可能会更新它的优先级数千次。事实上,每项工作的优先级都会以每秒10-20次的速度变化。 在我的例子中,假设队列中的工作不会超过10000个,这是相当安全的。在我的流程开始时,我希望它总是增长到大约10万个工作岗位,并且随着这些工作岗位被删除,队列最终应该几乎一直是空的,偶尔会有10-50个新工作岗位被添加,但它不应该增长超过1000个工作岗位。工作会以每秒几个工作的速率被删除。因为我对频繁的优先级更新的奇怪要求:STD:或设置不合适。简单的STD::列表似乎是一个更好的选择:优先级更改或更新/删除是O(1),当我需要删除作业时,O(n)遍历整个列表以找到最优先的项目,而不是优先修改优先级。

另一个观察是,即使工作优先级经常发生变化,这些变化也不一定会导致顺序的变化,例如,我可以简单地更新集合的关键元素(通过放弃常量或使密钥可变?)如果这个更改仍然将修改后的元素保留在左节点和右节点之间。对于这样的优先级队列,您有什么建议?任何Boost容器或自定义数据结构设计都可以。

在设置/映射的情况下,我使用优先级作为键。在我的例子中,为了使键唯一,每个键实际上是两个整数:作业序列号(从我为每个新请求递增的原子整数派生而来)和实际优先级号。这样,如果我添加多个具有相同优先级的作业,它们将按计划的顺序执行,因为序列号将保持它们的顺序。