Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/algorithm/ranges/upper bound"

From cppreference.com
< cpp‎ | algorithm‎ | ranges
(Apply previously unused `proj` argument `*it` to make a correct projection)
m (FTM.)
 
(3 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
{{cpp/algorithm/ranges/navbar}}
 
{{cpp/algorithm/ranges/navbar}}
 
{{dcl begin}}
 
{{dcl begin}}
−
{{dcl header | algorithm}}
+
{{dcl header|algorithm}}
−
{{dcl h | Call signature}}
+
{{dcl h|Call signature}}
−
{{dcl | num=1 | since=c++20 |1=
+
{{dcl rev begin|num=1}}
 +
{{dcla|anchor=1|since=c++20|until=c++26|1=
 
template< std::forward_iterator I, std::sentinel_for<I> S,
 
template< std::forward_iterator I, std::sentinel_for<I> S,
 
           class T, class Proj = std::identity,
 
           class T, class Proj = std::identity,
−
           std::indirect_strict_weak_order<
+
           std::indirect_strict_weak_order
−
               const T*,
+
               <const T*, std::projected<I, Proj>> Comp = ranges::less >
−
              std::projected<I, Proj>> Comp = ranges::less >
+
constexpr I upper_bound( I first, S last, const T& value,
−
  constexpr I
+
                        Comp comp = {}, Proj proj = {} );
−
upper_bound( I first, S last, const T& value, Comp comp = {}, Proj proj = {} );
+
 
}}
 
}}
−
{{dcl | num=2 | since=c++20 |1=
+
{{dcl|since=c++26|1=
−
template< ranges::forward_range R, class T, class Proj = std::identity,
+
template< std::forward_iterator I, std::sentinel_for<I> S,
−
           std::indirect_strict_weak_order<
+
          class Proj = std::identity,
−
               const T*,
+
          class T = std::projected_value_t<I, Proj>,
−
               std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less >
+
          std::indirect_strict_weak_order
−
  constexpr ranges::borrowed_iterator_t<R>
+
              <const T*, std::projected<I, Proj>> Comp = ranges::less >
−
upper_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
+
constexpr I upper_bound( I first, S last, const T& value,
 +
                        Comp comp = {}, Proj proj = {} );
 +
}}
 +
{{dcl rev end}}
 +
{{dcl rev begin|num=2}}
 +
{{dcl|since=c++20|until=c++26|1=
 +
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 = {} );
 +
}}
 +
{{dcl|since=c++26|1=
 +
template< ranges::forward_range R,
 +
          class Proj = std::identity,
 +
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
 +
          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 = {} );
 
}}
 
}}
 +
{{dcl rev end}}
 
{{dcl end}}
 
{{dcl end}}
  
−
@1@ Returns an iterator pointing to the first element in the range {{tt|[first, last)}} that is ''greater'' than {{tt|value}}, or {{tt|last}} if no such element is found.
+
@1@ Returns an iterator pointing to the first element in the range {{range|first|last}} that is ''greater'' than {{c|value}}, or {{c|last}} if no such element is found.
−
The range {{tt|[first, last)}} must be partitioned with respect to the expression or {{c|!comp(value, element)}}, i.e., all elements for which the expression is {{c|true}} must precede all elements for which the expression is {{c|false}}. A fully-sorted range meets this criterion.
+
The range {{range|first|last}} must be partitioned with respect to the expression or {{c|!comp(value, element)}}, i.e., all elements for which the expression is {{c|true}} must precede all elements for which the expression is {{c|false}}. A fully-sorted range meets this criterion.
  
−
@2@ Same as {{v|1}}, but uses {{tt|r}} as the source range, as if using {{c|ranges::begin(r)}} as {{tt|first}} and {{c|ranges::end(r)}} as {{tt|last}}.
+
@2@ Same as {{v|1}}, but uses {{c|r}} as the source range, as if using {{c|ranges::begin(r)}} as {{c|first}} and {{c|ranges::end(r)}} as {{c|last}}.
  
 
{{cpp/ranges/niebloid}}
 
{{cpp/ranges/niebloid}}
Line 32: Line 55:
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | first, last | iterator-sentinel defining the partially-ordered range to examine}}
+
{{par|first, last|iterator-sentinel defining the partially-ordered range to examine}}
−
{{par | r | the partially-ordered range to examine}}
+
{{par|r|the partially-ordered range to examine}}
−
{{par | value | value to compare the elements to}}
+
{{par|value|value to compare the elements to}}
−
{{par | pred | predicate to apply to the projected elements}}
+
{{par|pred|predicate to apply to the projected elements}}
−
{{par | proj | projection to apply to the elements}}
+
{{par|proj|projection to apply to the elements}}
 
{{par end}}
 
{{par end}}
  
 
===Return value===
 
===Return value===
−
Iterator pointing to the first element that is ''greater'' than {{tt|value}}, or {{tt|last}} if no such element is found.
+
Iterator pointing to the first element that is ''greater'' than {{c|value}}, or {{c|last}} if no such element is found.
  
 
===Complexity===
 
===Complexity===
−
The number of comparisons and applications of the projection performed are logarithmic in the distance between {{tt|first}} and {{tt|last}} (At most {{math|log{{su|b=2}}(last - first) + O(1)}} comparisons and applications of the projection). However, for an iterator that does not model {{lconcept|random_access_iterator}}, the number of iterator increments is linear.
+
The number of comparisons and applications of the projection performed are logarithmic in the distance between {{c|first}} and {{c|last}} (at most {{math|log{{su|b=2}}(last - first) + O(1)}} comparisons and applications of the projection). However, for an iterator that does not model {{lconcept|random_access_iterator}}, the number of iterator increments is linear.
  
 
===Possible implementation===
 
===Possible implementation===
−
{{eq fun
+
{{eq fun|1=
−
| 1=
+
struct upper_bound_fn
−
struct upper_bound_fn {
+
{
−
  template<std::forward_iterator I, std::sentinel_for<I> S,
+
    template<std::forward_iterator I, std::sentinel_for<I> S,
−
          class T, class Proj = std::identity,
+
            class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
−
          std::indirect_strict_weak_order<
+
            std::indirect_strict_weak_order
−
              const T*,
+
                <const T*, std::projected<I, Proj>> Comp = ranges::less>
−
              std::projected<I, Proj>> Comp = ranges::less>
+
    constexpr I operator()(I first, S last, const T& value,
−
  constexpr I operator()( I first, S last, const T& value,
+
                          Comp comp = {}, Proj proj = {}) const
−
                          Comp comp = {}, Proj proj = {} ) const
+
    {
−
  {
+
        I it;
−
      I it;
+
        std::iter_difference_t<I> count, step;
−
      std::iter_difference_t<I> count, step;
+
        count = ranges::distance(first, last);
−
      count = ranges::distance(first, last);
+
       
−
 
+
        while (count > 0)
−
      while (count > 0) {
+
        {
−
          it = first;  
+
            it = first;  
−
          step = count / 2;
+
            step = count / 2;
−
          ranges::advance(it, step, last);
+
            ranges::advance(it, step, last);
−
          if (!comp(value, std::invoke(proj, *it))) {
+
            if (!comp(value, std::invoke(proj, *it)))
−
              first = ++it;
+
            {
−
              count -= step + 1;
+
                first = ++it;
−
          }
+
                count -= step + 1;
−
          else {
+
            }
−
              count = step;
+
            else
−
          }
+
                count = step;
−
      }
+
        }
−
      return first;
+
        return first;
−
  }
+
    }
−
 
+
   
−
  template<ranges::forward_range R, class T, class Proj = std::identity,
+
    template<ranges::forward_range R, class Proj = std::identity,
−
          std::indirect_strict_weak_order<
+
            class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
−
              const T*,
+
            std::indirect_strict_weak_order
−
              std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
+
                <const T*, std::projected<ranges::iterator_t<R>,
−
  constexpr ranges::borrowed_iterator_t<R>
+
                                          Proj>> Comp = ranges::less>
−
  operator()( R&& r, const T& value, Comp comp = {}, Proj proj = {} ) const
+
    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));
+
        return (*this)(ranges::begin(r), ranges::end(r), value,
−
  }
+
                      std::ref(comp), std::ref(proj));
 +
    }
 
};
 
};
  
 
inline constexpr upper_bound_fn upper_bound;
 
inline constexpr upper_bound_fn upper_bound;
 
}}
 
}}
 +
 +
===Notes===
 +
{{feature test macro|__cpp_lib_algorithm_default_value_type|value=202403|std=C++26|[[cpp/language/list initialization|List-initialization]] for algorithms {{vl|1,2}}}}
  
 
===Example===
 
===Example===
 
{{example
 
{{example
−
|
+
|code=
−
| code=
+
 
#include <algorithm>
 
#include <algorithm>
 +
#include <cassert>
 +
#include <complex>
 
#include <iostream>
 
#include <iostream>
 
#include <iterator>
 
#include <iterator>
Line 103: Line 131:
 
{
 
{
 
     namespace ranges = std::ranges;
 
     namespace ranges = std::ranges;
−
 
+
   
−
     std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
+
     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 lower = ranges::lower_bound(data.begin(), data.end(), 4);
 
         auto upper = ranges::upper_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, " "));
 
         ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
 
         std::cout << '\n';
 
         std::cout << '\n';
Line 116: Line 144:
 
         auto lower = ranges::lower_bound(data, 3);
 
         auto lower = ranges::lower_bound(data, 3);
 
         auto upper = ranges::upper_bound(data, 3);
 
         auto upper = ranges::upper_bound(data, 3);
−
 
+
       
 
         ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
 
         ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
 
         std::cout << '\n';
 
         std::cout << '\n';
 
     }
 
     }
 +
 +
    using CD = std::complex<double>;
 +
    std::vector<CD> nums{<!---->{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}<!---->};
 +
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
 +
    #ifdef __cpp_lib_algorithm_default_value_type
 +
        auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
 +
    #else
 +
        auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
 +
    #endif
 +
    assert((*it == CD{3, 0}));
 
}
 
}
−
| output=
+
|output=
 
4 4 4  
 
4 4 4  
 
3 3 3 3  
 
3 3 3 3  
Line 128: Line 166:
 
===See also===
 
===See also===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/algorithm/ranges/dsc equal_range}}
+
{{dsc inc|cpp/algorithm/ranges/dsc equal_range}}
−
{{dsc inc | cpp/algorithm/ranges/dsc lower_bound}}
+
{{dsc inc|cpp/algorithm/ranges/dsc lower_bound}}
−
{{dsc inc | cpp/algorithm/ranges/dsc partition}}
+
{{dsc inc|cpp/algorithm/ranges/dsc partition}}
−
{{dsc inc | cpp/algorithm/dsc upper_bound}}
+
{{dsc inc|cpp/algorithm/dsc upper_bound}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|es|ja|zh}}
 
{{langlinks|es|ja|zh}}

Latest revision as of 21:34, 20 May 2024

 
C++
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
(C++11)                (C++11)(C++11)

Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17)(C++11)
(C++20)(C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
(C++11)
(C++17)
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
 
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations (on sorted ranges)
       
upper_bound
       
    
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
       
       
Permutation operations
Fold operations
Numeric operations
(C++23)            
Operations on uninitialized storage
Return types
 
Defined in header <algorithm>
Call signature
(1)
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 = {} );
 (since C++20)
(until C++26)
template< std::forward_iterator I, std::sentinel_for<I> S,

          class Proj = std::identity,
          class T = std::projected_value_t<I, Proj>,
          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 = {} );
 (since C++26)
(2)
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 = {} );
 (since C++20)
(until C++26)
template< ranges::forward_range R,

          class Proj = std::identity,
          class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
          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 = {} );
 (since C++26)
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 log2(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 Proj = std::identity, class T = std::projected_value_t<I, Proj>,
             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, std::invoke(proj, *it)))
            {
                first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
 
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             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] Notes

Feature-test macro Value Std Feature
__cpp_lib_algorithm_default_value_type 202403 (C++26) List-initialization for algorithms (1,2)

[edit] Example

Run this code
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    namespace ranges = std::ranges;
 
    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';
    }
 
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
    #else
        auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it == CD{3, 0}));
}

Output: 

4 4 4 
3 3 3 3

[edit] See also

(C++20)
 returns range of elements matching a specific key
(niebloid)[edit]
(C++20)
 returns an iterator to the first element not less than the given value
(niebloid)[edit]
(C++20)
 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]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/upper_bound&oldid=171929"