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, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: bool cmp(const Type1 &a, const Type2 &b); Использование noexcept (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по const&, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже const) |
| Требования к типам | ||
-ForwardIt должен соответствовать требованиям 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
[править] См. также
| возвращает диапазон элементов, соответствующих определённому ключу (шаблон функции) | |
| возвращает итератор на первый элемент, который больше определённого значения (шаблон функции) |
