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 > ForwardIt upper_bound( ForwardIt first, (until C++20) ForwardIt last, const T& value ); template< class ForwardIt, class T > constexpr ForwardIt upper_bound( ForwardIt (since C++20) first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > (1) (until C++20) ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); template< class ForwardIt, class T, class (2) Compare > constexpr ForwardIt upper_bound( ForwardIt (since C++20) first, ForwardIt last, const T& value, Compare comp ); Returns an iterator pointing to the first element in the range [first, last) such that value < element (or comp(value, element)) is true (i.e. strictly greater), or last if no such element is found. The range [first, last) must be partitioned with respect to the ex- pression !(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. Parameters first, last - iterators defining the partially-ordered range to ex- amine value - value to compare the elements to binary predicate which returns true if the first argu- ment 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); 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 pointing to the first element in the range [first, last) such that value < element (or comp(value, element)) is true, or last if no such ele- ment is found. 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-LegacyRando- mAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::upper_bound (resp. std::multiset::upper_bound) should be preferred. Possible implementation See also the implementations in libstdc++ and libc++. 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; } Example // Run this code #include <algorithm> #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'; } } 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 LWG 270 C++98 Compare was required to be a only a partitioning is needed; strict weak ordering heterogeneous com- parisons permitted 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 2022.07.31 std::upper_bound(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Possible implementation | First version | Second version | 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.0>