std.partition is fucked

Andrei Alexandrescu SeeWebsiteForEmail at
Wed May 13 21:13:58 PDT 2009

Steven Schveighoffer wrote:
> 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.

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.


More information about the Digitalmars-d mailing list