Re: [boost] [gsoc] heap review

Subject: Re: [boost] [gsoc] heap review
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-05-12 07:41:12

hi,

>>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 remember this issue ... i need to have a closer look at the algorithms again. 
using a counter works for every algorithm, even if the algorithm cannot support 
a stable ordering `natively' ...

tim

-- 
tim_at_[hidden]
http://tim.klingt.org
Most of the trouble in this world has been caused by folks who can't
mind their own business, because they have no business of their own to
mind, any more than a smallpox virus has.
  William S. Burroughs