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 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
prev sibling next sibling parent "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
prev sibling next sibling parent 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
prev sibling 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 next sibling parent "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
prev sibling next sibling 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 next sibling parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=

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

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

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=

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

 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=

 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 =

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

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

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

 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=

 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.
=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 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 next sibling parent Russel Winder <russel winder.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 =

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

 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 next 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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling 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