Boost logo

Boost :

Subject: Re: [boost] [review] [heap] Summary
From: Tim Blechmann (tim_at_[hidden])
Date: 2011-06-20 14:56:15


hi thorsten,

> I didn't cast a vote, but I will be /extremely/ unhappy with having
>
> a library where this is not addressed:
> > - Thorsten Ottosen suggest making b_heap and d_ary_heap container
> > adaptors along the lines of std::stack, std::queue, and
> > std::priority_queue, allowing parameterization over (e.g., stack-based
> > container). Subsequent discussion indicates that there are some
> > impracticalities in doing so, namely that it could invalidate other
> > policies (e.g., stability).
>
> I fail to to see the problem; I don't recall any problem with stability
> or other problem. If there is one, then make the guarantees conditional
> on the properties of the supplied container.
>
> If drop-in support for other types of containers is not added,
> the library is a lot less useful for me (and many others). There is
> plenty of motivation for having this feature, and it is dead-easy to
> implement as well.

concerning make_heap functions:

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

stability:
in order to implement stability, we need to either maintain a state for the
version count or to find a way to lookup elements by a key. maintaining a state
will require extra memory which cannot be stored in the container. looking up
the key of an inserted element will be inefficient (O(n) because one cannot
efficiently find elements) or requires an indirection via a dictionary (and
therefore cannot be implemented as container adaptor).

mutability:
mutability for container adaptors requires an indirection, which cannot be
achieved via container adaptors.

... for immutable and non-stable heaps, the std::make_heap family will perform
pretty well (as they are usually d-ary heaps with an arity of 4) ...

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
* 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.
* 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 ...

tim




Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk