Boost  v1.57.0
doxygen for www.boost.org
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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. More...

Functions

template<typename BidirectionalIterator , typename Pred >
std::pair
< BidirectionalIterator,
BidirectionalIterator > 
boost::algorithm::gather (BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred)
 iterator-based gather implementation More...
 
template<typename BidirectionalRange , typename Pred >
std::pair< typename
boost::range_iterator< const
BidirectionalRange >::type,
typename boost::range_iterator
< const BidirectionalRange >
::type > 
boost::algorithm::gather (const BidirectionalRange &range, typename boost::range_iterator< const BidirectionalRange >::type pivot, Pred pred)
 range-based gather implementation More...
 

Detailed Description

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.

Author
Marshall Clow
Date
January 2008

The algorithm is stable. The result is a pair of iterators that contains the items that satisfy the predicate.

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

The problem is broken down into two basic steps, namely, moving the items before the pivot and then moving the items from the pivot to the end. These "moves" are done with calls to stable_partition.

Storage Requirements:

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

Time Complexity:

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

Function Documentation

template<typename BidirectionalIterator , typename Pred >
std::pair<BidirectionalIterator, BidirectionalIterator> boost::algorithm::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> boost::algorithm::gather ( const BidirectionalRange &  range,
typename boost::range_iterator< const BidirectionalRange >::type  pivot,
Pred  pred 
)

#include <boost_1_57_0/boost/algorithm/gather.hpp>

range-based gather implementation

References boost::asio::begin, boost::end, and boost::algorithm::gather().