On Mon, 31 Oct 2011 05:16:11 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 31.10.2011 11:16, Tobias Pankrath wrote:
Jonathan M Davis wrote:
find allows
you to do that just fine, and such a remove function would simply be
duplicating its functionality.
But this thread serves as a proof that it is not obvious and something
like
containers should be obvious to use. Deleting an element with a certain
value is a common task and should should not take
three function calls, with functions from three different modules.
You would be doing exactly the same thing in C++ except that it would
be
with an iterator rather than a range. You would use find to find the
iterator to the element that you wanted and then you'd pass that to the
list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.
How do you delete every occurence of v? Not just the first one? Is this
equally "easy" with find and take? I didn't find an easy way not
envolving a loop within 10 Minutes by reading the documentation.
It is, let's use remove from std.algorithm! ... though there is no
overload of remove for forward ranges ... crap, worthy of bugzilla
report. Or SList could be special enough to offer a built-in remove with
predicate done in O(n).
However this should work( yet because of apparent bug in SList it
doesn't). The bug is:
Line 1294 of std.container should be:
for (; !r.empty; r.popFront())
...
or it will remove the whole container.
Code:
import std.container, std.range;
import std.functional, std.algorithm, std.stdio;
void removeFromList(alias pred, T)(ref SList!T s)
{
static if(is(typeof(pred) == string))
alias unaryFun!pred Pred;
else
alias pred Pred;
for(auto r=s[]; !r.empty; )
{
if(Pred(r.front))
{
r = s.linearRemove(take(r,1));
continue;
}
else
r.popFront();
}
}
void main()
{
SList!int list(20, 30, 40, 50, 60); // will work with stock Phobos if
the first element % 20 != 0
removeFromList!"a % 20 == 0"(list);
writeln(list[]);
}
And more importantly, it still would be horribly slow O(N^2).
Personally, because of that I'd prefer hand-rolled intrusive
singly-linked list any time of day.
ahem, using dcollections:
foreach(ref doRemove, cell; &organism.purge)
doRemove = cell.x == x && cell.y == y;
complexity: O(n)
:)
-Steve
