priority queue wrapper

[Jim Strathmeyer]

So, I've been looking for a wrapper class for STL priority queues, and
haven't been able to find one. (Websearching for info about the STL sure
shows how much it's changed over the past few years.) I basically need
to be able to queue up an object with a time, and retrieve and/or pop
the element with the earliest time. So I coded a little something up. I
also have a push function to reinsert the topmost element. I'm not very
good with templates, or with stl or priority_queues, so if I've done
anything blindingly stupid please let me know.


#ifndef PRIORITYQUEUE_T
#define PRIORITYQUEUE_T

#include <queue>

template <typename T>
class PriorityQueue {

private:
template <typename U>
typedef struct PriorityElement {
U * element;
double time;
PriorityElement(U * element, double time) : t(t), time(time) { }
};

template <typename V>
struct LessPriorityElement {
bool operator()(PriorityElement<V> * x, PriorityElement<V> * y) const {
return (x->time > y->time);
}
};

std:riority_queue<PriorityElement<T> *,
std::vector<PriorityElement<T> *>,
LessPriorityElement<T> > pq;

public:

void Add(T * e, double time) {
pq.push(new PriorityElement<T>(e,time));
}

void Push(double time) {
if( time = 0.0 ) return;
PriorityElement<T> * pe = pq.top();
pq.pop();
pe->time += time;
pq.push(pe);
}

void Pop() {
delete pq.top();
pq.pop();
}

T * Top() const {
if( pq.empty() ) return NULL;
return pq.top()->element;
}

double TopTime() const {
if( pq.empty() ) return 0.0;
return pq.top()->time;
}

bool Empty() const {
return pq.empty();
}

unsigned Size() const {
return pq.size();
}
};

#endif

 

[Dietmar Kuehl]

So, I've been looking for a wrapper class for STL priority queues, and
haven't been able to find one.

That's probably because normally you don't need to wrap
'std:riority_queue'. Typically, you just use it, possibly
inserting 'std:air's if the elements don't readily contain
a priority. What is quite common, though, is using a different
predicate.

template <typename U>
typedef struct PriorityElement {
U * element;
double time;
PriorityElement(U * element, double time) : t(t), time(time) { }
};

I'm always somewhat suspicious if pointers, especially non-const
pointers, are passes around: typically, this indicates a design
flaw! Reasonable alternatives are:
- Smart pointers indicating and handling the ownership policy
associated with the object, e.g. 'boost::shared_ptr<T>'
indicating the the object is released (automatically) as soon
as nobody references it.
- Value types copying the elements appropriately.

std:riority_queue<PriorityElement<T> *,
std::vector<PriorityElement<T> *>,
LessPriorityElement<T> > pq;

.... and in this case the suspicion against pointers is readily
confirmed: why do you use a pointer here? It is much easier and
probably also more efficient to use a 'PriorityElement<T>' as
value type (the memory allocation probably outweights the possible
increased effort for copying). ...or, what I would actually do,
use a 'std:air<double, T>' as element type: 'std:air' just
lumps together two otherwise unrelated objects which is the same
purpose 'PriorityElement' apparently has.

void Add(T * e, double time) {
pq.push(new PriorityElement<T>(e,time));
}

Of course, I would take the first argument by value. If the user
of the class still desires to use a pointer, he has the option
to do so in this case. The reverse is not true, i.e. using value
types is more general.

I would also call the function "push()" because this is what it
doese, in contrast to this function:

void Push(double time) {
if( time = 0.0 ) return;
PriorityElement<T> * pe = pq.top();
pq.pop();
pe->time += time;
pq.push(pe);
}

This function actually changes the priority of the top element and
does not push a new element into the heap as the name indicates. It
is also worth noting that this approach is not the most efficient
one (although it has the same asymptotic complexity as the
alternatives, i.e. it is O(log n)): if you changed the key and
adjusted the heap, it would be more efficient. I know that
'std:riority_queue' does not support this operation but I have
made available a bunch of priority queues which support this
additional operation (some of them even support adjusting the priority
of arbitrary elements, not only of the element). You can download them
from <http://www.dietmar-kuehl.de/cxxrt/heaps.tar.gz> (I just realized
that this archive is actually incomplete; I shall update it with a
more complete version over the weekend).

T * Top() const {
if( pq.empty() ) return NULL;
return pq.top()->element;
}

I consider this to be the wrong approach: accessing the top element
of an empty heap is a programming error which should probably
terminate the program immediately before worse things happen. If this
is not viable for whatever reason, I would throw an exception.

Of course, I wuold also use the conventional names use in C++ to
access priority queues: 'top()', 'pop()', 'push()', 'empty()',
'size()', etc. Since these should have the custom semantics, this
could allow the use of your wrapper exchangably with the other queues.