Re: [boost] [review] Heaps

Subject: Re: [boost] [review] Heaps
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-01 09:49:33

>> Also, if it is not already possible, those heaps that use
>> an std::vector ir similar internally should have this data-structure
>> as a template argument s.t. we can easily change this. In some
>> application it might even be possible to use boost::array<T,N>.
>
> hm ... not sure about this: the implementations requires push_back/pop_back
> (which are not available for boost::array) and random access iterators. the
> std::vector can be configured to use a different allocator using parameters and
> one can use `reserve' to reserve memory for the vector ...
>
> so i do not really see a specific use case, where one really wants to use a
> different container, or do you have a specific case?

I think the data structure *could* be adapted to use an array, but the
array would have to be adapted to emulate a back insertion sequence.

There may be cases where using a deque gives better performance than a
vector, especially if the value_type is large (say, > 512B). This
could be a moot point since priority queues are almost always used
indirectly (with pointers, handles, or descriptors). Those are
typically in the 4-32 byte range.

I think there's value in considering parameterizing over the container
type. There are probably use cases where bounding the heap size is
useful. I'd like to know about these use cases before committing to
make the change, however.

Andrew