std.container & ranges

[Dmitry Olshansky]

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.

>
> What do you think of an construct like this:
>
> foreach(item, itemRange; container)
> {
> // itemRange is a range only containing item
> // itemRange.length == 1&&  itemRange.front == item
> }

>
> That would be analogous to foreach over array with an index. You might think
> that iterating explicity may not be elegant. But it is what people want to
> do and it should not be any harder than necessary.
>

You still can, just use plain range interface with empty/front/popFront.
for(auto r = list[]; !r.empty; r.popFront())
{
	...
}


-- 
Dmitry Olshansky