On Jan 21, 2013, at 11:56 PM, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung@gmail.com> wrote:
On Mon, Jan 21, 2013 at 9:36 PM, Marshall Clow <mclow.lists@gmail.com>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
template <typename ForwardIterator, typename Pred> std::pair<ForwardIterator,ForwardIterator> gather ( ForwardIterator first, ForwardIterator last, ForwardIterator
On Jan 21, 2013, at 8:29 PM, Nathan Ridge <zeratul976@hotmail.com> wrote: pivot) within the sequence. The algorithm is stable. The result is a pair of iterators that contains the items that satisfy the predicate. 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@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki