From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-17 08:40:18
> Hi,
> > 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?).
Geurt