Adobe Systems Incorporated


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

Detailed Description

Marshall Clow
January 2008

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.

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

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

std::pair<Iter,Iter> adobe::gather ( Iter  first,
Iter  last,
Iter  pivot,
Pred  pred 

iterator-based gather implementation

Definition at line 78 of file gather.hpp.

std::pair< typename boost::range_iterator<BidirectionalRange>::type, typename boost::range_iterator<BidirectionalRange>::type> adobe::gather ( BidirectionalRange &  range,
typename boost::range_iterator< BidirectionalRange >::type  pivot,
Pred  pred 

range-based gather implementation

Definition at line 100 of file gather.hpp.

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google