STL Priority Queue - deleting an item

Question

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

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.