当前位置：文江博客话题详情

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

发布于 2024-09-05 23:23:42 字数 234 浏览 7 评论 0原文

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

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

有什么建议吗？

感谢您的帮助。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

雨后彩虹 2024-09-12 23:23:42

我曾经遇到过完全相同的场景，并执行了以下操作：

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

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

² 这是将索引推送到空闲索引堆栈时的要点。

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

回复收藏 0 原文

饭团 2024-09-12 23:23:42

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

I'm afraid STL priority_queue doesn't offer such functionality. You can write your own heap class (which is not that hard). You could even use the std::xxx_heap functions by dirty tricks like this:

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);
}

which will get you O(log n) delete.

回复收藏 0 原文

变身佩奇 2024-09-12 23:23:42

尽管其他一些答案是这么说的，但可以访问任何标准容器适配器的底层容器，包括 priority_queue，因为容器是作为名为 c 的受保护成员公开的。您可以继承 priority_queue 并扩展接口，或者使用肮脏的技巧，例如此可临时获得对普通priority_queue的访问权限。