Boost logo

Boost :

Subject: Re: [boost] [gsoc] boost.heap update
From: Tim Blechmann (tim_at_[hidden])
Date: 2010-07-29 08:50:28

>> 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 ...
> If you have some comment like // DON'T DO THIS AT HOME
> no harm would come from showing incorrect code, I guess.

well, people may think, that you may use it, if you are supersmart ;)

> BTW: Wouldn't it be possible to check whether or not increase/decrease
> are used correctly (and throw an exception otherwise)?

no. there is no way to detect, whether some data has been modified. stl
containers like map/set don't allow you to modify the key elements in
general, boost.intrusive lets you modify the nodes, but assumes that you are
careful enough not to modify the key ...

>>> * 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 ...
> One idea would be to have a table for complexities for each pair of type
> and action (i.e. push, top, pop, merge, ...). If you have different
> values (e.g. optimal, average, worst-case), name them all. Maybe also
> describe what optimal/worst-case look like.

i will see, what i can do.

> One more thing: Even if boost heaps are probably quite easy to use, I'd
> add a small tutorial/examples section that shows some working code using
> heaps and their features.

well, in the concepts section, i am trying to explain the concepts and give
some example code. not sure, if it is better to separate concepts and
examples or to combine them ...


All we composers really have to work with is time and sound - and
sometimes I'm not even sure about sound.
  Morton Feldman

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