RE: [boost] 'stable' priority queue

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