Boost logo

Boost :

Subject: Re: [boost] [gsoc] boost.heap update
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-07-29 05:34:22


thanks for looking into it ...

> * Motivation: Many boost libraries offer a "Motivation" section to say
> what real world issues are addressed by the library. Currently, I am
> using std::priority_queue and it suits my needs. When would they be
> insufficient?

true ... as for std::priority_queue. it not mutable, not stable, different
instances cannot be merged or compared, elements cannot be iterated.

> * Navigation: Some pages are missing navigation elements, e.g.
> should have a
> "top"-link.

hm, i just saw it too ... i guess, this is a quickbook/boostbook issue, that
will be resolved automatically, if it becomes an official part of boost ...

> * Warnings: For instance: Mutability: "Incorrect use of increase or
> decrease may corrupt the priority queue data structure!" It would be
> good to have short examples of correct and incorrect usage.

i am a bit afraid to show a piece of incorrect code. in the documentation.
but is is probably clearer than just describing it with words ...

> * Data structure comparisons: The information seems rather incomplete.
> For instance, "In contrast to d-ary heaps, binomial heaps can also be
> merged in O(log n)." OK, now I know, that binomial heaps can be merged
> in O(log n), and d-ary can't. But I don't know the complexity for
> merging d-ary nor any other heap.
> Maybe it would be easier to use one or more tables to compare the
> features/complexities?

well, i have been thinking about it ... however i am not sure, what to
compare (amortized or worst-case complexity). also the analysis of pairing
heaps is not solved, yet ...
otoh, there is also the `benchmarks' section.

will try to incorporate your changes!


Which is more musical, a truck passing by a factory or a truck passing
by a music school?
  John Cage

Boost list run by bdawes at, gregod at, cpdaniel at, john at