13

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

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

有什么建议么？。

感谢您的帮助。

4

6 回答 6

10

我曾经遇到过完全相同的情况并做了以下事情：

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

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

2这是将索引推送到空闲索引堆栈的要点

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

于 2010-06-19T18:29:35.407 回答
7

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

于 2010-06-19T16:30:53.460 回答
4

尽管其他一些答案说了什么，但可以访问任何标准容器适配器的底层容器，包括priority_queue，因为该容器被公开为一个名为 的受保护成员c。您可以继承priority_queue并扩展接口，也可以使用诸如此类的肮脏技巧来临时访问普通的priority_queue.

于 2010-06-19T17:12:06.813 回答
3

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

如果取消计时器经常发生，那么您需要使用一些不同的结构。std::map 也没有那么糟糕，尽管 delete_min 的成本会上升。

如果取消计时器很少发生，那么将元素标记为已删除（并在 ::pop 期间忽略它）可能会起到作用。

于 2010-06-19T17:08:54.157 回答
2

STL priority_queue 容器是专门设计的，因此只能访问顶部项目，因此如果您需要能够删除非顶部项目，您将不得不找到一个不同的类来使用。

于 2010-06-19T16:14:37.700 回答
0

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

两者都是有序的，并且可以擦除容器大小的对数元素（有关详细信息，请参阅文档）。有关删除多集中的帮助，您可能希望看到这个。

在决定之前查看std::set 与 std::priority_queue的区别。

于 2016-11-12T10:50:52.057 回答