On Tue, 22 Feb 2011 05:55:20 +0300, Jonathan M Davis <jmdavisp...@gmx.com>
wrote:
Okay, removing elements from a container sucks right now. You can do
stuff like
removeAny (generally pretty useless IMHO) or removeFront just fine, but
removing
an arbitrary range from a container just plain sucks.
remove takes a range type which is the range type for the container that
it's
on. That makes sense. It's obviously not going to be able to a take an
arbitrary
range and remove that from itself. How would it know which elements in
that
range corresponded to which elements in itself - especially when it
could be a
range which skips elements or something similar? So, _that_ part makes
sense.
But have you actually tried to get a range of the appropriate type to
remove
from a container? It seems like almost ever function in std.range and
std.algorithm returns a new range type, making them completely useless
for
processing a range to be removed from a container.
I was looking to remove a single element for a RedBlackTree. The best
function
that I could think to get the proper range was findSplit. The middle
portion of
the return value would be the portion that I was looking for. I'd take
that and
pass it to RedBlackTree's remove. Wrong. It uses takeExactly in its
implementation and the first two portions of the result of findSplit
aren't the
right range type.
So, what do I do? The _only_ thing that I can think of at the moment is
to use
find to locate the beginning of the range that I want, take the length
of the
range with walkLength and then use popBackN to pop of the elements I
don't want.
e.g.
======
import std.algorithm, std.container, std.conv,
std.range, std.stdio;
void main()
{
auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");
auto found = find(rbt[], 5);
assert(to!string(found) == "[5, 12, 22, 59]");
popBackN(found, walkLength(found) - 1);
assert(to!string(found) == "[5]");
rbt.remove(found);
assert(to!string(rbt[]) == "[0, 2, 12, 22, 59]");
}
======
That's disgusting. All that just to remove one element? And what if the
range
isn't bidirectional (e.g. SList)? Well, then you have no popBack, and as
far as
I can tell, you're screwed, since you can't use either take or
takeExactly,
because both of them return new range types.
In particular, the fact that you can't take a range and create a new one
of the
same type from its first n elements is highly problematic. Maybe we need
to add a
function to ForwardRange which returns a new range with the first n
elements (it
certainly looks like that's the key element that's missing here). I
don't know
if that would be reasonable, but the fact that you can't create a range
of the
same type as the original range when taking just its first n elements
seems
crippling in this situation.
I don't know what the proper solution to this is, but the current
situation
strikes me as untenable. I had to think through this problem for a while
before
I came to a solution that came even close to working, let alone get one
that
actually works. Removing elements from a container should _not_ be this
hard.
The situation with remove _needs_ to be improved.
- Jonathan M Davis
I believe remove operation is better expressed in terms of a Cursor
(iterator in C++). It also doesn't make much sense (at least of me) for a
find to return a subrange of the source range. While it does generalize
well, it's not really what most people expect.
What I'd love to have instead is something like this:
int[] arr = [1, 2, 3, 4, 5];
auto cursor = arr.find(3); // either points to 3 or null
int[] before = arr[0..cursor];
int value = arr[cursor]; // for consistency, C++ uses *cursor
int[] after = arr[arr.advance(cursor)..$];
Note that typeof(cursor) could/should actually be int*, but I don't use
arr[cursor+1..$] because cursor doesn't know about range bounds, and as
such it can't advance on it's own.
For dynamic arrays:
V[K] dynamicArray;
V* cursor = key in dynamicArray;
dynamicArray.remove(key); // requires an additional lookup, which is
sub-optimal
// dynamicArray.remove(cursor); // optimal but doesn't work atm. I think
it should
I think it's also worth noting that "find" for trees makes even less sense
(to me). You can't "slice" a tree arbitrarily, yet find tries to do that:
auto rbt = RedBlackTree!int([0, 2, 5, 12, 59, 22]);
assert(to!string(rbt[]) == "[0, 2, 5, 12, 22, 59]");
auto found = find(rbt[], 5);
assert(to!string(found) == "[5, 12, 22, 59]");
What is the type of "found"? It's clearly not a tree anymore. Don't know
why, but it's still a range. How is it implemented? Without looking at the
source I can tell it's implemented as an original tree + a cursor. And I
believe the two are better be separated.
As a side note, in my own code I have 2 version of remove - remove and
removeUnstable, which work differently. Simple example:
// swaps current element with last one and pops last
void removeUnstable(T)(ref T[] array, T* cursor)
{
auto length = array.length;
assert(length > 0);
--length;
T* last = array.ptr + length;
assert(array.ptr <= cursor && cursor <= last);
*cursor = *last;
array.length = length;
}
// Moves elements
T* remove(T)(ref T[] array, T* cursor)
{
auto length = array.length;
assert(length > 0);
--length;
assert(array.ptr <= cursor && cursor <= array.ptr + length);
auto numElementsToMove = length - (cursor - array.ptr);
memmove(cursor, cursor + 1, numElementsToMove * T.sizeof);
array.length = length;
return cursor;
}
