[boost] Re: Stable Heaps

From: Bill Wade (bill.wade_at_[hidden])
Date: 1999-12-03 12:24:29

> 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".

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 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.

> 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>.