From: Geurt Vos (G.Vos_at_[hidden])
Date: 2001-04-18 04:11:19
> Concerning the other question with respect to a newer version of the
> priority queues package: I haven't worked on this stuff since I have
> submitted an initial version. Actually, I haven't even pushed it
> through a review yet. If anybody is interested in taking this stuff
> over or to collaborate on the integration into Boost, I would really
> welcome any help with this! If you want me to do something,
> push me :-)
I will try to get them compiled for at least
BC++5.5 and VC++ 6. This is not necessarily
integrating stuff into boost. It's merely the
I already did some timing tests on Borland,
with different implementations for stable
priority queues. In the test I only measured
the time it takes to push an element. 10
elements are pushed. The first 5 are unique,
the second 5 are equivalent to the 'middle'
When the elements are of type std::string,
and only the first char is the priority, then
std::multiset out-performs all other
implementations. It's about 10-30% faster.
When the elements are of type int, I got some
1. boost::priority_queue is about 30% faster
than the std one and around 60% faster than
2. multiset is twice as fast as fibonacci_heap
(lazy_fibonacci_heap is slightly faster then
3. multiset is around 25% faster than pairing_heap
didn't try d_heap because it doesn't compile...
One conclusing from this is that a priorty_queue
wrapper is less suitable for large objects, because
some copying is done (correct?).
Another: heaps are slower than multiset!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk