The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Priority Queues


I need to use priority queue but I also need to maintain the order of entries if the priority is same. off the shelf STL priority_queue doesn't do that.

it will maintain sort order if the priority is different but if priority is same it will position elements randomly.

any ideas?.
Friday, March 03, 2006
Roll your own.

Any good algorithm textbook will have examples of how to create queues within a variety of constraints.
Anonymous Coward
Friday, March 03, 2006
How many priorities?

Keep an array indexed by priority with a list in each array element.

If you are going by strict priority start at the highest priority and process work until you hit a limit or run out of work.

Strict priority is often not desireable because it isn't fair enough. Starvation happens when high priority work comes in all the time and low priority work languishes on the queue.
son of parnas
Friday, March 03, 2006
When you put an item in the queue, give it a "timestamp".
When comparing priorities in the priority queue algorithm,
compare first on priority and then (if priorities are equal) on the "timestamp".
Saturday, March 04, 2006
Ok.  I wrote the original "roll your own" post but forgot to change the name.  In my algorithm book, one chapter alone discusses...

first come, first served
shortest job first
round robin (and its processor sharing variant)
multilevel queue
multilevel feedback queue
multiple processor scheduling
real time (hard and soft)

...and describes the pros and cons of each method, as well as how to determine the effectiveness of your queue.

I apologize - this is overkill. However, if there is no STL queue that does what Me originally wanted, as everyone else has pointed out so far, there IS the possibility of starvation (an item never gets its turn) and you really need to know what you're doing. Ergo, my original advice:

Read an algorithm book. Don't just "hack" a solution.  :)
Saturday, March 04, 2006
When you put an item in the queue, give it a "timestamp".
When comparing priorities in the priority queue algorithm,
compare first on priority and then (if priorities are equal) on the "timestamp".

Exactly.  The priority to use for the priority queue should be a combination of your application's "priority" and whatever subcriteria you need for sorting the equal "priority" elements (such as a timestamp or simple counter if you need to maintain insertion order).  Use a comparison function that compares "priority" first, then "timestamp" (or "counter" or whatever) if "priority" is equal.
SomeBody Send private email
Saturday, March 04, 2006
if you can change a class definiton of objects you store in the priority queue, then add a timestamp field (for example, it maybe int value, which stores the order of objects in your istream)
pq is parameterized by two classes

template <class Container, class Compare>
class  priority_queue

define the second class such that it takes into account a timestamp of  objects
Andrei Lopatenko Send private email
Monday, March 06, 2006
Great help guys.

I'll actually test out the timestamp. I do have my own functor since I'm basically storing pointers. all I have to do is probably add a timestamp.

will test out today.

I do not believe in rolling my own unless I can absolutely do nothing with off the shelf. Kinda like do not re invent the wheel :).

Thanks for all the help.
Monday, March 06, 2006
What I've done in such circumstances is to give each element both a priority and a sequence number, and then the sort key is (priority, sequence), so that sequence is used as a tie-breaker when the priorities are the same.

You will of course have to write your own comparison function.
dot for this one Send private email
Monday, March 06, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz