Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]

Subject: Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]
From: Scott McMurray (me22.ca+boost_at_[hidden])
Date: 2009-08-05 13:14:55

2009/8/5 Andrei Alexandrescu <andrei_at_[hidden]>:
> Scott McMurray wrote:
>>
>> On a related note, how would I, using ranges, sort only the first half
>> of a partition? Â It appears I can only get a range for the second
>> half[2]. Â In code, I'm looking for the equivalent of sort(b,
>> partition(b, e, pred));
>
> I made partial sorting available for random-access ranges (just like STL).
> For those it's easy to select the first half (e.g. in D by using r[0 ..
> r.length / 2]).
>

Sorry, that was unclear of me.  When I said "half" I meant "the
contiguous subsequence at the from of the original range in which the
predicate is true".  It looks like I have to do this (guessing at D
syntax):

falsepart = partition(r, pred);
sort(r[0 .. r.size()-falsepart.size()]);

Is there a more elegant way to do that?  I don't have confidence that
I haven't made an off-by-one error.  Also, I presume partition works
on bidirectional ranges for which I cannot use [] to get the range
where the predicate is true.  What if I wanted to run a
bottom_up_merge_sort function on the "predicate is true" subrange of
my list, for example?

In short, it feels like partition should be returning a pair of ranges.

(Though I haven't thought all the way through sentinel-terminated
ranges and such.  But I suppose they aren't bidirectional in the first
place.)