projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | [/ File gather.qbk] |
| 2 | ||
| 3 | [section:gather gather] | |
| 4 | ||
| 5 | [/license | |
| 6 | Copyright (c) 2013 Marshall Clow | |
| 7 | ||
| 8 | Distributed 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 | ||
| 12 | The 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 | ||
| 18 | The function `gather` returns a `std::pair` of iterators that denote the elements that satisfy the predicate. | |
| 19 | ||
| 20 | There are two versions; one takes two iterators, and the other takes a range. | |
| 21 | ||
| 22 | `` | |
| 23 | namespace boost { namespace algorithm { | |
| 24 | ||
| 25 | template <typename BidirectionalIterator, typename Pred> | |
| 26 | std::pair<BidirectionalIterator,BidirectionalIterator> | |
| 27 | gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred ); | |
| 28 | ||
| 29 | template <typename BidirectionalRange, typename Pred> | |
| 30 | std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type> | |
| 31 | gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred ); | |
| 32 | ||
| 33 | }} | |
| 34 | `` | |
| 35 | ||
| 36 | [heading Examples] | |
| 37 | ||
| 38 | Given an sequence containing: | |
| 39 | `` | |
| 40 | 0 1 2 3 4 5 6 7 8 9 | |
| 41 | `` | |
| 42 | ||
| 43 | a call to gather ( arr, arr + 10, arr + 4, IsEven ) will result in: | |
| 44 | ||
| 45 | `` | |
| 46 | 1 3 0 2 4 6 8 5 7 9 | |
| 47 | |---|-----| | |
| 48 | first | second | |
| 49 | pivot | |
| 50 | `` | |
| 51 | where `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 | ||
| 64 | If there is sufficient memory available, the run time is linear: `O(N)` | |
| 65 | ||
| 66 | If 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 | |
| 75 | Copyright 2013 Marshall Clow | |
| 76 | Distributed 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 |