Boost logo

Boost :

Subject: Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]
From: Scott McMurray ([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

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, gregod at, cpdaniel at, john at