Boost logo

Boost :

Subject: Re: [boost] [gsoc] heap review
From: Cliff Green (cliffg_at_[hidden])
Date: 2011-05-11 13:18:48


>From the docs on stable priority queue:

"If a priority queue is configured to be stable, an integer timestamp is
associated with each node, specifying the time ..."

I was one of the people discussing priority queue use cases, probably a year
ago, and specifically was wanting a stable priority queue. I also said that
adding a time stamp or counter to each entry was a naïve approach (and one
that I had done myself in about an hour, adapting a std::priority_queue). I
asked for a true, "native" implementation of a stable priority queue,
because adding a time stamp to each entry has a couple of drawbacks:

1) It adds storage to each element - while for many (most?) applications
this extra storage is negligible, in some cases it is not negligible
(embedded systems with large queues)
2) It can fail - if a true time stamp is used, what happens when times are
adjusted? If a counter is used, what happens when the counter overflows?
While the failures are edge cases, there's no need to have any failures.

I can dig out the e-mail, if more details of the discussion are needed. I'm
a bit perplexed that either this discussion was completely missed, or
somehow "read but misremembered, with the opposite of the desired result".

There must be heap data structures for priority queues that preserve order
(with no extra memory) at the cost of being slightly slower (but still with
the same big-O complexity). This is what I expect of a Boost library -
finding and implementing the best, not something naïve and easily thrown
together.

So this gives me very little confidence for a robust, world-class
implementation of heap structures.

Please read this as encouragement to do the hard work, not just the minimum
necessary for a review, at least for the case mentioned in this e-mail.

Cliff

 


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk