On 2/23/11 8:51 AM, Steven Schveighoffer wrote:
On Wed, 23 Feb 2011 08:33:03 -0500, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
On 2/22/11 8:41 AM, Steven Schveighoffer wrote:
On Tue, 22 Feb 2011 09:23:00 -0500, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
This may as well be The Great Unification that was needed to converge
std.container with dcollections in a harmonious whole.
I'm not sure what to think of this ;) Is this a "oh what could have
been" statement or a "let's reopen negotiations" statement?
Note, I would love for dcollections to be mainstream Phobos, but I have
accepted the current reality and am fine with the way things are now
too.
Absolutely, and your collaboration on e.g. RedBlackTree and others is
very much appreciated.
The way I was thinking is, there would a lot of convergence if
dcollections wiped the notion of "cursor" and replaced it with takeOne
throughout. One obvious objection to the range/cursor design is there
are two abstractions to deal with instead of one. I had the intuition
that ranges should be enough, but was not quite able to substantiate
it fully until just about now. With take, takeExactly, and takeOne, it
seems that indeed there is only need for the range interface, and that
particular range types can replace cursors.
I don't think this is possible. When passing a range to a container for
removal, the container needs to access the underlying implementation
(e.g. pointer to tree node) in order to immediately know what element is
being removed. The takeOne range you propose does not allow this, you
can't get at the underlying range.
I agree that takeOne's source should be made public.
Even if you could, only
takeOne!(myrangetype) would work, which leaves us right back at
supporting a small number of specific ranges.
That's arguably correct and in any case better than supporting a range
plus a distinct cursor abstraction. You remove the cursor abstraction
and replace it with a specific realization of the range abstraction.
In addition, a cursor points to one element, a range points to multiple
elements. *conceptually* takeOne is the same, but it still stores the
range internally, so it's actually more expensive than a range to pass
around (additional _empty member).
I agree. There are a number of ways around this if important, but I need
first to be clear of the projected uses of takeOne.
I was thinking more along the lines of ranges being able to generate
cursors if it makes sense (i.e. base range is a range of the container).
Dcollections already supports this with the two accessors begin() and
end(). We might also need a last() which gets the last valid element in
the range. This would be akin to back().
Here is what I was thinking that can help with unifying interface. I'll
just show you as a code snippet:
void remove(C)(C c) if (is(C == mycursortype))
{
// since we know the structure of c, we can use it to remove the element
from the container
}
void remove(R)(R r) if (is(R == myrangetype))
{
// possibly can be optimized
}
void remove(R)(R r) if (!is(R == myrangetype) && isInputRange!R &&
is(typeof(r.begin) == mycursortype))
{
while(!r.empty)
{
auto c = r.begin;
r.popFront();
remove(c);
}
}
If wrapper ranges can "forward" the begin and end functions through
their API, then you can construct arbitrary ranges that will be accepted
as parameters to remove. We could potentially add forwarding functions
to all wrapper ranges, or we could pick ones that make the most sense
(like take).
Soon as we get to begin() and end() as primitives it all starts being
problematic. We may as well design with STL-style iterators then. One
good thing about ranges is that they _don't_ need to rely on lower-level
primitives.
In addition, dcollections (and any collection that can verify its
endpoints and cursor membership, SList obviously cannot) allows slicing
based on cursors in a limited fashion. Therefore, this allows
constructing ranges from cursors if you have the original container.
As an example of what this could allow (assuming retro and take forward
the begin(), end() and last() methods):
container.remove(take(retro(container[]), 5)); // remove the last 5
elements from the container.
I understand and I see the advantages. Still I believe that the
disadvantages of dealing with cursors overcome this potential
flexibility. I'd be more inclined to look for a design for which ranges
suffice for iteration.
Andrei
