October 07, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Attachments:
| On Sun, 2012-10-07 at 02:15 -0700, Jonathan M Davis wrote: […] > 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. 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? -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder@ekiga.net 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 |
October 07, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
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
|
October 07, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jonathan M Davis | 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
|
October 07, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jonathan M Davis | 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 |
October 09, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jonathan M Davis | 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 |
October 09, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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
|
October 09, 2012 Re: Remove element from DList | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jonathan M Davis | 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
|
Copyright © 1999-2021 by the D Language Foundation