From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-17 08:40:18
> > Is there any interest in a stable priority queue?
> I don't know whether there is any interest, however, I can comment on
> the technical issues of the implementation of a stable priority queue.
> > This problem seems to come up so now and then
> > at several places. For what I know, also boost
> > doesn't provide a stable one (right?).
> For good reasons the provided priority queues do not support this
> option. Basically, the good reason is this: There are two approaches,
> only one of them being viable:
> - Find elements with the same priority in the priority queue and use a
> list or something similar to guarantee stability. This is rather
> inefficient and thus not viable: Priority queues are not order by
> their priority but rather according to a certain "heap property"
> which makes it efficient to access the element with a highest (or
> lowest priority).
> - Add a time stamp to the element and make it part of the priority key:
> If the priority is identical, compare the time stamp. This is the way
> to go and a viable approach with all priority queues I have provided.
> It desired, it should be reasonably simple to create a wrapper which
> aides in doing so.
Hmm, interesting one. A stable_priority_queue, which is wrapper
around one of the existing queues + timestamp should be quite
sufficient. The queue to use can be configurable, and even the
way the timestamp is handled could be a policy.
> > I do realize the functionality is quite easily
> > emulated with a std::multiset, which could be
> > reason enough to not add the priorty queue
> > 'wrapper'.
> It is likely that this approach is much slower than the other approach:
> I haven't measured the difference and can only guess but the idea of
> typical priority queues is to store the data in a structure well suited
> for the heap operations. In any case, the theoretical complexity of the
> approach using a multi-set is worse than the complexity of the priority
> queues (may be it is identical for some but definitely worse for
> Fibonacci heaps which happen, however, to be practically slighlty
> inferior than d-heaps).
Agreed, though 'much slower' highly depends on the situation.
The one thing multiset (and multimap) provide that I
miss in all the queue-alikes is the equal_range()
function, but then again, I don't know how much sense
it makes to have it in a queue...
BTW, are there any newer versions than the ones found
in boost_1_21_1/libs/pri_queue? That is, I'm having
some troubles getting them through the compiler (IOW,
which compiler is supported?).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk