October 07, 2012
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
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
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
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
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
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
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
1 2
Next ›   Last »