Sean Kelly wrote:
== Quote from Andrei Alexandrescu ([email protected])'s article
Sean Kelly wrote:
== Quote from Andrei Alexandrescu ([email protected])'s article
Sean Kelly wrote:
Andrei Alexandrescu wrote:
Note how the left edge of result follows the left edge of r, but the
right edge stays put because partition() returns the right-hand-side
range. r shrinks from both ends to exhaustion.
So all the elements that satisfy the predicate end up at the end of the
original range instead of the beginning? Was that an arbitrary choice,
or is there a reason for it?
The elements satisfying the predicate are at the beginning, see e.g. the
unittests. The range returned is (as always) the right-hand side, i.e.
the range containing the elements that don't satisfy the predicate.
Weird. I'd always thought that the standard behavior was the opposite.
That way partition could be passed a lessThan predicate and be used
for sorting. Though I guess you can just use a greaterThan predicate
instead.
Nono, lessThan is a binary predicate whereas partition takes a unary
predicate. The spec of partition is very simple: do whatever the hell it
takes to put elements e that satisfy pred(e) before elements that don't.
If you follow the way std.sort uses partition, you'll see that it passes
a unary predicate that compares for less than against the chosen pivot.
Okay, I think we're talking at cross-purposes :-) It seems we both agree
that partition should place the elements satisfying pred before those that
do not. And I should have been more clear about pred being a unary
function. In any case, what I'm wondering is why partition returns the
range representing the elements that do not satisfy pred. When I call
partition, wouldn't I be interested in the result containing the elements
that have satisfied the supplied predicate? Or does this cause problems
for the sort routine.
Oh, now I understand. Sorry.
As a general rule, when they could return either the left or the right
subrange of a range, functions in std.algorithm return the right range.
This is because sentinel-terminated ranges cannot express the
left-hand-side range.
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").
So for generality's sake, whenever you have a choice, return the
right-hand part of a range.
There is growing interest in defining additional ranges that express (at
a cost) things like "the portion of a singly-linked list starting at
node X and ending at node Y". For example, people want to do a find()
and then deal with the portion _before_ the found element. I'd love to
discuss that further, but I guess I'll have to wait for the d.next
newsgroup. :oD
Andrei
