std.container & ranges

[Steven Schveighoffer]

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)

:)

-Steve