std::upper_bound - cppreference.com (2024)

C++

Language
Standard Library Headers
Freestanding and hosted implementations
Named requirements
Language support library
Concepts library (C++20)
Diagnostics library
Utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Input/output library
Localizations library
Regular expressions library (C++11)
Atomic operations library (C++11)
Thread support library (C++11)
Filesystem library (C++17)
Technical Specifications

[edit]

Algorithm library

Constrained algorithms and algorithms on ranges (C++20)

Concepts and utilities: std::Sortable, std::projected, ...

Constrained algorithms: std::ranges::copy, std::ranges::sort, ...

Execution policies (C++17)

is_execution_policy

execution::seqexecution::parexecution::par_unseqexecution::unseq

(C++20)

execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced

(C++20)

Non-modifying sequence operations

all_ofany_ofnone_of (C++11)(C++11)(C++11)
for_each
for_each_n (C++17)

countcount_if
mismatch
equal
adjacent_find

findfind_iffind_if_not (C++11)
find_end
find_first_of

search
search_n
lexicographical_compare
lexicographical_compare_3way (C++20)

Modifying sequence operations

copycopy_if (C++11)
copy_n (C++11)
copy_backward
move (C++11)
move_backward (C++11)
shift_leftshift_right (C++20)(C++20)
transform

fill
fill_n
generate
generate_n
swap
iter_swap
swap_ranges
sample (C++17)

removeremove_if
replacereplace_if
reverse
rotate
unique
random_shuffle (until C++17)

remove_copyremove_copy_if
replace_copyreplace_copy_if
reverse_copy
rotate_copy
unique_copy
shuffle (C++11)

Operations on uninitialized storage

uninitialized_copy
uninitialized_move (C++17)
uninitialized_fill

uninitialized_copy_n (C++11)
uninitialized_move_n (C++17)
uninitialized_fill_n

uninitialized_default_construct (C++17)
uninitialized_value_construct (C++17)
destroy (C++17)

uninitialized_default_construct_n (C++17)
uninitialized_value_construct_n (C++17)
destroy_n (C++17)

Partitioning operations

is_partitioned (C++11)
partition_point (C++11)

partition
partition_copy (C++11)

stable_partition

Sorting operations

is_sorted (C++11)
is_sorted_until (C++11)

sort
stable_sort

partial_sort
partial_sort_copy

nth_element

Binary search operations

lower_bound

upper_bound

binary_search

equal_range

Set operations (on sorted ranges)

merge
inplace_merge

set_difference
set_intersection

set_symmetric_difference
set_union

includes

Heap operations

is_heap (C++11)
is_heap_until (C++11)

make_heap
sort_heap

push_heap
pop_heap

Minimum/maximum operations

max
max_element

min
min_element

minmax (C++11)
minmax_element (C++11)

clamp (C++17)
compare_3way (C++20)

Permutations

is_permutation

(C++11)

next_permutation

prev_permutation

Numeric operations

iota (C++11)
inner_product
adjacent_difference

accumulate
reduce (C++17)
transform_reduce (C++17)

partial_sum
inclusive_scan (C++17)
exclusive_scan (C++17)


transform_inclusive_scan (C++17)
transform_exclusive_scan (C++17)

C library

qsort

bsearch

[edit]

Defined in header `<algorithm>`
	(1)
template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );			(until C++20)
template< class ForwardIt, class T > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );			(since C++20)
		(2)
template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(until C++20)
template< class ForwardIt, class T, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(since C++20)

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 !(value < element) 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.

The first version uses operator< to compare the elements, the second version uses the given comparison function comp.

1 Parameters
2 Return value
3 Complexity
4 Possible implementation
5 Example
6 Defect reports
7 See also

[edit] Parameters

first, last	-	the range of elements to examine
value	-	value to compare the elements to
comp	-	binary predicate which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for `Type1` a move is equivalent to a copy (since C++11)). The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2.
Type requirements
-`ForwardIt` must meet the requirements of LegacyForwardIterator.
-`Compare` must meet the requirements of BinaryPredicate. it is not required to satisfy Compare

[edit] Return value

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

[edit] Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most log
2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

[edit] Possible implementation

First version
template<class ForwardIt, class T>ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value){ ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!(value < *it)) { first = ++it; count -= step + 1; } else count = step; } return first;}
Second version
template<class ForwardIt, class T, class Compare>ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp){ ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!comp(value, *it)) { first = ++it; count -= step + 1; } else count = step; } return first;}

First version

template<class ForwardIt, class T>ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value){ ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!(value < *it)) { first = ++it; count -= step + 1; } else count = step; } return first;}

Second version

template<class ForwardIt, class T, class Compare>ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp){ ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!comp(value, *it)) { first = ++it; count -= step + 1; } else count = step; } return first;}

[edit] Example

Run this code

#include <algorithm>#include <iostream>#include <iterator>#include <vector>int main(){ std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 }; auto lower = std::lower_bound(data.begin(), data.end(), 4); auto upper = std::upper_bound(data.begin(), data.end(), 4); std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));}

Output:

4 4 4

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 270	C++98	Compare was required to be a strict weak ordering	only a partitioning is needed; heterogeneous comparisons permitted

[edit] See also

equal_range	returns range of elements matching a specific key (function template) [edit]
lower_bound	returns an iterator to the first element not less than the given value (function template) [edit]
partition	divides a range of elements into two groups (function template) [edit]