std::upper_bound

From cppreference.com
 
 
 
Defined in header <algorithm>
template< class ForwardIterator, class T >

ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last,

                             const T& value );
(1)
template< class ForwardIterator, class T, class Compare >

ForwardIterator upper_bound( ForwardIterator first, ForwardIterator 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 first version uses operator< to compare the elements, the second version uses the given comparison function comp.

Contents

[edit] 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:

bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
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 ForwardIterator can be dereferenced and then implicitly converted to  Type2. ​

[edit] Return value

iterator pointing to the first element that is greater than value, or last if no such element is found.

[edit] Possible implementation

[edit] 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

[edit] Complexity

logarithmic in the distance between first and last

[edit] 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)