A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://cplusplus.com/reference/algorithm/upper_bound/ below:

function template

<algorithm>

std::upper_bound default (1) 
template <class ForwardIterator, class T>  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,                               const T& val);
custom (2) 
template <class ForwardIterator, class T, class Compare>  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,                               const T& val, Compare comp);

Return iterator to upper bound

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

The elements are compared using operator< for the first version, and comp for the second. The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for random-access iterators.

Unlike lower_bound, the value pointed by the iterator returned by this function cannot be equivalent to val, only greater.

The behavior of this function template is equivalent to:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

Parameters
first, last
Forward iterators to the initial and final positions of a sorted (or properly partitioned) sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
val
Value of the upper bound to search for in the range.
For (1), T shall be a type supporting being compared with elements of the range [first,last) as the left-hand side operand of operator<.
comp
Binary function that accepts two arguments (the first is always val, and the second of the type pointed by ForwardIterator), and returns a value convertible to bool. The value returned indicates whether the first argument is considered to go before the second.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Return value An iterator to the upper bound position for val in the range.
If no element in the range compares greater than val, the function returns last.

Example 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

Output: 
lower_bound at position 3
upper_bound at position 6


Complexity On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance).
On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

Data races The objects in the range [first,last) are accessed.

Exceptions Throws if either an element comparison or an operation on an iterator throws.
Note that invalid arguments cause undefined behavior.

See also
lower_bound
Return iterator to lower bound (function template)
equal_range
Get subrange of equal elements (function template)
binary_search
Test if value exists in sorted sequence (function template)
max_element
Return largest element in range (function template)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4