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
