std::upper_bound
From Cppreference
| Defined in header
<algorithm> | ||
| template< class ForwardIterator, class T >
ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last, | (1) | |
| template< class ForwardIterator, class T, class Compare >
ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last, | (2) | |
Returns an iterator pointing to the first element in the range [first, last) that is greater than value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
Contents |
Parameters
| first, last | - | the range of elements to examine | |||||||||
| value | - | value to compare the elements to | |||||||||
| comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have const &, but the function must not modify the objects passed to it. | |||||||||
Return value
iterator pointing to the first element that is greater than value, or last if no such element is found.
Equivalent function
| First version: |
|---|
template<class ForwardIterator, class T> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value) { ForwardIterator it; std::iterator_traits<ForwardIterator>::distance_type count, step; count = 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 ForwardIterator, class T, class Compare> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) { ForwardIterator it; std::iterator_traits<ForwardIterator>::distance_type count, step; count = 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
| This section is incomplete |
Complexity
logarithmic in the distance between first and last
See also
| returns range of elements matching a specific key (function template) | |
| returns an iterator to the first element not less than the given value (function template) | |
