On 2010-07-11, Tim Blechmann <tim@klingt.org> 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@klingt.org 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.