Re: [boost] [review] Heaps: size and stability

Subject: Re: [boost] [review] Heaps: size and stability
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2011-06-05 08:27:08

> how does this approach deal with mutabiliy? if we have multiple keys a, and
> change one key from a to b and later back to a, we loose any information about
> the original position. we could simply define this sequence as undefined or
> interpret `update' as `insert' ...

I think that updating an object gives would have the same meaning as
erasing the object and then re-pushing it. The heap shouldn't expect
to retain a history of previous values.

>> Another option would be chaining, where each heap node contains either
>> a single item or a linked list of items with the same key value.
>
> chaining would be a reasonable way for node-based implementations, but not for
> container adaptors ...

I'm not sure that's entirely true. Obviously, it won't work for any
containers of the form container<T> where T is the value type of the
heap. If you can rebind it to something like container<node<T>>, you
might be able to make it work.

Chaining can change the properties of the data structure, however. For
example, a binary heap (for example) using array<T, N> does not
require an allocator. A stable binary heap (using chaining) would
require allocations. For node-based heaps, this is, of course, a
non-issue.

Andrew