Re: [boost] Painting a bikeshed ...

Subject: Re: [boost] Painting a bikeshed ...
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2015-10-03 07:40:12

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<typename Iterator, typename Pred>
>   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