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 — компаратор, согласно которому была произведена сортировка контейнера в заданном промежутке

Сложность

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

Примеры

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int p;
    int a[] = {-3, 2, 5, 4, 7, -1, 2, 8, 9, -4};
    vector <int> 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++