libs/algorithm/doc/gather.qbk

   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