STL优先队列 - 删除一个项目

Question

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

我的问题是，我想偶尔取消一个计时器，但没有接口可以轻松地删除优先级队列中不是顶部项的项目。

有什么建议吗？

谢谢您的帮助。

- Umbungu

Answer 1

我曾经遇到过完全相同的情况，做了以下几点:

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

¹ 为了快速查找空闲索引，我使用了一个单独的索引堆栈 std::stack。当添加计时器时，如果该堆栈为空，则添加到向量的末尾；否则弹出顶部索引并使用它。

² 在此处将索引推送到空闲索引堆栈

整个过程有些棘手和容易出错，特别是如果你的计时器回调需要添加或取消计时器。 这里链接到我上面描述的取消计时器类的代码，该代码属于公共领域

- sbk

---

我也做过类似的事情。这是一个有用的模式。 - Tyler McHenry

有趣。但我看不出你如何处理计时器“取消”的情况，而实际上它已经执行了。当计时器触发时，你是不是只让调用代码清除任何计时器的句柄？ - Lightness Races in Orbit

我想让我的队列结构存储一个 boost::shared_ptr<some_detail_type>，它可以作为计时器的句柄。然后任何人都可以进入该句柄并设置“已取消”标志，在计时器到期时被捕获。 - Lightness Races in Orbit

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)删除。

- jpalecek

---

有趣。这个函数会复制多少数据？ - Dummy00001

Answer 3

尽管其他答案表明不可能，但实际上可以访问任何标准容器适配器（包括priority_queue）的基础容器，因为该容器作为一个受保护成员 c 暴露。您可以继承priority_queue并扩展接口，或者使用诸如此方法来暂时访问普通的priority_queue。

- Mike Seymour

---

有趣的是，容器成员"c"实际上是标准化的。 - sstn

Answer 4

我的问题是，我想偶尔取消一个计时器，但是没有任何接口可以让我轻松地删除优先队列中不是顶部项的项目。

如果经常取消计时器，则需要使用一些不同的结构。std::map 也不错，尽管 delete_min 的成本会增加。

如果很少取消计时器，则将元素标记为已删除（并在 ::pop 期间忽略它）可能会奏效。

- Dummy00001

Answer 5

STL优先队列容器专门设计为只能访问顶部项，因此如果您需要能够删除非顶部项，您将需要找到另一个可用的类。

- Amber

Answer 6

我有同样的需求。如果您有更改容器的自由，可以解决此问题的是std::set（不允许重复）或std::multiset。

两者都是有序的，并且可以对容器大小进行对数删除元素（有关详细信息，请参见文档）。 如果需要在多集合中删除帮助，您可能想要查看this。

在决定之前，请查看std::set vs std::priority_queue的区别。

- n00buser