On Sunday, December 30, 2012 15:59:01 d coder wrote:
> Greetings
> 
> I have created a DList of class objects. Now I want to delete a particular object from the list. I do not see a straightforward way of doing that. The only way I found was to create a DList range, take out all other elements from the range using popFront and popBack and then apply remove(Range).
> 
> Am I missing something?

You should be able to do something like

list.stableRemove(take(find(list[], 5), 3));

or if you prefer UFCS

list.stableRemove(list[].find(5).take(3));

A more detailed example would be

import std.algorithm;
import std.container;
import std.range;
import std.stdio;

void main()
{
    auto list = make!(DList!int)([2, 9, 14, 22, 7, 64, 5]);
    assert(equal(list[], [2, 9, 14, 22, 7, 64, 5]));

    auto found = find(list[], 14);
    assert(equal(found, [14, 22, 7, 64, 5]));

    auto toRemove = take(found, 3);
    assert(equal(toRemove, [14, 22, 7]));

    list.linearRemove(toRemove);
    assert(equal(list[], [2, 9, 64, 5]));
}

For some reason, DList's remove function won't accept the result of take, so you have to use linearRemove. But in general, the functions in std.container which take the range type of the container that the function is on should accept the result of take, takeExactly, and takeOne. If they don't (and some don't yet), then it's a bug. And the remove functions generally take the range type of their container, so you use find to find the element that you want and one of the take functions to create a range with only the elements that you want to remove rather than every element starting at the element that you were searching for.

- Jonathan M Davis


P.S. This sort of question really should be asked in D.Learn. This newsgroup is for general discussions about the language, not for questions on how to use aspects of the language or the standard library.

Ok, I thought I found the answer in an earlier thread http://forum.dlang.org/thread/lozpofrboxsfybmhkhch@forum.dlang.org

auto range = find(list[], elem);
list.remove(take(range, 1));

But it does not work. Gives me:

Error: function std.container.DList!(Foo).DList.remove (Range r) is not
callable using argument types (Take!(Range))
Error: cannot implicitly convert expression (take(range, 1LU)) of type
Take!(Range) to Range

I get similar issues if I try using std.algorithm.filter instead of find.

I am using latest DMD snapshot from github.

Regards
- Puneet

Thanks Jonathan.

On Sunday, December 30, 2012 16:18:18 d coder wrote:
> Ok, I thought I found the answer in an earlier thread http://forum.dlang.org/thread/lozpofrboxsfybmhkhch@forum.dlang.org
> 
> auto range = find(list[], elem);
> list.remove(take(range, 1));
> 
> But it does not work. Gives me:
> 
> Error: function std.container.DList!(Foo).DList.remove (Range r) is not
> callable using argument types (Take!(Range))
> Error: cannot implicitly convert expression (take(range, 1LU)) of type
> Take!(Range) to Range
> 
> I get similar issues if I try using std.algorithm.filter instead of find.
> 
> I am using latest DMD snapshot from github.

For some reason, remove doesn't support take like it should, but linearRemove does. However, filter will never work. The remove function must operate on a range which refers to specific elements in the container, not a range which happens to hold elements which match elements in the container, so it needs either the exact range type that it gives you with opSlice or a range that it can recognize as wrapping the range type that it gives you. filter returns a range that no container recognizes, and its very nature means that the range won't necessarily hold a contiguous set of elements from the container, making it very problematic in general for the container functions to try and recognize it as being a wrapper around one of their ranges and operate on it.

At this point, only the exact range type or the result of take* on the exact range type is going to work (and if any of those don't remove for a container's remove* function, then it's a bug). Some other range wrapper types (e.g. retro) may end up being recognized in the future, but the list of range wrapper types supported by std.container is likely to be very small - primarily to what's required to reasonably get the slice you need from one of its ranges. Transformative and filtering ranges are unlikely to ever be supported.

- Jonathan M Davis

On Sunday, 30 December 2012 at 10:58:38 UTC, Jonathan M Davis wrote:
> On Sunday, December 30, 2012 16:18:18 d coder wrote:
> For some reason, remove doesn't support take like it should, but linearRemove does.
>
> [SNIP]
>
> - Jonathan M Davis

That's because remove guarantees o(1), whereas linearRemove is allowed to operate in o(N).*

Removing a DListRange is o(1)

To remove a "take" range, one must first walk the source range until you have extracted the eauivalent DListRange, which is a o(N)operation.

Forcing you to use the word "linearRemove" guarantees you know what you are paying for.

That is the how and why.

--------
As a matter of fact, std.algorithm.Array doesn't even have "remove" for exactly this reason, but it does have "linearRemove". Trying to call Array.remove will actually result in a weird-ass error because the compiler thinks you are calling std.algorithm.remove, but you may not immediately realize that nor what the compiler is complaining about...

--------
*The whole thing is a little inconsistent because "insert" may or may not be linear but there is no "linearInsert" variant. Guess this is to avoid things like "linearStableInsertBefore".

As for remove, according to the "top doc", the complexities are actually:
c.remove(r) 	        O(nr * log nc)
c.linearRemove(r) 	O(nc)
So technically, remove could accept a take!Range... but I think having a generalized complexity is wishful thinking, each container should define its own complexities.

--------
One last thing, avoid using the "stable" versions of remove. Appart from Slist's stableRemoveFront, NONE of them are actually stable (stable = "guarantees that ranges iterating over the container are never invalidated"). And even, then, that's because SList has a weird design, which I think may end up getting "fixed" ...