486 ___________Часть III. Современное программирование на C++

lower_bound. Алгоритм находит первое место во входной последовательности, на которое можно поместить значение value, не нарушая при этом упорядоченности этой последовательности. Ясно, что эта функция работает с сортируемыми контейнерами. Возвращаемое значение указывает на позицию в последовательности, куда можно поместить value.

template <class Forwardlterator, class T> Forwardlterator lower bound (Forwardlterator first,

Forwardlterator last,

const T& value);

template <class Forwardlterator, clas T, class Compare>

Forwardlterator lower_bound (Forwardlterator first, Forwardlterator last, const T& value. Compare comp);

upper_bound. Как и lower_bound предназначен для сортируемых контейнеров. Он возвращает указатель на последнюю позицию в которую можно вставить некоторый элемент, не нарушая упорядоченности контейнера.

template <class Forwardlterator, class T> Forwardlterator upper bound (Forwardlterator first,

Forwardlterator last,

const T& value) ;

template <class Forwardlterator, class T, class Compare>

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

equaLrcirige. Этот алгоритм — комбинация алгоритмов lower_bound и upper_bound. Он находит во входной последовательности отрезок, в который может быть вставлено значение value, не нарушая упорядоченности. Возвращаемое значение — это экземпляр класса-шаблона pair. При этом первый параметр — это результат выполнения функции iower_boupd, а второй —

upper_bound.

template <class Forwardlterator, class T> pair <ForwardIterator, Forwardlterator> equal_range (Forwardlterator first, Forwardlterator last, const T& value);

template <class Forwardlterator, class T, class Compare> pair <ForwardIterator, Forwardlterator> equal_range (Forwardlterator first, Forwardlterator last, const T& value. Compare comp) ;

binary_search. В упорядоченной входной последовательности ищет значение value и возвращает истину если находит, и ложь — в противном случае.