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. Â 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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk