ceph/src/boost/libs/range/doc/reference/algorithm/partial_sort.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:partial_sort partial_sort]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<class RandomAccessRange>
  12 RandomAccessRange& partial_sort(
  13     RandomAccessRange& rng,
  14     typename range_iterator<RandomAccessRange>::type middle);
  15
  16 template<class RandomAccessRange>
  17 const RandomAccessRange& partial_sort(
  18     const RandomAccessRange& rng,
  19     typename range_iterator<const RandomAccessRange>::type middle);
  20
  21 template<class RandomAccessRange>
  22 RandomAccessRange& partial_sort(
  23     RandomAccessRange& rng,
  24     typename range_iterator<RandomAccessRange>::type middle,
  25     BinaryPredicate sort_pred);
  26
  27 template<class RandomAccessRange>
  28 const RandomAccessRange& partial_sort(
  29     const RandomAccessRange& rng,
  30     typename range_iterator<const RandomAccessRange>::type middle,
  31     BinaryPredicate sort_pred);
  32 ``
  33
  34 [heading Description]
  35
  36 `partial_sort` rearranges the elements in `rng`. It places the smallest `distance(begin(rng), middle)` elements, sorted in ascending order, into the range `[begin(rng), middle)`. The remaining elements are placed in an unspecified order into `[middle, last)`.
  37
  38 The non-predicative versions of this function specify that one element is less than another by using `operator<()`. The predicate versions use the predicate instead.
  39
  40
  41 [heading Definition]
  42
  43 Defined in the header file `boost/range/algorithm/partial_sort.hpp`
  44
  45 [heading Requirements]
  46
  47 [*For the non-predicate version:]
  48
  49 * `RandomAccessRange` is a model of the __random_access_range__ Concept.
  50 * `RandomAccessRange` is mutable.
  51 * `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
  52 * The ordering relation on `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  53
  54
  55 [*For the predicate version:]
  56
  57 * `RandomAccessRange` is a model of the __random_access_range__ Concept.
  58 * `RandomAccessRange` is mutable.
  59 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  60 * `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
  61
  62
  63 [heading Complexity]
  64
  65 Approximately `distance(rng) * log(distance(begin(rng), middle))` comparisons.
  66
  67 [endsect]
  68
  69