ceph/src/boost/libs/range/doc/reference/algorithm/lower_bound.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:lower_bound lower_bound]
   7
   8 [heading Prototype]
   9
  10 ``
  11 template<
  12     class ForwardRange,
  13     class Value
  14     >
  15 typename range_iterator<ForwardRange>::type
  16 lower_bound(ForwardRange& rng, Value val);
  17
  18 template<
  19     range_return_value re,
  20     class ForwardRange,
  21     class Value
  22     >
  23 typename range_return<ForwardRange, re>::type
  24 lower_bound(ForwardRange& rng, Value val);
  25
  26 template<
  27     class ForwardRange,
  28     class Value,
  29     class SortPredicate
  30     >
  31 typename range_iterator<ForwardRange>::type
  32 lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
  33
  34 template<
  35     range_return_value re,
  36     class ForwardRange,
  37     class Value,
  38     class SortPredicate
  39     >
  40 typename range_return<ForwardRange,re>::type
  41 lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
  42 ``
  43
  44 [heading Description]
  45
  46 The versions of `lower_bound` that return an iterator, returns the first iterator in the range `rng` such that:
  47 without predicate - `*i < value` is `false`,
  48 with predicate - `pred(*i, value)` is `false`.
  49
  50 `end(rng)` is returned if no such iterator exists.
  51
  52 The versions of `lower_bound` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
  53
  54 [heading Definition]
  55
  56 Defined in the header file `boost/range/algorithm/lower_bound.hpp`
  57
  58 [heading Requirements]
  59
  60 [*For the non-predicate versions:]
  61
  62 * `ForwardRange` is a model of the __forward_range__ Concept.
  63 * `Value` is a model of the `LessThanComparableConcept`.
  64 * The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
  65 * `ForwardRange`'s value type is the same type as `Value`.
  66
  67 [*For the predicate versions:]
  68
  69 * `ForwardRange` is a model of the __forward_range__ Concept.
  70 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
  71 * `ForwardRange`'s value type is the same type as `Value`.
  72 * `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
  73
  74 [heading Precondition:]
  75
  76 [*For the non-predicate versions:]
  77
  78 `rng` is sorted in ascending order according to `operator<`.
  79
  80 [*For the predicate versions:]
  81
  82 `rng` is sorted in ascending order according to `pred`.
  83
  84 [heading Complexity]
  85
  86 For ranges that model the __random_access_range__ concept the complexity is `O(log N)`, where `N` is `distance(rng)`.
  87
  88 For all other range types the complexity is `O(N)`.
  89
  90
  91 [endsect]
  92
  93