Some background: I am building a C++
thread manager which allows the user to create an AsyncJob
object and assign a priority of execution. I have a JobManager
singleton class which manages a priority queue of these AsyncJobs
and assigns them to a thread when available.
The Problem: Users need to be able to modify the priority AFTER
creation. For instance, based on some run-time events, a file may need to be loaded more urgently than others. The issue I am facing is that priority queues only reorder elements on the internal heap when push()
or pop()
is called. There is no exposed interface, to my knowledge, that allows one to request a reorder based on changing priorities.
What I would like to do is something like this:
hashmap
in my JobManager
class which holds pointers to objects in the priority queueJobManager
then signals to the priority queue that priorities have changedWhat would be the best way of going about this? Should I expect to make my own custom priority queue class? Or maybe extend from the std::priority_queue
?
Thanks!
One option could be to allow your AsyncJob to have a 'cancelled' state, and simply add a new (copy of) the AsyncJob to your PQ each time the priority is modified, after cancelling the old one.
As with many things, I'd suggest that 'best way' is highly subjective, as it depends on how constrained you are, and how you quantify 'best'. Personally I like to avoid deriving from standard library types and re-inventing container structures if possible.
A binary search tree seems like a decent alternative.
The binary search tree should be ordered by priority and, secondly, if priority isn't unique, a unique identifier / set of identifiers in the object.
If you don't know the previous priority when you want to change it, you'll need a way to look that up - perhaps a hash table of object to priority.
This allows you to remove and reinsert a specific item in O(log n)
, without losing the O(log n)
performance on other operations (and O(1)
to get the first).
For C++:
If priority is unique, a map
of priority to object could work, otherwise a set
<
pair
>
where the first element in the pair is the priority, and the second is the object (yes, I know, those aren't necessarily BST's).
For the hash table, you could use an unordered_map
of object to priority, or simply a map
pre-C++11.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With