STL 优先级队列 - 删除一个项目 [英] STL Priority Queue - deleting an item

问题描述

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

I want to implement a timer queuing system using the C++ STL priority_queue container adapter.

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

My problem is that I want to occasionally cancel a timer, however there are no interfaces that enable me to easily delete an item in the priority_queue that is not the top item.

有什么建议吗?.

感谢您的帮助.

推荐答案

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

I had the exact same scenario once and did the following:

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

• the structure I kept in std::priority_queue contained only the time to sort by and an index to a std::vector<Handler> (in my case Handler was boost::function, but could as well be pointer to interface or function)
• when adding a timer, I'd find a free index in the vector of handlers¹ and store the handler at that index. Store the index and the time in the priority_queue. Return the index to the client as token to cancel
• to cancel a timer, pass the index received when adding it. Clear the handler at that index (for boost::function call clear(), if using pointers, set it to zero)
• when it's time to callback a timer, get its handler index from the priority queue and check the handlers vector - if the handler at that position is empty()/NULL, the timer has been canceled. Mark that handler index as free².

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

¹ To make finding a free index fast, I used a separate std::stack of indices. When adding a timer and that stack is empty, add at the end of vector; otherwise pop the top index and use it.

² 这是将索引推入空闲索引堆栈的要点

² Here's the point when you push the index to the free indices stack

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

The whole thing is somewhat tricky and error-prone, especially if your timer callbacks need to add or cancel timers. Here's a link to my canceling timer class described above, this code is public domain

这篇关于STL 优先级队列 - 删除一个项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！