std::ranges::upper_bound

Defined in header `<algorithm>`
Call signature
	(1)
template < std::forward_iterator I, std::sentinel_for <I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order < const T*, std:: projected <I, Proj>> Comp = ranges::less > constexpr I upper_bound( I first, S last, const T& value, Comp comp = { }, Proj proj = { } ) ;			(since C++20) (until C++26)
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 upper_bound( I first, S last, const T& value, Comp comp = { }, Proj proj = { } ) ;			(since C++26)
		(2)
template < ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order < const T*, std:: projected < ranges::iterator_t <R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_iterator_t <R> upper_bound( R&& r, const T& value, Comp comp = { }, Proj proj = { } ) ;				(since C++20) (until C++26)
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> upper_bound( R&& r, const T& value, Comp comp = { }, Proj proj = { } ) ;				(since C++26)

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

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 algorithm function objects (informally known as 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

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

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

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

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

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