...one 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> 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 ); }}

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.

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

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

.