On Thu, Oct 1, 2015 at 4:50 AM, Roland Bock
On 2015-10-01 16:24, Marshall Clow wrote:
In Sean Parent's CppCon keynote last week, he went through the process of implementing an algorithm he called "sort_subrange", which takes four iterators describing two ranges, one a subset of the other, and sorts the subrange - as if you had sorted the entire range. (See https://www.youtube.com/watch?v=sWgDk-o-6ZE, starting at about 31:30).
I have implemented this in Boost.Algorithm (crediting Sean) - called partition_sort.
However, while I was doing this, I thought of a different algorithm; one that gathered all the elements into the subrange as if the entire range was sorted, but didn't actually do the sorting.
I've implemented that one, too - but I'm having a bit of trouble coming up with a name.
I've used "partition_subrange", but that not that clear. Sean has suggested "elements_in_subrange" and "elements_within_subrange".
Here's the declaration:
template
void partition_subrange ( Iterator first, Iterator last, Iterator sub_first, Iterator sub_last, Pred p) /// \brief Gather the elements of the subrange [sub_first, sub_last) that is /// inside the range [first, last) as if you had sorted the entire range.
Any suggestions?
Assuming that the elements in [first, sub_first) are also less or equal to the element at sub_first, this is quite similar to nth_element, isn't it? Then you could call it
mth_to_nth_element
Not too smooth, but it should be clear to anyone who knows about nth_element.
Yes, it effectively partitions the sequence into three parts. (Hmm... maybe I should call it "Gaul"). All the values "less" than sub_first, then the values "between" sub_first and sub_last, and then the values "after" sub_last. -- Marshall