[boost] Re: Stable Heaps

From: Nathan Myers (ncm_at_[hidden])
Date: 1999-12-03 14:15:40

"Bill Wade" <bill.wade_at_[hidden]> wrote:
> From: Dietmar Kuehl [mailto:dietmar_kuehl_at_[hidden]]
> 
> > Basically the standard C++ library already has a stable heap with the
> > best [asymptotic] performance which can be achieved in this case: It is
> > called "multiset".

This has a problem: multiset is not guaranteed to have the
desired property.  Typical implementations do, but your code
will not be portable.
 
> Well if you have N elements and M much less than N values, the asymptotic
> behavior for
>   set<mutable queue<T> >
> is better.  It also doesn't suffer the ambiguities associated with
> multiset::insert.

This approach has another problem: creating and destroying queues
may dominate the runtime.
 
> This application should probably default to queue<T,list> rather than
> queue<T,deque> since it is likely to have many very short queues and also
> has much better support for removing elements out of order.

Lists are cheaper to create and destroy, so this approach may be better.

Probably best is an adapter approach in which queues are maintained
in a pool (or even statically) and re-used as needed.  For a small
number of priorities a vector of queues is probably best.
 
> > However, since this class has a different interface
> > than the other heaps, it is probably reasonable to provide a
> > corresponding adapter which gives the common heap interface to the
> > "multiset".
> 
> Even more so with set<queue>.

Indeed, std::priority_queue was intended as an example of the power
of adapters.  It should take hardly any longer to submit a nice
stable priority queue adapter than it has taken to discuss it in
the various forums.

Nathan Myers
ncm_at_[hidden]