Boost C++ Libraries

The header file 'boost/algorithm/gather.hpp' contains two variants of a single algorithm, gather.

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.

Interface

The function gather returns a std::pair of iterators that denote the elements that satisfy the predicate.

There are two versions; one takes two iterators, and the other takes a range.

namespace boost { namespace algorithm {

template <typename BidirectionalIterator, typename Pred>
std::pair<BidirectionalIterator,BidirectionalIterator>
gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred );

template <typename BidirectionalRange, typename Pred>
std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type>
gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred );

}}

Examples

Given an sequence containing:

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 that is returned by the call.

Iterator Requirements

gather work on bidirectional iterators or better. This requirement comes from the usage of stable_partition, which requires bidirectional iterators. Some standard libraries (libstdc++ and libc++, for example) have implementations of stable_partition that work with forward iterators. If that is the case, then gather will work with forward iterators as well.

Storage Requirements

gather uses stable_partition, which will attempt to allocate temporary memory, but will work in-situ if there is none available.

Complexity

If there is sufficient memory available, the run time is linear: O(N)

If there is not any memory available, then the run time is O(N log N).

Exception Safety

Notes