Tim, Do you really need to parametrize the constant-time size property? C++11 requires constant time size for all containers. I think that this is also a reasonable requirement for Heaps. I'm not aware of any applications that use so many heaps that the extra 4-8 bytes required by a size parameter would make huge difference in memory usage. Also, for heaps that can be effectively implemented in terms of other containers, they should guarantee O(1) size. The stability issue relates to a previous discussion from a couple months ago (brought up by Cliff Green, http://article.gmane.org/gmane.comp.lib.boost.devel/219330). Cliff was concerned that the implementation of stability added overhead to the normally unstable heaps (i.e., an extra size_t, I think) from the implementation. I worry that the use of a policy parameter to specify stability will result in "accidental overhead" in cases where users don't fully understand the impact of their configuration choices. Would it be better (would it be possible?) to write stable_heap as a heap adaptor? I think that this approach (if possible) has two benefits. First it encapsulates the strategy for implementing stability. It also provides a single point of reference for describing the impact of using that configuration. Andrew
On 6/2/2011 10:08 AM, Andrew Sutton wrote:
C++11 requires constant time size for all containers.
Not strictly true. Even though the requirement is specified for the general container requirements, it's possible for a container to remove that requirement. As "forward_list" does, by removing the "size()" member function. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
Not strictly true. Even though the requirement is specified for the general container requirements, it's possible for a container to remove that requirement. As "forward_list" does, by removing the "size()" member function.
Ah. Thank you for the clarification. This makes me wonder how important size() actually is for heaps. Most of the algorithms I've seen simply use empty(). Andrew
Not strictly true. Even though the requirement is specified for the general container requirements, it's possible for a container to remove that requirement. As "forward_list" does, by removing the "size()" member function.
Ah. Thank you for the clarification.
This makes me wonder how important size() actually is for heaps. Most of the algorithms I've seen simply use empty().
if you use priority queues in a scheduler to run different jobs by their priority, it may be interesting to inform the user, how many jobs are left ... tim
hi,
Do you really need to parametrize the constant-time size property?
the design to customize the data structure is directly related to boost.intrusive ... and basically it does not hurt to be able to customize it, even if the effect may be marginal ...
The stability issue relates to a previous discussion from a couple months ago (brought up by Cliff Green, http://article.gmane.org/gmane.comp.lib.boost.devel/219330). Cliff was concerned that the implementation of stability added overhead to the normally unstable heaps (i.e., an extra size_t, I think) from the implementation. I worry that the use of a policy parameter to specify stability will result in "accidental overhead" in cases where users don't fully understand the impact of their configuration choices.
it is not possible to write every heap algorithm as `stable' heap. i do not recall the exact point that will break stability if one just orders the nodes in the tree, but there was a non-trivial issue (possibly related to mutable heaps). iac the node versioning seems to be the usual approach for implementing stable heaps. the type of the version should be exposed to the interface, though, so one can specify arbitrary-sized integer types to avoid overflows ...
Would it be better (would it be possible?) to write stable_heap as a heap adaptor? I think that this approach (if possible) has two benefits. First it encapsulates the strategy for implementing stability. It also provides a single point of reference for describing the impact of using that configuration.
what do you mean by `heap adaptor'? at the moment, i am using the same implementation, but customize the node type ... tim
participants (3)
-
Andrew Sutton -
Rene Rivera -
Tim Blechmann