Namespaces
Variants
Views
Actions

std::ranges::upper_bound

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms: std::ranges::copy, std::ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
C library
 
Constrained algorithms
Non-modifying sequence operations
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
Binary search operations
ranges::upper_bound
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutations
 
Defined in header <algorithm>
Call signature
template< std::forward_iterator I, std::sentinel_for<I> S,

          class T, class Proj = std::identity,
          std::indirect_strict_weak_order<
              const T*,
              std::projected<I, Proj>> Comp = ranges::less >
  constexpr I

upper_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );
(1) (since C++20)
template< ranges::forward_range R, class T, class Proj = std::identity,

          std::indirect_strict_weak_order<
              const T*,
              std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less >
  constexpr ranges::borrowed_iterator_t<R>

upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
(2) (since C++20)
1) Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. The range [first, last) must be partitioned with respect to the expression or !comp(value, element), i.e., all elements for which the expression is true must precede all elements for which the expression is false. A fully-sorted range meets this criterion.
2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.

Contents

[edit] Parameters

first, last - iterator-sentinel defining the partially-ordered range to examine
r - the partially-ordered range to examine
value - value to compare the elements to
pred - predicate to apply to the projected elements
proj - projection to apply to the elements

[edit] Return value

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

[edit] Complexity

The number of comparisons and applications of the projection performed are logarithmic in the distance between first and last (At most log
2
(last - first) + O(1)
comparisons and applications of the projection). However, for an iterator that does not model random_access_iterator, the number of iterator increments is linear.

[edit] Possible implementation

struct upper_bound_fn {
  template<std::forward_iterator I, std::sentinel_for<I> S,
           class T, class Proj = std::identity,
           std::indirect_strict_weak_order<
               const T*,
               std::projected<I, Proj>> Comp = ranges::less>
  constexpr I operator()( I first, S last, const T& value,
                          Comp comp = {}, Proj proj = {} ) const
  {
      I it;
      std::iter_difference_t<I> count, step;
      count = ranges::distance(first, last);
 
      while (count > 0) {
          it = first; 
          step = count / 2;
          ranges::advance(it, step, last);
          if (!comp(value, *it)) {
              first = ++it;
              count -= step + 1;
          }
          else {
              count = step;
          }
      }
      return first;
  }
 
  template<ranges::forward_range R, class T, class Proj = std::identity,
           std::indirect_strict_weak_order<
               const T*,
               std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
  constexpr ranges::borrowed_iterator_t<R>
  operator()( R&& r, const T& value, Comp comp = {}, Proj proj = {} ) const
  {
    return (*this)(ranges::begin(r), ranges::end(r), value,
                   std::ref(comp), std::ref(proj));
  }
};
 
inline constexpr upper_bound_fn upper_bound;

[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 = ranges::lower_bound(data.begin(), data.end(), 4);
        auto upper = ranges::upper_bound(data.begin(), data.end(), 4);
 
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
    {
        auto lower = ranges::lower_bound(data, 3);
        auto upper = ranges::upper_bound(data, 3);
 
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
}

Output:

4 4 4 
3 3 3 3

[edit] See also

returns range of elements matching a specific key
(niebloid) [edit]
returns an iterator to the first element not less than the given value
(niebloid) [edit]
divides a range of elements into two groups
(niebloid) [edit]
returns an iterator to the first element greater than a certain value
(function template) [edit]