Namespaces
Variants
Actions

std::ranges::lower_bound

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
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)
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
(C++11)
Minimum/maximum operations
(C++11)
(C++17)
Lexicographical comparison operations Permutation operations


C library
Numeric operations
 
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
(C++23)
(C++23)  
(C++23)
(C++23)  
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 algorithm function objects (informally known as niebloids), that is:

Contents

[edit] Parameters

first, last - the iterator-sentinel pair defining the partially-ordered range of elements 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

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

AltStyle によって変換されたページ (->オリジナル) /