std.partition is fucked

Sean Kelly sean at
Wed May 13 13:47:47 PDT 2009

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at's article
> Sean Kelly wrote:
> > == Quote from Andrei Alexandrescu (SeeWebsiteForEmail at'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.

More information about the Digitalmars-d mailing list