FreeBSD Manual Pages
std::upper_bound(3) C++ Standard Libary std::upper_bound(3) NAME std::upper_bound - std::upper_bound Synopsis Defined in header <algorithm> template< class ForwardIt, class T > (constexpr since ForwardIt upper_bound( ForwardIt first, C++20) ForwardIt last, (until C++26) const T& value ); template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > (since C++26) constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > (1) (con- stexpr since ForwardIt upper_bound( ForwardIt first, C++20) ForwardIt last, (until C++26) const T& value, Compare comp ); template< class ForwardIt, class T = typename std::iterator_traits (2) <ForwardIt>::value_type, class Compare > (since C++26) constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); Searches for the first element in the partitioned range [first, last) which is ordered after value. 1) The order is determined by operator<: Returns the first iterator iter in [first, last) where bool(value < *iter) is true, or last if no such iter exists. (un- til C++20) If the elements elem of [first, last) are not partitioned with re- spect to the expression bool(value < elem), the behavior is undefined. Equivalent to std::upper_bound(first, last, value, std::less{}). (since C++20) 2) The order is determined by comp: Returns the first iterator iter in [first, last) where bool(comp(value, *iter)) is true, or last if no such iter exists. If the elements elem of [first, last) are not partitioned with re- spect to the expression bool(comp(value, elem)), the behavior is undefined. Parameters first, last - the partitioned range of elements to examine value - value to compare the elements to binary predicate which returns true if the first argu- ment 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); comp - 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 re- gardless 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 con- verted to Type2. Type requirements - ForwardIt must meet the requirements of LegacyForwardIterator. - Compare must meet the requirements of BinaryPredicate. It is not re- quired to satisfy Compare. Return value Iterator to the first element of the range [first, last) ordered af- ter value, or last if no such element is found. Complexity Given \(\scriptsize N\)N as std::distance(first, last): 1) At most \(\scriptsize \log_{2}(N)+O(1)\)log 2(N)+O(1) comparisons with value using operator< (until C++20) std::less{} (since C++20). 2) At most \(\scriptsize \log_{2}(N)+O(1)\)log 2(N)+O(1) applications of the comparator comp. However, if ForwardIt is not a LegacyRandomAccessIterator, the num- ber of iterator increments is linear in \(\scriptsize N\)N. Notably, std::map, std::multimap, std::set, and std::multiset iterators are not random access, and so their member upper_bound functions should be preferred. Possible implementation See also the implementations in libstdc++ and libc++. upper_bound (1) template<class ForwardIt, class T = typename std::iterator_traits<For- wardIt>::value_type> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value) { return std::upper_bound(first, last, value, std::less{}); } upper_bound (2) template<class ForwardIt, class T = typename std::iterator_traits<For- wardIt>::value_type, 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; } Notes Although std::upper_bound only requires [first, last) to be parti- tioned, this algorithm is usually used in the case where [first, last) is sorted, so that the binary search is valid for any value. For any iterator iter in [first, last), std::upper_bound requires value < *iter and comp(value, *iter) to be well-formed, while std::lower_bound re- quires *iter < value and comp(*iter, value) to be well-formed instead. Feature-test macro Value Std Feature __cpp_lib_algorithm_default_value_type 202403 (C++26) List-initial- ization for algorithms (1,2) Example // Run this code #include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <vector> struct PriceInfo { double price; }; int main() { const std::vector<int> data{1, 2, 4, 5, 5, 6}; for (int i = 0; i < 7; ++i) { // Search first element that is greater than i auto upper = std::upper_bound(data.begin(), data.end(), i); std::cout << i << " < "; upper != data.end() ? std::cout << *upper << " at index " << std::dis- tance(data.begin(), upper) : std::cout << "not found"; std::cout << '\n'; } std::vector<PriceInfo> prices{{100.0}, {101.5}, {102.5}, {102.5}, {107.3}}; for (double to_find : {102.5, 110.2}) { auto prc_info = std::upper_bound(prices.begin(), prices.end(), to_find, [](double value, const PriceInfo& info) { return value < info.price; }); prc_info != prices.end() ? std::cout << prc_info->price << " at index " << prc_info - prices.begin() : std::cout << to_find << " not found"; 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 = std::upper_bound(nums.cbegin(), nums.cend(), {2, 0}, cmpz); #else auto it = std::upper_bound(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz); #endif assert((*it == CD{3, 0})); } Output: 0 < 1 at index 0 1 < 2 at index 1 2 < 4 at index 2 3 < 4 at index 2 4 < 5 at index 3 5 < 6 at index 5 6 < not found 107.3 at index 4 110.2 not found Defect reports The following behavior-changing defect reports were applied retroac- tively to previously published C++ standards. DR Applied to Behavior as published Correct behavior Compare was required to satisfy only a parti- tioning is required; LWG 270 C++98 Compare and T was required heterogeneous comparisons to be LessThanComparable permitted (strict weak ordering required) at most \(\scriptsize corrected to \(\scriptsize LWG 384 C++98 \log(N)+1\)log \log_{2}(N)+O(1)\)log 2(N)+1 comparisons were allowed 2(N)+O(1) LWG 577 C++98 last could not be returned allowed if any iterator iter exists in [first, last) such that LWG 2150 C++98 bool(comp(value, *iter)) is no iterator af- ter true, std::lower_bound iter can be re- turned could return any iterator in [iter, last) See also equal_range returns range of elements matching a specific key (function template) returns an iterator to the first element not less than the given lower_bound value (function template) partition divides a range of elements into two groups (function template) partition_point locates the partition point of a partitioned range (C++11) (function template) ranges::upper_bound returns an iterator to the first element greater than a certain (C++20) value (niebloid) returns an iterator to the first element greater than the given upper_bound key (public member function of std::set<Key,Com- pare,Allocator>) returns an iterator to the first element greater than the given upper_bound key (public member function of std::multi- set<Key,Compare,Allocator>) http://cppreference.com 2024.06.10 std::upper_bound(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Possible implementation | Notes | Example | Output: | See also
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::upper_bound&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>