On 2015-10-01 10: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)
Not sure if this helps with the naming, but I find the order of arguments here unintuitive. I feel that it ought to follow nth_element and have void partition_subrange ( Iterator first, Iterator sub_first, Iterator sub_last, Iterator last, Pred p) and, having done that, I immediately feel like it ought to be variadic and support arbitrarily many points to fix in sorted order void partition_subrange ( Iterator first, Iterator... nth, Iterator last, Pred p) or even void partition_subrange ( Iterator first, Range<Iterator> nth, Iterator last, Pred p) This is actually a thing I have wanted to do, for example when one wishes to distribute data amongst several processors such that each gets a contiguous (in sorted order) chunk of the data. In the past I have simply sorted, but this would be better (especially when the number of processors is small), because you could partition the data in this way, then distribute it (and then sort each subrange in parallel if you needed it sorted). If you did chose to go down one of these routes then I guess a name like nth_elements or, to emphasize the plurality, multiple_nth_elements, might work. Or block_sort, or something along that line. (Of course, for this algorithm to be efficient you need to first partition on the point closest to the centre of the range, which makes it a little trickier to implement) John Bytheway