From: Yakov Bachmutsky (yakov_at_[hidden])
Date: 2002-12-10 04:30:03
I would like to propose a multi priority queue class template.
I've written this template about a year ago and I really use it.
What I mean by a multi priority queue is this:
1. U define as much priorities as u like (I use 256)
2. U can push an item to any (valid) priority
3. U can request to pop an item from a specific priority - pop(item,pri); -
but if there are no items in this priority u'll get the highest priority
item from lower priorities.
4. (and thats why I wrote it) U can request to pop the highest priority item
simply by pop(item).
5. U have an iterator class to traverse the entire queue.
I know this can be implemented very simply by holding many std::deque
classes and checking them one after the other to find the first (highest)
populated item but my queue is optimized for not doing this traverse so. I
do all actions in O(1).
The declaration looks like this:
template<class Ty, int nPr> class pque
Ty is the item class like in std::deque
nPr is the number of priorities (0 is highest)
My implementation follows my private programming style so the pop function
returns bool to indicate success and the item is given by reference.
If there is any interest in this class template I'll happy to share it -
just tell me where to upload it.
My class does not use the std allocator and iterator - I guess I'll have a
bit of reconstruction to do.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk