Re: [boost] New algorithm in Boost.Algorithm: "gather" -- looking for comments

Subject: Re: [boost] New algorithm in Boost.Algorithm: "gather" -- looking for comments
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2013-01-22 02:56:27

On Mon, Jan 21, 2013 at 9:36 PM, Marshall Clow <mclow.lists_at_[hidden]>wrote:

> On Jan 21, 2013, at 8:29 PM, Nathan Ridge <zeratul976_at_[hidden]> wrote:
> >>> gather() takes a collection of elements defined by a pair of iterators
> and moves the ones satisfying a predicate to them to a position (called the
> pivot) within the sequence. The algorithm is stable. The result is a pair
> of iterators that contains the items that satisfy the predicate.
> >>>
> >>> template <typename ForwardIterator, typename Pred>
> >>> std::pair<ForwardIterator,ForwardIterator>
> >>> gather ( ForwardIterator first, ForwardIterator last, ForwardIterator
> pivot, Pred pred );
> >>>
> >>>
> >>> Given an sequence containing:
> >>> int [] arr = { 0 1 2 3 4 5 6 7 8 9 };
> >>>
> >>> A call to gather ( arr, arr + 10, arr + 4, IsEven) will result in:
> >>>
> >>> 1 3 0 2 4 6 8 5 7 9
> >>> |---|-----|
> >>> first | second
> >>> pivot
> >>>
> >>> where first and second are the fields of the pair returned by the call.
> >>>
> >>
> >> I don't understand why the matches are
> >> inserted between 3 and 5, rather than
> >> (say) 1 and 3. You need to specify
> >> exactly what the algorithm does (and
> >> does not) guarantee.
> >
> > Notice the pivot is "arr + 4", which holds the same value (4) before and
> > after the call.
> >
> > It seems to me that the algorithm operates independently on the
> sub-ranges
> > [first, pivot) and [pivot + 1, last), for the first one moving elements
> > satisfying the predicate to just before the pivot (while maintaining the
> > relative order), and for the second one to just after the pivot.
> >
> > Am I understanding that correctly?
>
> Yes, you are.
> it "gathers" the elements satisfying the predicate together at the pivot
> point, preserving their (relative) order.
>

So...isn't this basically a (stable_)partition call on each subrange?

If pred(*pivot) is true, then the range returned will contain pivot.
> If pred(*pivot) is false, then the range returned may or may not contain
> pivot.
>         (if there are no elements in [pivot, end) that satisfy the
> predicate, then the range returned will have pivot as it's end)
>

Sounds like the returned range will never contain the pivot; in the
parenthesized case, the returned range still doesn't contain the pivot,
right?

I used this in an email client I worked on several years ago. It had a
> great feature for "gathering" related messages together.
> If you option-clicked on a particular message's subject, it would collect
> all the messages with the same subject (and "Re:"), and bring them together
> where you clicked.
> Ditto if you option-clicked on a sender - all the messages from that
> person would be gathered together (and selected).
>
> Really handy feature.
>

Well, I guess up to you whether it necessitates a separate function, but I
would think a couple (stable_)partition calls would be sufficient (I could
be wrong about the gather == 2 x (stable_)partition equivalence, though).
Or is there some optimization that gather provides over (stable_)partition?

- Jeff