std.container & ranges

[Steven Schveighoffer]

On Mon, 31 Oct 2011 12:40:37 -0400, Dmitry Olshansky  
<dmitry.olsh at gmail.com> wrote:

> 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.

That could also be added (and I agree it's a good idea).  Alas, interface  
templates still don't work, so it'd have to be defined as a convention.

Note that this isn't really the intended usage for purge (though it works  
quite nicely as an afterthought).  Typically, when I use purge, I'm  
iterating through all the elements, processing them somehow, and then  
deciding to remove them or not based on the processing.

For instance, a main thread processing results from sub-threads, and  
removing ones that are finished.

Think of it as an implementation of Java's Iterator.remove:

http://download.oracle.com/javase/7/docs/api/java/util/Iterator.html#remove()

-Steve