std::lower_bound
| Определено в заголовочном файле <algorithm>
|
||
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
См. также
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) | |
| возвращает итератор на первый элемент, который больше определённого значения (шаблон функции) |
