std::upper_bound - cppreference.com (original) (raw)

| Defined in header | | | | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | ------------------------------------- | | (1) | | | | template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); | | (constexpr since C++20) (until C++26) | | template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); | | (since C++26) | | (2) | | | | template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | | (constexpr since C++20) (until C++26) | | template< class ForwardIt, class T = typename std::iterator_traits <ForwardIt>::value_type, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | | (since C++26) |

Searches for the first element in the partitioned range [first, last) which is ordered after value.

1. The order is determined by operator<:

1. 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 respect to the expression bool(comp(value, elem)), the behavior is undefined.

Contents

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

[edit] Parameters

[edit] Return value

Iterator to the first element of the range [first, last) ordered after value, or last if no such element is found.

[edit] Complexity

Given \(\scriptsize N\)N as std::distance(first, last):

1. At most \(\scriptsize \log_{2}(N)+O(1)\)log2(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)\)log2(N)+O(1) applications of the comparator comp.

However, if ForwardIt is not a LegacyRandomAccessIterator, the number 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.

[edit] Possible implementation

See also the implementations in libstdc++ and libc++.

[edit] Notes

Although std::upper_bound only requires [first, last) to be partitioned, 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 requires *iter < value and comp(*iter, value) to be well-formed instead.

[edit] Example

#include #include #include #include #include   struct PriceInfo { double price; };   int main() { const std::vector 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::distance(data.begin(), upper) : std::cout << "not found"; std::cout << '\n'; }   std::vector 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; std::vector 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

[edit] Defect reports

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

[edit] See also