www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Remove element from DList

reply "cal" <callumenator gmail.com> writes:
I'd like to remove a single element from a std.container.DList. 
For that I need a range, but I'm not sure how to get a single 
element 'range'.

I thought something like this might work:

auto list = DList!int([1,2,3,4]);
auto r = list[];
while(r.front != 3)
    r.popFront;

list.remove(r.take(1));

But the the range returned by r.take(1) is not valid as an 
argument to DList.remove. What is the correct way to do this?
Oct 06 2012
next sibling parent "cal" <callumenator gmail.com> writes:
On Saturday, 6 October 2012 at 21:39:29 UTC, cal wrote:

 I'd like to remove a single element from a std.container.DList. 
 For that I need a range, but I'm not sure how to get a single 
 element 'range'.

 I thought something like this might work:

 auto list = DList!int([1,2,3,4]);
 auto r = list[];
 while(r.front != 3)
    r.popFront;

 list.remove(r.take(1));

 But the the range returned by r.take(1) is not valid as an 
 argument to DList.remove. What is the correct way to do this?


One solution:
list.linearRemove(list[].find(3).takeOne);
Oct 06 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Saturday, October 06, 2012 23:27:31 cal wrote:

 I'd like to remove a single element from a std.container.DList.
 For that I need a range, but I'm not sure how to get a single
 element 'range'.
 
 I thought something like this might work:
 
 auto list = DList!int([1,2,3,4]);
 auto r = list[];
 while(r.front != 3)
     r.popFront;
 
 list.remove(r.take(1));
 
 But the the range returned by r.take(1) is not valid as an
 argument to DList.remove. What is the correct way to do this?


The correct way is to use find combined with take (which is what you're doing, 
except that you're not using find). So, something like this should work

void main()
{
    auto list = DList!int([1,2,3,4]);
    list.remove(find(list[], 3).take(1));
}


However, for some reason, this is indeed not working right now. It's a bug. 
Please report it.

But! If you use linearRemove, it _does_ work.

void main()
{
    auto list = DList!int([1,2,3,4]);
    list.linearRemove(find(list[], 3).take(1));
}

I have no idea why remove doesn't work with take (because it's supposed to), 
and I have no idea why remove isn't an alias to linearRemove (or vice versa). 
I would have thought that they'd be one and the same for linked lists, but 
maybe I'm missing something, since I haven't spent a lot of time thinking 
about it.

Regardless, report it as a bug. Using take on the range returned by a 
container should work for _all_ of the various remove functions for _all_ 
containers in std.container. If it doesn't, it's a bug.

- Jonathan M Davis
Oct 06 2012
parent reply "cal" <callumenator gmail.com> writes:
On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:

 The correct way is to use find combined with take (which is 
 what you're doing,
 except that you're not using find). So, something like this 
 should work

 void main()
 {
     auto list = DList!int([1,2,3,4]);
     list.remove(find(list[], 3).take(1));
 }


 However, for some reason, this is indeed not working right now. 
 It's a bug.
 Please report it.


SList doesn't implement remove, so perhaps DList can only 
guarantee the required complexity when given the range defined in 
DList, and for other types of ranges, it can only guarantee 
linear complexity?
Oct 06 2012
next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, October 07, 2012 04:14:58 cal wrote:

 On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis wrote:

 The correct way is to use find combined with take (which is
 what you're doing,
 except that you're not using find). So, something like this
 should work
 
 void main()
 {
 
     auto list = DList!int([1,2,3,4]);
     list.remove(find(list[], 3).take(1));
 
 }
 
 
 However, for some reason, this is indeed not working right now.
 It's a bug.
 Please report it.


 
 SList doesn't implement remove, so perhaps DList can only
 guarantee the required complexity when given the range defined in
 DList, and for other types of ranges, it can only guarantee
 linear complexity?


singly-linked lists and doubly-linked lists are completely different beasts. A 
singly-linked list can't do it sanely, because it has to traverse the list to 
find the previous node so that it adjust the links. A node in a doubly-linked 
list has a link to the previous node in the list instead of just the next 
node, so it doesn't have that problem. You can add and remove elements from 
anywhere in a doubly-linked list in O(1). And if you're dealing with 
iterators, it won't affect any iterators except if they point at the element 
being removed (so it's a stable remove). With ranges, it would affect the 
elements in the range, but unless you're removing an element which is at the 
front or end of a range, it shouldn't invalidate the range at all. And that 
can be gotten around by letting that node continue to exist and point to what 
was the next node in the list (in which case, it would go away once no more 
ranges referred to it - the GC makes doing that fairly easy).

So, I don't see any reason why remove wouldn't be stable or non-linear. It's 
actually kind of hard to make it _un_stable in this case. And actually, 
looking at the code, stableLinearRemove (and linearRemove is an alias for 
stableLinearRemove in this case) calls remove, so overall, this is a bit 
bizarre. Regardless, it's a bug that normal remove doesn't work with the 
result of take.

- Jonathan M Davis
Oct 06 2012
next sibling parent "cal" <callumenator gmail.com> writes:
On Sunday, 7 October 2012 at 02:54:44 UTC, Jonathan M Davis wrote:

 On Sunday, October 07, 2012 04:14:58 cal wrote:

 On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis 
 wrote:

 The correct way is to use find combined with take (which is
 what you're doing,
 except that you're not using find). So, something like this
 should work
 
 void main()
 {
 
     auto list = DList!int([1,2,3,4]);
     list.remove(find(list[], 3).take(1));
 
 }
 
 
 However, for some reason, this is indeed not working right 
 now.
 It's a bug.
 Please report it.


 
 SList doesn't implement remove, so perhaps DList can only
 guarantee the required complexity when given the range defined 
 in
 DList, and for other types of ranges, it can only guarantee
 linear complexity?


 singly-linked lists and doubly-linked lists are completely 
 different beasts. A
 singly-linked list can't do it sanely, because it has to 
 traverse the list to
 find the previous node so that it adjust the links. A node in a 
 doubly-linked
 list has a link to the previous node in the list instead of 
 just the next
 node, so it doesn't have that problem. You can add and remove 
 elements from
 anywhere in a doubly-linked list in O(1). And if you're dealing 
 with
 iterators, it won't affect any iterators except if they point 
 at the element
 being removed (so it's a stable remove). With ranges, it would 
 affect the
 elements in the range, but unless you're removing an element 
 which is at the
 front or end of a range, it shouldn't invalidate the range at 
 all. And that
 can be gotten around by letting that node continue to exist and 
 point to what
 was the next node in the list (in which case, it would go away 
 once no more
 ranges referred to it - the GC makes doing that fairly easy).

 So, I don't see any reason why remove wouldn't be stable or 
 non-linear. It's
 actually kind of hard to make it _un_stable in this case. And 
 actually,
 looking at the code, stableLinearRemove (and linearRemove is an 
 alias for
 stableLinearRemove in this case) calls remove, so overall, this 
 is a bit
 bizarre. Regardless, it's a bug that normal remove doesn't work 
 with the
 result of take.

 - Jonathan M Davis


Righto, i'll put in a ticket, thanks for the help.
Oct 06 2012
prev sibling parent reply "cal" <callumenator gmail.com> writes:
 On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis 
 wrote:
 Regardless, it's a bug that normal remove doesn't work with the 
 result of take.


I guess this is also true of insertAfter and co? Should they 
accept the result of take? (Currently they don't)
Oct 06 2012
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, October 07, 2012 06:54:25 cal wrote:

 On Sunday, 7 October 2012 at 01:14:48 UTC, Jonathan M Davis
 wrote:
 Regardless, it's a bug that normal remove doesn't work with the
 result of take.


 
 I guess this is also true of insertAfter and co? Should they
 accept the result of take? (Currently they don't)


Any function on a container in std.container which takes a range from that 
container should accept the result of take or takeExactly. It's something that 
was overlooked in the initial design and added later, so it hasn't necessarily 
been added consistently. But without it, those functions can't operate on the 
an element or elements in a range without operating on every element after 
them in the entire container.

- Jonathan M Davis
Oct 06 2012
prev sibling parent Russel Winder <russel winder.org.uk> writes:
On Sat, 2012-10-06 at 19:42 -0700, Jonathan M Davis wrote:
[=E2=80=A6]

 singly-linked lists and doubly-linked lists are completely different beas=


ts. A=20

 singly-linked list can't do it sanely, because it has to traverse the lis=


t to=20

 find the previous node so that it adjust the links. A node in a doubly-li=


nked

Not sure about the D implementation, but in other languages all the
singly-linked list iterator has to do to allow for removal is to
maintain a "front foot"/"back foot" state. This is needed for insert as
well, so it is already there.


 list has a link to the previous node in the list instead of just the next=


=20

 node, so it doesn't have that problem. You can add and remove elements fr=


om=20

 anywhere in a doubly-linked list in O(1). And if you're dealing with=20
 iterators, it won't affect any iterators except if they point at the elem=


ent=20

 being removed (so it's a stable remove). With ranges, it would affect the=


=20

 elements in the range, but unless you're removing an element which is at =


the=20

 front or end of a range, it shouldn't invalidate the range at all. And th=


at=20

 can be gotten around by letting that node continue to exist and point to =


what=20

 was the next node in the list (in which case, it would go away once no mo=


re=20

 ranges referred to it - the GC makes doing that fairly easy).


Removal from a singly-linked list can be O(1) as well, it depends
whether you are deleting using an iterator in progress.


 So, I don't see any reason why remove wouldn't be stable or non-linear. I=


t's=20

 actually kind of hard to make it _un_stable in this case. And actually,=


=20

 looking at the code, stableLinearRemove (and linearRemove is an alias for=


=20

 stableLinearRemove in this case) calls remove, so overall, this is a bit=


=20

 bizarre. Regardless, it's a bug that normal remove doesn't work with the=


=20

 result of take.
=20
 - Jonathan M Davis


--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Oct 07 2012
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:

 Removal from a singly-linked list can be O(1) as well, it depends
 whether you are deleting using an iterator in progress.


IIRC that dcollections' singly-linked list is like this, but 
std.container.SList definitely isn't. I'm not a big fan of singly-linked lists 
in the first place and tend to think that they're useless, but std.container's 
is particularly bad in that regard.

- Jonathan M Davis
Oct 07 2012
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 10/7/12 5:15 AM, Jonathan M Davis wrote:

 On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:

 Removal from a singly-linked list can be O(1) as well, it depends
 whether you are deleting using an iterator in progress.


 IIRC that dcollections' singly-linked list is like this, but
 std.container.SList definitely isn't. I'm not a big fan of singly-linked lists
 in the first place and tend to think that they're useless, but std.container's
 is particularly bad in that regard.


Singly-linked lists are limited in functionality as containers, but very 
fast for a few applications. It's quite likely someone would choose a 
singly-linked list primarily for performance.

Some more functionality could be implemented for SList if it used for 
its range a pointer pointing one before the first element. But that 
would have meant an extra indirection for each and every access, undoing 
a large fraction of performance benefits. That's why I chose the 
primitives the way I did.


Andrei
Oct 07 2012
prev sibling next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 10/07/2012 02:15 AM, Jonathan M Davis wrote:


 not a big fan of singly-linked lists


They can be useful as hash table buckets. They are efficient in that 
application especially if they do not have the overhead of a length member.

Ali
Oct 07 2012
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sun, 07 Oct 2012 05:15:05 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Sunday, October 07, 2012 10:09:06 Russel Winder wrote:

 Removal from a singly-linked list can be O(1) as well, it depends
 whether you are deleting using an iterator in progress.


 IIRC that dcollections' singly-linked list is like this


dcollections does not have singly-linked lists.


 , but
 std.container.SList definitely isn't. I'm not a big fan of singly-linked  
 lists
 in the first place and tend to think that they're useless, but  
 std.container's
 is particularly bad in that regard.


They are definitely not useless.  But IMO, they are difficult to write in  
a generic way.  Typically they are very tightly coupled to whatever it is  
you need them for.  If you are using singly linked lists, it's because  
doubly-linked lists are too bloated, or cannot implement what you are  
trying to do, so there is already a necessary optimization based on your  
particular situation that is difficult to provide as a generic container.

But I agree a singly linked list is near useless without O(1) removal.  I  
think that there has been some improvement in SList in that regard  
though...

-Steve
Oct 09 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, October 09, 2012 10:29:46 Steven Schveighoffer wrote:

 dcollections does not have singly-linked lists.


My mistake. I thought that you had said that it did in previous discussions on 
this topic.

- Jonathan M Davis
Oct 09 2012
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 09 Oct 2012 13:51:09 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:


 On Tuesday, October 09, 2012 10:29:46 Steven Schveighoffer wrote:

 dcollections does not have singly-linked lists.


 My mistake. I thought that you had said that it did in previous  
 discussions on
 this topic.


I decided early on that all dcollections objects would be forward and  
backwards traversable.  Not based on any studies or anything, I just found  
it to be easier to create interfaces that can always assume this.

Naturally, this precludes singly linked lists.  This doesn't mean I can't  
change my mind or accept code that does use SLL, or even accept containers  
that are not traversable backwards, but I think it helps to always know  
they are all bidirectional.

-Steve
Oct 09 2012
prev sibling next sibling parent Russel Winder <russel winder.org.uk> writes:
On Sun, 2012-10-07 at 02:15 -0700, Jonathan M Davis wrote:
[=E2=80=A6]

 IIRC that dcollections' singly-linked list is like this, but=20
 std.container.SList definitely isn't. I'm not a big fan of singly-linked =


lists=20

 in the first place and tend to think that they're useless, but std.contai=


ner's=20

 is particularly bad in that regard.


I guess I like closed queues for which singly-linked lists are fine.

Is there a rationale for having multiple implementation of the same data
structure, one in druntime and the other in std.container?

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Oct 07 2012
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday, October 07, 2012 12:54:00 Russel Winder wrote:

 Is there a rationale for having multiple implementation of the same data
 structure, one in druntime and the other in std.container?


Which data structure are you takling about? I'm not aware of anything in 
std.container being in druntime at all.

- Jonathan M Davis
Oct 07 2012