std.partition is fucked

Steven Schveighoffer schveiguy at
Wed May 13 15:43:13 PDT 2009

On Wed, 13 May 2009 17:17:33 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at> 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.


More information about the Digitalmars-d mailing list