STL优先级队列 - 删除项目

Question

我想使用C++ STL priority_queue容器适配器实现计时器排队系统.

我的问题是我偶尔会取消一个计时器,但没有接口可以让我轻松删除priority_queue中不是顶级项目的项目.

有什么建议？.

谢谢您的帮助.

Answer 1

我有一个完全相同的场景,并做了以下事情:

• 我保留的结构std::priority_queue只包含排序的时间和a的索引std::vector<Handler>(在我的情况下Handler是boost::function,但也可以是指向接口或函数的指针)
• 添加计时器时,我会在处理程序¹的向量中找到一个自由索引,并将处理程序存储在该索引处.将索引和时间存储在priority_queue中.将索引作为标记返回给客户端以取消
• 取消定时器,传递添加时收到的索引.清除该索引处的处理程序(对于boost::function调用clear(),如果使用指针,则将其设置为零)
• 当回调计时器时,从优先级队列中获取其处理程序索引并检查处理程序向量 - 如果该位置的处理程序为空()/ NULL,则计时器已被取消.将处理程序索引标记为free ².

¹为了快速找到一个免费索引,我使用了一个单独std::stack的索引.添加计时器并且该堆栈为空时,在向量的末尾添加; 否则弹出顶部索引并使用它.

²这是将索引推送到自由索引堆栈时的要点

整个过程有点棘手且容易出错,特别是如果您的计时器回调需要添加或取消计时器.这是我上面描述的取消计时器类的链接,此代码是公共域

Answer 2

我担心STL priority_queue不提供这样的功能.您可以编写自己的堆类(这并不难).你甚至可以std::xxx_heap通过像这样的脏技巧来使用这些功能:

delete_heap(iterator to_delete, iterator heap_begin, iterator heap_end)
{
  to_delete->key = something that would compare less to everything; // make sure it gets to the top in the next step
  std::push_heap(heap_begin, to_delete+1);
  std::pop_heap(heap_begin, heap_end);
}

哪个会让你O(log n)删除.