Re: [boost] [gsoc] boost.heap snapshot

Subject: Re: [boost] [gsoc] boost.heap snapshot
From: Daniel Trebbien (dtrebbien_at_[hidden])
Date: 2010-07-11 18:39:40

On 2010-07-11, Tim Blechmann <tim_at_[hidden]> wrote:
> hi all,
>
> i have uploaded a snapshot of boost.heap [1] and the initial documentation
> to [2]. feedback / suggestions are more than welcome! especially i would
> like to hear some thoughts about the interface, and if someone requests a
> specific heap implementation, it is also a good time to ask for it now ...
>
> cheers, tim
>
> [1]
> http://tim.klingt.org/code/attachments/download/28/boost_heap_110710.tar.gz
> [2] http://tim.klingt.org/boost_heap
>
> --
> tim_at_[hidden]
> http://tim.klingt.org

A few points of feedback:

1. Would it make sense to overload some operators to merge heaps?
Perhaps `|` and `|=` to mirror Boost Dynamic Bitset and the suggestion
for `interval_set` of Boost Interval Container Library.

2. The `pointer`, `const_pointer`, `reference`, and `const_reference`
typedefs should come from the `Alloc` template parameter.

3. The `pointer` and `const_pointer` types from `Alloc::template
rebind<node>::other` should be used instead of `node*` and `const
node*`.

4. It might be nice to implement a B-heap. Poul-Henning Kamp wrote an
article for ACM Queue that was published just a month ago. In it, Kamp
argues for B-heaps instead of binary heaps:
http://queue.acm.org/detail.cfm?id=1814327

5. A soft heap implementation might be nice, too, depending on time.
Of course, this could be a future extension:
http://en.wikipedia.org/wiki/Soft_heap

6. Members that take rvalue references might be good to add in
anticipation of C++0x.

7. I saw in the documentation that you were defining the interfaces of
heaps and mutable heaps. This is really good because it helps to
standardize things. It would be nice to also have concept checking
classes so that programs can use `BOOST_CONCEPT_ASSERT`. See
<boost/graph/graph_concepts.hpp>
(http://www.boost.org/doc/libs/1_43_0/boost/graph/graph_concepts.hpp)
for some examples of creating concepts.

8. In the documentation, would you outline the major differences
between the different heap types?

9. Do your implementations accept equivalent values (equivalent in the
equivalence relation induced by the compare object)? I assume so,
because you discuss "stable" heaps. A point about accepting
"duplicates" would be good to add to the documentation, though.