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 09:56:22

On Jan 21, 2013, at 11:56 PM, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung_at_[hidden]> wrote:

> 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?

It is - in fact, that's how it's implemented.

> 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?

No - the returned range will always contain the pivot (position),
 _except_ in the case where none of the elements in [pivot, end) satisfy the predicate.

> 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?

Nope. 
But I think it's sufficiently useful (and possibly non-obvious) to be given its' own name.

[ If you watch Bjarne's keynote from GoingNative 2012, he relates an anecdote about how a whole bunch of code, involving loops and multiple calls to rotate, was replaced by a single call to gather (starting at about 52:50) ]

-- 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