ceph/src/boost/libs/range/doc/reference/algorithm/stable_partition.qbk

   1 [/
   2     Copyright 2010 Neil Groves
   3     Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 /]
   6 [section:stable_partition stable_partition]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<class ForwardRange, class UnaryPredicate>
  12 typename range_iterator<ForwardRange>::type
  13 stable_partition(ForwardRange& rng, UnaryPredicate pred);
  14
  15 template<class ForwardRange, class UnaryPredicate>
  16 typename range_iterator<const ForwardRange>::type
  17 stable_partition(const ForwardRange& rng, UnaryPredicate pred);
  18
  19 template<
  20     range_return_value re,
  21     class ForwardRange,
  22     class UnaryPredicate
  23 >
  24 typename range_return<ForwardRange, re>::type
  25 stable_partition(ForwardRange& rng, UnaryPredicate pred);
  26
  27 template<
  28     range_return_value re,
  29     class ForwardRange,
  30     class UnaryPredicate
  31 >
  32 typename range_return<const ForwardRange, re>::type
  33 stable_partition(const ForwardRange& rng, UnaryPredicate pred);
  34 ``
  35
  36 [heading Description]
  37
  38 `stable_partition` reorders the elements in the range `rng` base on the function object `pred`. Once this function has completed all of the elements that satisfy `pred` appear before all of the elements that fail to satisfy it. `stable_partition` differs from `partition` because it preserves relative order. It is stable.
  39
  40 For the versions that return an iterator, the return value is the iterator to the first element that fails to satisfy `pred`.
  41
  42 For versions that return a `range_return`, the `found` iterator is the iterator to the first element that fails to satisfy `pred`.
  43
  44 [heading Definition]
  45
  46 Defined in the header file `boost/range/algorithm/stable_partition.hpp`
  47
  48 [heading Requirements]
  49
  50 * `ForwardRange` is a model of the __forward_range__ Concept.
  51 * `ForwardRange` is mutable.
  52 * `UnaryPredicate` is a model of the `PredicateConcept`.
  53
  54 [heading Complexity]
  55
  56 Best case: `O(N)` where `N` is `distance(rng)`.
  57 Worst case: `N * log(N)` swaps, where `N` is `distance(rng)`.
  58
  59 [endsect]
  60
  61