Re: [boost] [review] [heap] Summary

Subject: Re: [boost] [review] [heap] Summary
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-21 03:11:30

> > using the b_heap as container adaptor is pretty fragile, since it
> > requires padding of the first element. this cannot really be done in the
> > std::make_heap family as this padding element should be invisible to the
> > user. with free functions
> 
> With free functions ...? What exactly?

make_heap/push_heap/pop_heap [1,2,3]

> > about a container<>  policy argument to the heap:
> > 
> > * one template parameter conflicting with another is not really clean
> > (although
> > 
> >    it could be caught via static assertions)
> > 
> > * containers cannot be rebound (unlike allocators). so one will have to
> > specify
> > 
> >    the exact type, that is used internally ... which is not really a
> >    clean interface, either
> 
> That is good enough for me.

for immutable heaps, this could be statically asserted ... still it somehow 
smells ...

> > * for mutable heaps, the allocator template parameter will be used for
> > both the
> > 
> >    heap container and for the list of values. if we specify the
> >    container, the allocator argument will have to be used for the value
> >    list, so we cannot statically assert the parameter conflict.
> 
> I can't follw you here.

to implement mutability, you need to efficiently find the elements in the heap. 
so the actual heap is not a heap of value_type of pair<value_type, 
stability_count_type>, but of iterators to a std list, which contains a 
pair<internal_value, index_in_heap>. the allocator argument is therefore used 
twice: once for the std::vector storing the heap-structed tree and once for the 
list containing the value and index to the heap.

> > * for mutable heaps, the container argument will have to be specified
> > with the
> > 
> >    exact type of the internal handles, which would have to be exposed
> >    directly.
> > 
> > this would be WAY easier, if we had a standardized way to rebind
> > containers. But since this is not the case, the interface would be
> > pretty ugly. my concern is not really the implementation ... it surely
> > is dead-easy ... but the consistency of the interface is not necessarily
> > trivial ...
> 
> Maybe this feature is not needed for mutable heaps?

maybe it is not reasonable for mutable heaps ...

in general, i prefer robustness and consistency over features. and i do not 
really see a reason to duplicate functionality from the stl ... if you really 
need to specify the container directly, you loose mutability and the nice 
interface for stability (you'd have to implement the version counting manually, 
but that is dead-easy). the only features that you will miss are ordered 
iterators and comparison/equivalence checks, however only few applications will 
actually use those features...

tim

[1] http://www.cplusplus.com/reference/algorithm/make_heap/
[2] http://www.cplusplus.com/reference/algorithm/push_heap/
[3] http://www.cplusplus.com/reference/algorithm/pop_heap/