Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | algorithm‎ | ranges
m (fix numbering)
m (FTM.)
 
(14 intermediate revisions by 9 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 lower_bound( I first, S last, const T& value,
−
constexpr I
+
                        Comp comp = {}, Proj proj = {} );
−
lower_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 >
−
lower_bound( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
+
constexpr I lower_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>
 +
    lower_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>
 +
    lower_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 ''not less'' than (i.e. greater or equal to) {{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 ''not less'' than (i.e. greater or equal to) {{c|value}}, or {{c|last}} if no such element is found.
−
The range {{tt|[first, last)}} must be partitioned with respect to the expression {{c|comp(element, value)}}, 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 {{c|std::invoke(comp, std::invoke(proj, element), value)}}, 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 pair defining the partially-ordered range to examine}}
+
{{par|first, last|iterator-sentinel pair 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 projected elements to}}
−
{{par | pred | predicate to apply to the projected elements}}
+
{{par|comp|comparison 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 ''not less'' than {{tt|value}}, or {{tt|last}} if no such element is found.
+
Iterator pointing to the first element that is ''not less'' 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-sentinel pair that does not satisfy {{lconcept|sized_sentinel_for}} or a range that does not satisfy {{lconcept|sized_range}}, 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===
+
===Notes===
−
{{eq fun | 1=
+
On a range that's fully sorted (or more generally, partially ordered with respect to {{c|value}}) after projection, {{tt|std::ranges::lower_bound}} implements the binary search algorithm. Therefore, {{lc|ranges::binary_search|std::ranges::binary_search}} can be implemented in terms of it.
−
struct lower_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 = std::ranges::distance(first, last);
+
−
 
+
−
      while (count > 0) {
+
−
          it = first;
+
−
          step = count / 2;
+
−
          ranges::advance(it, step, last);
+
−
          if (comp(*it, value)) {
+
−
              first = ++it;
+
−
              count -= step + 1;
+
−
          }
+
−
          else {
+
−
              count = step;
+
−
          }
+
−
      }
+
−
      return first;
+
−
  }
+
  
−
  template<ranges::forward_range R, class T, class Proj = std::identity,
+
{{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}}}}
−
          std::indirect_strict_weak_order<
+
 
−
              const T*,
+
===Possible implementation===
−
              std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less>
+
{{eq fun|1=
−
  constexpr ranges::borrowed_iterator_t<R>
+
struct lower_bound_fn
−
  operator()( R&& r, const T& value, Comp comp = {}, Proj proj = {} ) const
+
{
−
  {
+
    template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
−
    return (*this)(ranges::begin(r), ranges::end(r), value,
+
            class T = std::projected_value_t<I, Proj>,
−
                  std::ref(comp), std::ref(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 = std::ranges::distance(first, last);
 +
       
 +
        while (count > 0)
 +
        {
 +
            it = first;
 +
            step = count / 2;
 +
            ranges::advance(it, step, last);
 +
            if (comp(std::invoke(proj, *it), value))
 +
            {
 +
                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));
 +
    }
 
};
 
};
  
Line 92: Line 122:
 
===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 134:
 
template<std::forward_iterator I, std::sentinel_for<I> S, class T,
 
template<std::forward_iterator I, std::sentinel_for<I> S, class T,
 
         class Proj = std::identity,
 
         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 binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
−
I binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
+
 
{
 
{
 
     first = ranges::lower_bound(first, last, value, comp, proj);
 
     first = ranges::lower_bound(first, last, value, comp, proj);
−
     return first != last && !comp(value, *first) ? first : last;
+
     return first != last && !comp(value, proj(*first)) ? first : last;
 
}
 
}
  
 
int main()
 
int main()
 
{
 
{
−
     std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
+
     std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
−
 
+
    //                                ^^^^^^^^^^
 
     auto lower = ranges::lower_bound(data, 4);
 
     auto lower = ranges::lower_bound(data, 4);
 
     auto upper = ranges::upper_bound(data, 4);
 
     auto upper = ranges::upper_bound(data, 4);
  
 +
    std::cout << "found a range [" << ranges::distance(data.cbegin(), lower)
 +
              << ", " << ranges::distance(data.cbegin(), upper) << ") = { ";
 
     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';
+
  
 
     // classic binary search, returning a value only if it is present
 
     // classic binary search, returning a value only if it is present
  
−
     data = { 1, 2, 4, 6, 9, 10 };  
+
     data = {1, 2, 4, 8, 16};
 +
    //              ^
 +
    auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end()
  
−
    auto it = binary_find(data.cbegin(), data.cend(), 4); //< choosing '5' will return end()
+
     if (it != data.cend())
−
+
        std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);
−
     if(it != data.cend())
+
−
      std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);
+
  
−
     return 0;
+
     using CD = std::complex<double>;
 +
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
 +
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
 +
    #ifdef __cpp_lib_algorithm_default_value_type
 +
        auto it2 = ranges::lower_bound(nums, {2, 0}, cmpz);
 +
    #else
 +
        auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz);
 +
    #endif
 +
    assert((*it2 == CD{2, 2}));
 
}
 
}
−
| output=
+
|output=
−
4 4 4  
+
found a range [6, 10) = { 4 4 4 4 }
−
4 found at index 2
+
8 found at index 3
 
}}
 
}}
  
 
===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 partition}}
+
{{dsc inc|cpp/algorithm/ranges/dsc partition}}
−
{{dsc inc | cpp/algorithm/ranges/dsc partition_point}}
+
{{dsc inc|cpp/algorithm/ranges/dsc partition_point}}
−
{{dsc inc | cpp/algorithm/ranges/dsc upper_bound}}
+
{{dsc inc|cpp/algorithm/ranges/dsc upper_bound}}
−
{{dsc inc | cpp/algorithm/dsc lower_bound}}
+
{{dsc inc|cpp/algorithm/dsc lower_bound}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|es|ja|zh}}
 
{{langlinks|es|ja|zh}}

Latest revision as of 21:32, 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)
lower_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 lower_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 lower_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>

    lower_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>

    lower_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 not less than (i.e. greater or equal to) value, or last if no such element is found. The range [first, last) must be partitioned with respect to the expression std::invoke(comp, std::invoke(proj, element), value), 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 pair defining the partially-ordered range to examine
r - the partially-ordered range to examine
value - value to compare the projected elements to
comp - comparison 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 not less 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] Notes

On a range that's fully sorted (or more generally, partially ordered with respect to value) after projection, std::ranges::lower_bound implements the binary search algorithm. Therefore, std::ranges::binary_search can be implemented in terms of it.

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

[edit] Possible implementation

struct lower_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 = std::ranges::distance(first, last);
 
        while (count > 0)
        {
            it = first;
            step = count / 2;
            ranges::advance(it, step, last);
            if (comp(std::invoke(proj, *it), value))
            {
                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 lower_bound_fn lower_bound;

[edit] Example

Run this code
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
 
namespace ranges = std::ranges;
 
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 binary_find(I first, S last, const T& value, Comp comp = {}, Proj proj = {})
{
    first = ranges::lower_bound(first, last, value, comp, proj);
    return first != last && !comp(value, proj(*first)) ? first : last;
}
 
int main()
{
    std::vector data{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
    //                                 ^^^^^^^^^^
    auto lower = ranges::lower_bound(data, 4);
    auto upper = ranges::upper_bound(data, 4);
 
    std::cout << "found a range [" << ranges::distance(data.cbegin(), lower)
              << ", " << ranges::distance(data.cbegin(), upper) << ") = { ";
    ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "}\n";
 
    // classic binary search, returning a value only if it is present
 
    data = {1, 2, 4, 8, 16};
    //               ^
    auto it = binary_find(data.cbegin(), data.cend(), 8); // '5' would return end()
 
    if (it != data.cend())
        std::cout << *it << " found at index "<< ranges::distance(data.cbegin(), it);
 
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it2 = ranges::lower_bound(nums, {2, 0}, cmpz);
    #else
        auto it2 = ranges::lower_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it2 == CD{2, 2}));
}

Output: 

found a range [6, 10) = { 4 4 4 4 }
8 found at index 3

[edit] See also

(C++20)
 returns range of elements matching a specific key
(niebloid)[edit]
(C++20)
 divides a range of elements into two groups
(niebloid)[edit]
(C++20)
 locates the partition point of a partitioned range
(niebloid)[edit]
(C++20)
 returns an iterator to the first element greater than a certain value
(niebloid)[edit]
returns an iterator to the first element not less than the given value
(function template) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/lower_bound&oldid=171927"