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

Subject: Re: [boost] New algorithm in Boost.Algorithm: "gather" -- looking for comments
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2013-01-21 23:29:00

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

Regards,
Nate