ceph/src/boost/libs/range/doc/reference/algorithm/nth_element.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:nth_element nth_element]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<class RandomAccessRange>
  12 RandomAccessRange& nth_element(
  13     RandomAccessRange& rng,
  14     typename range_iterator<RandomAccessRange>::type nth);
  15
  16 template<class RandomAccessRange>
  17 const RandomAccessRange& nth_element(
  18     const RandomAccessRange& rng,
  19     typename range_iterator<const RandomAccessRange>::type nth);
  20
  21 template<class RandomAccessRange>
  22 RandomAccessRange& nth_element(
  23     RandomAccessRange& rng,
  24     typename range_iterator<RandomAccessRange>::type nth,
  25     BinaryPredicate sort_pred);
  26
  27 template<class RandomAccessRange>
  28 const RandomAccessRange& nth_element(
  29     const RandomAccessRange& rng,
  30     typename range_iterator<const RandomAccessRange>::type nth,
  31     BinaryPredicate sort_pred);
  32 ``
  33
  34 [heading Description]
  35
  36 `nth_element` partially orders a range of elements. `nth_element` arranges the range `rng` such that the element corresponding with the iterator `nth` is the same as the element that would be in that position if `rng` has been sorted.
  37
  38
  39 [heading Definition]
  40
  41 Defined in the header file `boost/range/algorithm/nth_element.hpp`
  42
  43 [heading Requirements]
  44
  45 [*For the non-predicate version:]
  46
  47 * `RandomAccessRange` is a model of the __random_access_range__ Concept.
  48 * `RandomAccessRange` is mutable.
  49 * `RandomAccessRange`'s value type is a model of the `LessThanComparableConcept`.
  50 * The ordering relation on `RandomAccessRange`'s value type is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  51
  52
  53 [*For the predicate version:]
  54
  55 * `RandomAccessRange` is a model of the __random_access_range__ Concept.
  56 * `RandomAccessRange` is mutable.
  57 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  58 * `RandomAccessRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
  59
  60
  61 [heading Complexity]
  62
  63 On average, linear in `distance(rng)`.
  64
  65 [endsect]
  66
  67