std.container & ranges

[Jonathan M Davis]

On Monday, October 31, 2011 13:16:11 Dmitry Olshansky 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.

Probably because it has to swap elements around, which requires a 
bidirectional range.

> Or SList could be special enough to offer a built-in remove with
> predicate done in O(n).

It would be valuable in general IMHO. We should add something similar to the 
STL's remove_if function on linked lists. The fact that std.algorith.remove 
must shuffle elements around instead of actually removing them (similar to what 
the STL does with its free function erase) just shows how it doesn't really 
work all that well. It can be done _much_ more efficiently by putting remove_if 
(or whatever we would call it) on the container. It's also less confusing, 
since std.algorithm.remove (and the STL's erase function) doesn't actually 
_anything_. You have to pass the returned range (or iterator in C++) to the 
container's linearRemove function (or erase in C++) to remove the elements, 
which is _highly_ confusing (but since iterators and ranges don't really know 
about their containers beyond the elements that they reference, it's the best 
that can be done with a free function).

For the case where you're searching for a specific element to remove though, I 
see no reason to add another function. That's what find is for (and given that 
we have lambdas, it's easy to use even in the case where you need a predicate 
other than ==), and if you really want to, you can iterate the range 
explicitly and pass the portion of the range to the container's remove 
function that you want to remove. The main problem with it is that we don't 
have proper examples, and we don't have enough documentation explaining ranges 
in general, so it's not immediately obvious to people how to properly use a 
container's remove function.

- Jonathan M Davis