On 06/08/2010 04:41 PM, Simen kjaeraas wrote:
Andrei Alexandrescu <seewebsiteforem...@erdani.org> wrote:
On 06/08/2010 10:53 AM, Simen kjaeraas wrote:
Andrei Alexandrescu <seewebsiteforem...@erdani.org> wrote:
But where should I put it then? I thought it would be even more
confusing if I put something in std.container that wait a minute, is
not a container.
How is it not a container? Because it uses a different container as a
back-end?
It does not implement the container primitives and is not a reference
type.
So it is not a container because you chose not to make it a container.
Instead of assuming that I'm simultaneously retard(ed) and stubborn, it
would be more productive to ask more about my reasons. I'll assume you
did so.
I wrote BinaryHeap out of necessity. The necessity was to solve the
selection problem (see topN, topNIndex in std.algorithm) and to
implement n-way merge (see std.algorithm.nWayUnion, I think I'll rename
it to nWayMerge).
In all these cases, there was no necessity for defining a heap as a
container; instead, using it as a means to add structure over an
existing range were sufficient.
If I defined the heap as a container, there would be need for one extra
allocation and also extra indirections to ensure reference semantics. I
wanted to avoid all that.
There are already rules that disambiguate range operations from
similar container operations. For example a range defines popFront()
whereas a container defines removeFront().
And my point is that removeFront() is popFront() with a different name,
so many containers could be considered ranges with mutated member
functions. :p But we're arguing semantics.
It's a good point. I agree it would make sense to define a binary heap
container in addition to a binary heap range. I'm only weary that they
don't have very clean means to reuse code, so we'll end up with some
unpleasant implementation internals. I guess I'll just have to do that.
I agree that a BinaryHeap built on top of a container may ultimately
affect the topology of the container, which makes it unlike e.g. Take
or Chain. I could choose to disallow that and simply require that
BinaryHeap always works on top of a range, not a container. But I
think it's useful to have the growing functionality, and I don't think
that makes BinaryHeap hopelessly confusing.
To me, this makes it a container.
Now, my favorite way of dealing with this: Where would I look for a
binary heap if I wanted one? I would think of it as a container, and thus
check std.container. If it was not there, I would use the search function
to find it. I can invent reasons, but it's mostly grounded in learned
names and categories.
I think that's sensible.
Andrei
