www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - questions: remove from SList

reply enuhtac <enuhtac_lists gmx.de> writes:
Hello,

I have two issues removing items from a SList.
Consider following code:


import std.container;
import std.algorithm;

void main()
{
    SList!int a = [ 5, 4, 3, 2, 1 ];
    auto r = a[];
    remove( r, 2 ); // ERROR! Needed member function are not
                    // implemented by SList(T).Range
    a.remove( r );  // ERROR! There is no member function remove
}


* The call to algorithm.remove produces these error messages:

/usr/include/d/dmd/phobos/std/algorithm.d(5951): Error: src.front() is
not an lvalue
/usr/include/d/dmd/phobos/std/algorithm.d(5951): Error: tgt.front() is
not an lvalue
/usr/include/d/dmd/phobos/std/algorithm.d(5954): Error: no property
'popFrontN' for type 'Range'
/usr/include/d/dmd/phobos/std/algorithm.d(5956): Error: no property
'popBack' for type 'Range'

I would presume that phobos algorithms should work for all phobos
containers, right? - At least if the prerequisites are met. The relevant
prerequisite for this version of "remove" is "isForwardRange!Range"
which is clearly the case for SList(T).Range. Nevertheless "remove"
tries to access "popFrontN" and "popBack" which are not part of the
ForwardRange specification. The lvalue-errors are another issue.
I would clearly say this implementation of remove is buggy - or am I wrong?

* The second call to remove does not succeed because there is no member
function "remove". Instead there is "linearRemove". This is not a bug of
course. But if I want to write code that uses some unspecific container
it is very inconvenient that instead of "remove" I might have to call
"linearRemove" or "stableRemove". Why not add a simple

alias linearRemove remove ?

This is sensible as "linearRemove" is a specialization of "remove". So
the general function "remove" would always be present but the
specialized function "linearRemove" or "stableRemove" would only be
present if it makes sense for the specific container.

Regards,
enuhtac
Oct 11 2011
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 11 Oct 2011 05:19:41 -0400, enuhtac <enuhtac_lists gmx.de> wrote:


 Hello,

 I have two issues removing items from a SList.
 Consider following code:


 import std.container;
 import std.algorithm;

 void main()
 {
     SList!int a = [ 5, 4, 3, 2, 1 ];
     auto r = a[];
     remove( r, 2 ); // ERROR! Needed member function are not
                     // implemented by SList(T).Range
     a.remove( r );  // ERROR! There is no member function remove
 }


 * The call to algorithm.remove produces these error messages:

 /usr/include/d/dmd/phobos/std/algorithm.d(5951): Error: src.front() is
 not an lvalue
 /usr/include/d/dmd/phobos/std/algorithm.d(5951): Error: tgt.front() is
 not an lvalue
 /usr/include/d/dmd/phobos/std/algorithm.d(5954): Error: no property
 'popFrontN' for type 'Range'
 /usr/include/d/dmd/phobos/std/algorithm.d(5956): Error: no property
 'popBack' for type 'Range'

 I would presume that phobos algorithms should work for all phobos
 containers, right? - At least if the prerequisites are met. The relevant
 prerequisite for this version of "remove" is "isForwardRange!Range"
 which is clearly the case for SList(T).Range. Nevertheless "remove"
 tries to access "popFrontN" and "popBack" which are not part of the
 ForwardRange specification. The lvalue-errors are another issue.
 I would clearly say this implementation of remove is buggy - or am I  
 wrong?


Yes, I'd agree either remove's implementation or its constraint  
specification are buggy.  It should not specify that it needs a forward  
range and then use bi-directional range primitives.

However, I don't think std.algorithm.remove does what you want, I think it  
moves data that is not desired to the end of the range (not exactly sure).


 * The second call to remove does not succeed because there is no member
 function "remove". Instead there is "linearRemove". This is not a bug of
 course. But if I want to write code that uses some unspecific container
 it is very inconvenient that instead of "remove" I might have to call
 "linearRemove" or "stableRemove". Why not add a simple

 alias linearRemove remove ?


The exact point of why SList contains linearRemove and not remove is so  
that code which expects sub-linear remove function will not compile for  
SList, because SList does not support quick removal.  Aliasing remove to  
linearRemove would defeat the purpose of using function names to imply  
complexity and side-effects, which is one of the main charters of  
std.container.

There's always dcollections ;)

http://www.dsource.org/projects/dcollections

-Steve
Oct 11 2011
parent reply kennytm <kennytm gmail.com> writes:
"Steven Schveighoffer" <schveiguy yahoo.com> wrote:


 Yes, I'd agree either remove's implementation or its constraint 
 specification are buggy.  It should not specify that it needs a forward 
 range and then use bi-directional range primitives.
 


I think remove's constraint is fine. With a SList you don't really want to
remove the current node, but the 'next' node. SList should provide the O(1)
removeNext and insertNext functions (c.f. C++11's std::forward_list).
Oct 11 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 11 Oct 2011 13:29:02 -0400, kennytm <kennytm gmail.com> wrote:


 "Steven Schveighoffer" <schveiguy yahoo.com> wrote:


 Yes, I'd agree either remove's implementation or its constraint
 specification are buggy.  It should not specify that it needs a forward
 range and then use bi-directional range primitives.


 I think remove's constraint is fine. With a SList you don't really want  
 to
 remove the current node, but the 'next' node. SList should provide the  
 O(1)
 removeNext and insertNext functions (c.f. C++11's std::forward_list).


See the definition of std.algorithm.remove here:

https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm.d#L5927

And see line 5956 which uses popBack on the range which is determined not  
to be a bidirectional range.

Looking at the code, I'd say the bug is simply that remove is overloaded  
for forward ranges.  I'd remove this whole overload.

But your points on SList are valid -- a linked list of any kind that does  
not support O(1) removal or insertion is DOA.

-Steve
Oct 12 2011