FreeBSD Manual Pages
std::lower_bound(3) C++ Standard Libary std::lower_bound(3) NAME std::lower_bound - std::lower_bound Synopsis Defined in header <algorithm> template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, (until C++20) ForwardIt last, const T& value ); template< class ForwardIt, class T > constexpr ForwardIt lower_bound( ForwardIt (since C++20) first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > (1) (until C++20) ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); template< class ForwardIt, class T, class (2) Compare > constexpr ForwardIt lower_bound( ForwardIt (since C++20) first, ForwardIt last, const T& value, Compare comp ); Returns an iterator pointing to the first element in the range [first, last) that does not satisfy element < value (or comp(element, value)), (i.e. greater or equal to), or last if no such element is found. The range [first, last) must be partitioned with respect to the ex- pression element < value (or comp(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. The first version uses operator< to compare the elements, the second version uses the given comparison function comp. Parameters first, last - iterators defining the partially-ordered range to examine value - value to compare the elements to binary predicate which returns true if the first ar- gument is less than (i.e. is ordered before) the second. The signature of the predicate function should be equivalent to the following: bool pred(const Type1 &a, const Type2 &b); comp - While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 re- gardless of value category (thus, Type1 & is not allowed , nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implic- itly converted to Type2. Type requirements - ForwardIt must meet the requirements of LegacyForwardIterator. - Compare must meet the requirements of BinaryPredicate. it is not re- quired to satisfy Compare Return value Iterator pointing to the first element in the range [first, last) such that element < value (or comp(element, value)) is false, or last if no such ele- ment is found. Complexity The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-LegacyRando- mAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::lower_bound (resp. std::multiset::lower_bound) should be preferred. Possible implementation See also the implementations in libstdc++ and libc++. First version template<class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (*it < value) { first = ++it; count -= step + 1; } else count = step; } return first; } Second version template<class ForwardIt, class T, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (comp(*it, value)) { first = ++it; count -= step + 1; } else count = step; } return first; } Example // Run this code #include <algorithm> #include <iostream> #include <vector> struct PriceInfo { double price; }; int main() { const std::vector<int> data = { 1, 2, 4, 5, 5, 6 }; for (int i = 0; i < 8; ++i) { // Search for first element x such that i x auto lower = std::lower_bound(data.begin(), data.end(), i); std::cout << i << " "; lower != data.end() ? std::cout << *lower << " at index " << std::dis- tance(data.begin(), lower) : std::cout << "not found"; std::cout << '\n'; } std::vector<PriceInfo> prices = { {100.0}, {101.5}, {102.5}, {102.5}, {107.3} }; for(double to_find: {102.5, 110.2}) { auto prc_info = std::lower_bound(prices.begin(), prices.end(), to_find, [](const PriceInfo& info, double value){ return info.price < value; }); prc_info != prices.end() ? std::cout << prc_info->price << " at index " << prc_info - prices.begin() : std::cout << to_find << " not found"; std::cout << '\n'; } } Output: 0 1 at index 0 1 1 at index 0 2 2 at index 1 3 4 at index 2 4 4 at index 2 5 5 at index 3 6 6 at index 5 7 not found 102.5 at index 2 110.2 not found Defect reports The following behavior-changing defect reports were applied retroac- tively to previously published C++ standards. DR Applied to Behavior as published Correct behavior LWG 270 C++98 Compare was required to be a only a partitioning is needed; strict weak ordering heterogeneous com- parisons permitted See also equal_range returns range of elements matching a specific key (function template) partition divides a range of elements into two groups (function template) partition_point locates the partition point of a partitioned range (C++11) (function template) returns an iterator to the first element greater than a certain upper_bound value (function template) returns an iterator to the first element not less than the given lower_bound key (public member function of std::set<Key,Com- pare,Allocator>) returns an iterator to the first element not less than the given lower_bound key (public member function of std::multi- set<Key,Compare,Allocator>) ranges::lower_bound returns an iterator to the first element not less than the given (C++20) value (niebloid) http://cppreference.com 2022.07.31 std::lower_bound(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Possible implementation | First version | Second version | Example | Output: | See also
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::lower_bound&sektion=3&manpath=FreeBSD+Ports+15.0>