BinaryHeap is a range so it goes in std.range. Agree?

[Andrei Alexandrescu]

On 06/08/2010 12:29 PM, jlquinn wrote:
> Steven Schveighoffer Wrote:
>>>> You might say the same about an array, but an array is special
>>>> in that if I append to one array, it does not affect the
>>>> other.
>>>>
>>>> I don't know where it belongs. To me, a range is a type that in
>>>> itself cannot affect the topology of the data structure. It's
>>>> like a window into the data structure that provides a common
>>>> interface. A container is the owner of the data structure, and
>>>> can provide ranges over its data. This may be an inadequate
>>>> view, but its worked for me so far.
>>>
>>> Actually if a heap is built on top of a container, it can affect
>>> its topology because it has the sensible primitive of adding to
>>> the heap.
>>
>> Yes, that is my point of why at least growable heaps should not be
>> considered ranges.
>
> I second this point.  In STL parlance, BinaryHeap would be a
> container adapter.  Also, to me a range feels morally equivalent to
> an iterator and binary heap feels like a data structure that you can
> iterate over.  And the fact that you can insert objects into it and
> later remove them in a manipulated order makes it feel even more like
> an active component and thus a container.
>
> So I'd naturally go looking for it in std.container and be a little
> confused to find it in std.range.  It would become a quirk that one
> adjusts to.
>
> Jerry

Unfortunately things are not that simple.

A BinaryHeap built on top of a range can _still_ grow, just not larger 
than the size of the range. If you look through the code, you'll see 
that a constructor takes a range and an initial size.

Oddly enough, this is a very frequent of binary heaps: you have a range 
and you want to take the top N. So I wouldn't want to discount that.

So, what we have here are binary heaps having ranges as support (can 
only grow up to the size of the range) and binary heaps having 
containers as support (can grow with the container).


Andrei