Re: [boost] Painting a bikeshed ...

Subject: Re: [boost] Painting a bikeshed ...
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2015-10-21 13:20:39

On Thu, Oct 1, 2015 at 4:50 AM, Roland Bock <rbock_at_[hidden]> wrote:

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