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

Subject: Re: [boost] New algorithm in Boost.Algorithm: "gather" -- looking for comments
From: Marshall Clow (mclow.lists_at_[hidden])
Date: 2013-01-22 00:36:54

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.

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)

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.

-- Marshall

Marshall Clow     Idio Software   <mailto:mclow.lists_at_[hidden]>

A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait).
        -- Yu Suzuki