Subject: Re: [boost] Partial Sort and Partition with Ranges [was: Boostcon Keynote available]
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-08-05 13:55:50
Scott McMurray wrote:
> 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.
Not that I know of.
> Also, I presume partition works
> on bidirectional ranges for which I cannot use [] to get the range
> where the predicate is true.
partition requires bidirectional ranges but if you pass a random-access
range it gives you back a portion of it, which is also a random-access
range.
> 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.)
Interesting point. Partition actually works on forward ranges if no
stability is required. There are different algorithms that work best
depending on stability requirements. If you look at the implementation
of std.partition, you'll see that I use different algorithms for stable
vs. semistable vs. unstable partition. In particular, I don't know of
efficient stable partition for bidirectional ranges.
I could return two ranges *if* the range is bidirectional and the
partition is not stable; that would complicate the interface a bit by
spilling subtle realities about the algorithm into the client.
Note that if you know the length of the range, you can always use
take(n, range) to restrict a range to its first n elements. This, I
think, takes care of all situations of interest (if you have a range
that you don't know the length of *and* want to do bottom_up_merge_sort
on it, I guess that won't work).
Andrei