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

Subject: Re: [boost] New algorithm in Boost.Algorithm: "gather" -- looking for comments
From: Sean Parent (sparent_at_[hidden])
Date: 2013-01-26 16:18:58

On Jan 21, 2013, at 4:49 PM, Marshall Clow <mclow.lists_at_[hidden]<mailto:mclow.lists_at_[hidden]>> wrote:

I have committed a new algorithm named "gather" into Boost.Algorithm.

Actually, it's one I wrote for Sean Parent as part of ASL about five years ago, and it's the first (of hopefully many) of the bits oF ASL to be moved into boost.

Here's a summary:

My edits:

gather() takes a sequence of objects and moves the objects that satisfy a predicate to a position within the sequence. The algorithm is stable, meaning that the relative position of items satisfying the predicate, and those not satisfying the predicate are not changed. gather() returns the range of objects satisfying the predicate.

Post-condition: The position is within the returned range.

Sean

...

[Rename pivot to position in diagram]

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.

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

Sean Parent
sparent_at_[hidden]<mailto:sparent_at_[hidden]>

“Explanations exist; they have existed for all time; there is always a well-known solution to every human problem — neat, plausible, and wrong.” - H. L. Mencken