std.container & ranges

[Dmitry Olshansky]

On 31.10.2011 18:38, Steven Schveighoffer wrote:
> On Mon, 31 Oct 2011 05:16:11 -0400, Dmitry Olshansky
> <dmitry.olsh at 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)

While computer happily does O(n) work here, my brain screams in 
cognitive dissonance figuring out that this assignment actually does 
delete... meh voodoo through and through :)

I'd rather
organism.remove!((cell){ return cell.x == x && cell.y == y; })();
or something like that.
But it's not a question of form, but more of a missing stuff that should 
be there.

>
> :)
>
> -Steve


-- 
Dmitry Olshansky