Defined in header <algorithm> | ||
---|---|---|
template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); | (1) | |
template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); | (2) |
Returns an iterator pointing to the first element in the range [first, last)
that is greater than value
.
The range [first, last)
must be at least partially ordered, i.e. partitioned with respect to the expression !(value < element)
or !comp(value, element)
. A fully-sorted range meets this criterion, as does a range resulting from a call to std::partition
.
The first version uses operator<
to compare the elements, the second version uses the given comparison function comp
.
Parameters
first, last | - | the range of elements to examine |
value | - | value to compare the elements to |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare ) 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 |
Type requirements | ||
- ForwardIt must meet the requirements of ForwardIterator . |
Return value
iterator pointing to the first element that is greater than value
, or last
if no such element 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-RandomAccessIterator
s, the number of iterator increments is linear.
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; } |
Example
#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
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) | |
divides a range of elements into two groups (function template) |
Please login to continue.