Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards



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.


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



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

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.


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