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:upper_bound upper_bound] 7 8[heading Prototype] 9 10`` 11template< 12 class ForwardRange, 13 class Value 14 > 15typename range_iterator<ForwardRange>::type 16upper_bound(ForwardRange& rng, Value val); 17 18template< 19 range_return_value re, 20 class ForwardRange, 21 class Value 22 > 23typename range_return<ForwardRange, re>::type 24upper_bound(ForwardRange& rng, Value val); 25 26template< 27 class ForwardRange, 28 class Value, 29 class SortPredicate 30 > 31typename range_iterator<ForwardRange>::type 32upper_bound(ForwardRange& rng, Value val, SortPredicate pred); 33 34template< 35 range_return_value re, 36 class ForwardRange, 37 class Value, 38 class SortPredicate 39 > 40typename range_return<ForwardRange,re>::type 41upper_bound(ForwardRange& rng, Value val, SortPredicate pred); 42`` 43 44[heading Description] 45 46The versions of `upper_bound` that return an iterator, returns the first iterator in the range `rng` such that: 47without predicate - `val < *i` is `true`, 48with predicate - `pred(val, *i)` is `true`. 49 50`end(rng)` is returned if no such iterator exists. 51 52The versions of `upper_bound` that return a `range_return`, defines `found` in the same manner as the returned iterator described above. 53 54[heading Definition] 55 56Defined in the header file `boost/range/algorithm/upper_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 86For ranges that model the __random_access_range__ Concept the complexity is `O(log N)`, where `N` is `distance(rng)`. For all other range types the complexity is `O(N)`. 87 88[endsect] 89 90 91