std::lower_bound
cppreference.com
<tbody>
</tbody>
template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); |
(1) | |
template< class ForwardIt, class T, class Compare > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(2) | |
[first, last) ( ) value.
(1) operator< .
(2) comp.
[first, last)
|
, | |
value
|
||
comp
|
(.. , Compare), true, "", .:
| |
-ForwardIterator.
| ||
, , ( ), value, last .
[first, last)
template<class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value)
{
ForwardIt it;
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;
}
|
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
ForwardIt it;
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;
}
|
#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 = std::lower_bound(data.begin(), data.end(), 4);
auto upper = std::upper_bound(data.begin(), data.end(), 4);
std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
}
:
4 4 4
.
| , ( ) | |
| , ( ) |