std::upper_bound
![]() |
Эта страница была переведена автоматически с английской версии вики используя Переводчик Google.
Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке. Щёлкните здесь, чтобы увидеть английскую версию этой страницы |
Определено в заголовочном файле <algorithm>
|
||
template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value ); |
(1) | |
template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ); |
(2) | |
[first, last)
то есть' больше, чем value
. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp
.[first, last)
that is greater than value
. The first version uses operator< to compare the elements, the second version uses the given comparison function comp
.Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
Содержание |
[править] Параметры
first, last | - | диапазон элементов для изучения
Оригинал: the range of elements to examine Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. |
value | - | Значение для сравнения элементов
Оригинал: value to compare the elements to Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. |
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 .
|
[править] Возвращаемое значение
value
, или last
, если такой элемент не найден.value
, or last
if no such element is found.Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
[править] Возможная реализация
Первый вариант |
---|
template<class ForwardIt, class T> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value) { ForwardIt it; std::iterator_traits<ForwardIt>::distance_type count, step; count = std::distance(first,last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!(value < *it)) { first = ++it; count -= step + 1; } else count = step; } return first; } |
Второй вариант |
template<class ForwardIt, class T, class Compare> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) { ForwardIt it; std::iterator_traits<ForwardIt>::distance_type count, step; count = std::distance(first,last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (!comp(value, *it)), 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
[править] Сложность
first
и last
first
and last
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
[править] См. также
возвращает набор элементов для конкретного ключа Оригинал: returns range of elements matching a specific key Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. (шаблон функции) | |
возвращает итератор на первый элемент' не менее, чем заданное значение Оригинал: returns an iterator to the first element not less than the given value Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда. (шаблон функции) |