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
>> 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 ...
-- tim_at_[hidden] http://tim.klingt.org 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk