upper_bound

Структуры и функции   20 января 2012  Автор статьи:  

Пусть имеется контейнер, упорядоченный на полуинтервале [first, last). Тогда значением функции является итератор, указывающий на первый элемент из данного диапазона, который строго больше заданного значения value. Если в заданном промежутке такого элемента нет, то функция возвращает итератор last в качестве значения.
Библиотека
stdlib.h

Способы вызова функции

ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value );
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );

Где

  • first — итератор, указывающий на начало промежутка, в котором осуществляется поиск
  • last — итератор, указывающий на правую границу (не включительно) промежутка поиска
  • value — значение, относительно которого осуществляется поиск большего элемента
  • comp — компаратор, согласно которому была произведена сортировка контейнера в заданном промежутке

Сложность

Функция имеет логарифмическую сложность от длины промежутка поиска.

Примеры

#include
#include
#include
using namespace std;

int main()
{
int p;
int a[] = {-3, 2, 5, 4, 7, -1, 2, 8, 9, -4};
vector v (a, a + 10);

sort (a, a + 10);
sort (v.begin(), v.end());

//После сортировки массив и вектор приняли вид
// -4 -3 -1 2 2 4 5 7 8 9

p = *upper_bound (a, a + 10, 2);
//Значением переменной p будет число 4

p = *upper_bound (v.begin(), v.end(), 6);
//Значением переменной p будет число 7

p = *upper_bound (v.begin(), v.end(), 9);
//Такое выражение вызовет Runtime Error, так как в массиве все числа меньше либо равны 9
//upper_bound вернет итератор, равный v.end(), указывающий на несуществующий элемент

return 0;
}

Замечания

Функция часто применяется для нахождения числа элементов упорядоченного массива, строго больших данного.
Эту величину можно вычислить как int (last — upper_bound (first, last, value)).
Упорядоченный контейнер set имеет встроенную функцию upper_bound, но так как итераторы контейнера set нельзя вычитать, то предыдущее замечание в этом случае неверно.

Научиться программировать

  • на Delphi

  • на Java

  • на C++