std::lower_bound
![]() |
This page has been machine-translated from the English version of the wiki using Google Translate.
The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here. |
Определено в заголовочном файле <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) | |
Returns an iterator pointing to the first element in the range [first, last)
that is not less than value
. The first version uses operator< to compare the elements, the second version uses the given comparison function comp
.
Содержание |
[править] Параметры
first, last | - | iterators defining the range to examine |
value | - | Значение для сравнения элементов
Оригинал: value to compare the elements to Текст был переведён автоматически через Google Translate. Вы можете проверить и исправить перевод. Для инструкций кликните сюда. |
comp | - | comparison function which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function must not modify the objects passed to it. |
Требования к типам | ||
-ForwardIt должен соответствовать требованиям ForwardIterator .
|
[править] Возвращаемое значение
Iterator pointing to the first element that is not less than value
, or last
if no such element is found.
[править] Сложность
first
и last
first
and 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
[править] См. также
возвращает набор элементов для конкретного ключа Оригинал: returns range of elements matching a specific key Текст был переведён автоматически через Google Translate. Вы можете проверить и исправить перевод. Для инструкций кликните сюда. (шаблон функции) | |
возвращает итератор на первый элемент' больше, чем определенное значение Оригинал: returns an iterator to the first element greater than a certain value Текст был переведён автоматически через Google Translate. Вы можете проверить и исправить перевод. Для инструкций кликните сюда. (шаблон функции) |