NAME¶

std::ranges::upper_bound - std::ranges::upper_bound

Synopsis¶

Defined in header <algorithm>
Call signature
template< std::forward_iterator I, std::sentinel_for<I> S,

class T, class Proj = std::identity, (since
std::indirect_strict_weak_order C++20)
<const T*, std::projected<I, Proj>> Comp = (until
ranges::less > C++26)
constexpr I upper_bound( I first, S last, const T& value,

Comp comp = {}, Proj proj = {} );
template< std::forward_iterator I, std::sentinel_for<I> S,

class Proj = std::identity,
class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order (since
<const T*, std::projected<I, Proj>> Comp = C++26)
ranges::less >
constexpr I upper_bound( I first, S last, const T& value,

Comp comp = {}, Proj proj = {} );
template< ranges::forward_range R,

class T, class Proj = std::identity,
std::indirect_strict_weak_order (1)
<const T*, (since
std::projected<ranges::iterator_t<R>, C++20)
Proj>> Comp = (until
ranges::less > C++26)
constexpr ranges::borrowed_iterator_t<R>

upper_bound( R&& r, const T& value, Comp comp = {}, Proj
proj = {} );
template< ranges::forward_range R, (2)

class Proj = std::identity,
class T =
std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, (since
std::projected<ranges::iterator_t<R>, C++26)
Proj>> Comp =
ranges::less >
constexpr ranges::borrowed_iterator_t<R>

upper_bound( R&& r, const T& value, Comp comp = {}, Proj
proj = {} );

1) Returns an iterator pointing to the first element in the range [first, last) that
is greater than value, or last if no such element is found. The range [first, last)
must be partitioned with respect to the expression or !comp(value, element), i.e.,
all elements for which the expression is true must precede all elements for which
the expression is false. A fully-sorted range meets this criterion.
2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as
first and ranges::end(r) as last.

The function-like entities described on this page are niebloids, that is:

* Explicit template argument lists cannot be specified when calling any of them.
* None of them are visible to argument-dependent lookup.
* When any of them are found by normal unqualified lookup as the name to the left
of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler
extensions.

Parameters¶

first, last - iterator-sentinel defining the partially-ordered range to examine
r - the partially-ordered range to examine
value - value to compare the elements to
pred - predicate to apply to the projected elements
proj - projection to apply to the elements

Return value¶

Iterator pointing to the first element that is greater than value, or last if no
such element is found.

Complexity¶

The number of comparisons and applications of the projection performed are
logarithmic in the distance between first and last (at most log
2(last - first) + O(1) comparisons and applications of the projection). However, for
an iterator that does not model random_access_iterator, the number of iterator
increments is linear.

Possible implementation¶

struct upper_bound_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less>
constexpr I operator()(I first, S last, const T& value,
Comp comp = {}, Proj proj = {}) const
{
I it;
std::iter_difference_t<I> count, step;
count = ranges::distance(first, last);

while (count > 0)
{
it = first;
step = count / 2;
ranges::advance(it, step, last);
if (!comp(value, std::invoke(proj, *it)))
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}

template<ranges::forward_range R, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less>
constexpr ranges::borrowed_iterator_t<R>
operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::end(r), value,
std::ref(comp), std::ref(proj));
}
};

inline constexpr upper_bound_fn upper_bound;

Notes¶

Feature-test macro Value Std Feature
__cpp_lib_algorithm_default_value_type 202403 (C++26) List-initialization for
algorithms (1,2)

Example¶

// Run this code

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
namespace ranges = std::ranges;

std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};

{
auto lower = ranges::lower_bound(data.begin(), data.end(), 4);
auto upper = ranges::upper_bound(data.begin(), data.end(), 4);

ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}
{
auto lower = ranges::lower_bound(data, 3);
auto upper = ranges::upper_bound(data, 3);

ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}

using CD = std::complex<double>;
std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
#ifdef __cpp_lib_algorithm_default_value_type
auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
#else
auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
#endif
assert((*it == CD{3, 0}));
}

Output:¶

4 4 4
3 3 3 3

See also¶

ranges::equal_range returns range of elements matching a specific key
(C++20) (niebloid)
ranges::lower_bound returns an iterator to the first element not less than the given
(C++20) value
(niebloid)
ranges::partition divides a range of elements into two groups
(C++20) (niebloid)
returns an iterator to the first element greater than a certain
upper_bound value
(function template)