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