STL Priority Queue - deleting an item_问答_开发者

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 sugges开发者_运维技巧tions?.

Thank you for your help.

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

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.

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.

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.

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.

I had the same requirement. If you have the freedom to change the container, the one that can solve this problem is std::set (no duplicates allowed) or std::multiset.

Both are ordered and can erase an element logarithmic in container size (see the documentation for details). For help in deleting in multi set you might want to see this.

See the difference std::set vs std::priority_queue before deciding.