1[/ File gather.qbk] 2 3[section:gather gather] 4 5[/license 6Copyright (c) 2013 Marshall Clow 7 8Distributed under the Boost Software License, Version 1.0. 9(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 10] 11 12The header file 'boost/algorithm/gather.hpp' contains two variants of a single algorithm, `gather`. 13 14`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. 15 16[heading Interface] 17 18The function `gather` returns a `std::pair` of iterators that denote the elements that satisfy the predicate. 19 20There are two versions; one takes two iterators, and the other takes a range. 21 22`` 23namespace boost { namespace algorithm { 24 25template <typename BidirectionalIterator, typename Pred> 26std::pair<BidirectionalIterator,BidirectionalIterator> 27gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred ); 28 29template <typename BidirectionalRange, typename Pred> 30std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type> 31gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred ); 32 33}} 34`` 35 36[heading Examples] 37 38Given an sequence containing: 39`` 400 1 2 3 4 5 6 7 8 9 41`` 42 43a call to gather ( arr, arr + 10, arr + 4, IsEven ) will result in: 44 45`` 461 3 0 2 4 6 8 5 7 9 47 |---|-----| 48 first | second 49 pivot 50`` 51where `first` and `second` are the fields of the pair that is returned by the call. 52 53 54[heading Iterator Requirements] 55 56`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. 57 58[heading Storage Requirements] 59 60`gather` uses `stable_partition`, which will attempt to allocate temporary memory, but will work in-situ if there is none available. 61 62[heading Complexity] 63 64If there is sufficient memory available, the run time is linear: `O(N)` 65 66If there is not any memory available, then the run time is `O(N log N)`. 67 68[heading Exception Safety] 69 70[heading Notes] 71 72[endsect] 73 74[/ File gather.qbk 75Copyright 2013 Marshall Clow 76Distributed under the Boost Software License, Version 1.0. 77(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). 78] 79 80