STL Priority Queue - deleting an item

Question

Hello,

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

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.

Any suggestions?.

Thank you for your help.

Answer 1

The STL priority_queue container is specifically designed so that only the top item is accessible, so if you need to be able to remove non-top items, you're going to have to find a different class to use.

Answer 2

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.

Answer 3

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.

If canceling a timer happens often, then you need to use some different structure. std::map isn't that bad too, though cost of delete_min would go up.

If canceling a timer happens rarely, then marking the element as deleted (and ignoring it during ::pop) might do the trick.

Answer 4

Despite what some other answers say, it is possible to access the underlying container of any standard container adapter, including priority_queue, since the container is exposed as a protected member called c. You can either inherit from priority_queue and extend the interface, or use dirty tricks such as this to temporarily gain access to a normal priority_queue.

Answer 5

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

• 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².

¹ 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