Sean Kelly wrote:

> == Quote from Lutger (lutger.blijdestijn@gmail.com)'s article
>>
>> Some time ago I reinvented these wheels for study purpose. A custom stack was a little faster but not
> that much. std.swap can't be inlined because it uses ref params, that cost also a bit since it's called
>> many times. Switching to another sort if a certain recursion depth is reached helped, but mostly in
> degenerate cases.
>> I still have the thing somewhere, it is about twice as fast as builtin sort. It's not a lot of work but I could
> dig it up and provide some timings if you want.
> 
> The sort I wrote for Tango uses the same basic heuristics, thanks to a ticket that either you or Stewart Gordon submitted long ago.  I've been meaning to compare it against the sort routine in std.algorithm to see whether the Phobos routine could benefit from any of the same tweaks.

It wasn't me, I used the Tango code as one the sources to study this algorithm :)

On Wed, 13 May 2009 17:17:33 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Partition is in fact the perfect example because it works with forward
> ranges. If you want to partition a singly-linked list, you'd have to
> return the right-hand sublist. There's nothing else you could possibly
> return! If you wanted to return the left-hand sublist, you'd have to
> return a different type of range (something like "list up to this node").
>

It depends on if the sentinel is static.

For example, it would be perfectly legal to specify a linked list as the nodes between node x and y, where y is null at runtime in the case of a full list.  I'm not even sure the performance would suffer significantly.

dcollections' linked list is a doubly linked list, but I use a sentinel dummy element to denote both the beginning and the end.  It makes insertion/deletion code completely uniform because there is *always* a valid previous and next node for each node.  No checking for "if this is the head node, update the original list pointer"

Not being able to return a subrange of a container as fundamental as a linked list is a pretty significant oversight in my opinion.

-Steve

Steven Schveighoffer wrote:
> On Wed, 13 May 2009 17:17:33 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> 
>> Partition is in fact the perfect example because it works with forward
>> ranges. If you want to partition a singly-linked list, you'd have to
>> return the right-hand sublist. There's nothing else you could possibly
>> return! If you wanted to return the left-hand sublist, you'd have to
>> return a different type of range (something like "list up to this node").
>>
> 
> It depends on if the sentinel is static.
> 
> For example, it would be perfectly legal to specify a linked list as the nodes between node x and y, where y is null at runtime in the case of a full list.  I'm not even sure the performance would suffer significantly.
> 
> dcollections' linked list is a doubly linked list, but I use a sentinel dummy element to denote both the beginning and the end.  It makes insertion/deletion code completely uniform because there is *always* a valid previous and next node for each node.  No checking for "if this is the head node, update the original list pointer"
> 
> Not being able to return a subrange of a container as fundamental as a linked list is a pretty significant oversight in my opinion.

Well it's not quite an oversight because I was well aware of the issue. The only thing is, I started with the narrowest interface I could to figure how far I can get. Primitives can be added to select range categories as needed.

Andrei