else {

cout 5 is not present endl;

Проверка существования элемента со значением 42 if (binary search(coll .beginO, coll.endO, 42)) { cout 42 is present endl;

else {

cout 42 is not present endl;

Результат выполнения программы выглядит так:

12 3 4 5 6 7 8 9

5 Is present

42 is not present

Проверка присутствия нескольких элементов

bool

includes (Inputlteratorl beg. Inputlteratorl end.

InputIterator2 searchBeg. InputIterator2 searchEnd)

bool

includes (Inputlteratorl beg. Inputlteratorl end.

Inputlteratar2 searchBeg. InputIterator2 searchEnd. BinaryPredicate op)

О Обе формы проверяют, содержит ли зшорядоченный интервал [beg,end) все элементы зшорядоченного интервала [searchBeg,searchEnd), и возвращают результат в виде логической величины. Иначе говоря, для каждого элемента интервала [searchBeg,searchEnd) должен существовать равный элемент в интервале [beg, end). Если некоторые элементы интервала [searckBeg,searckEnd) равны, то в интервале [beg,end) должно присутствовать такое же количество дубликатов. Таким образом, интервал [searchBeg,searchEnd) должен быть подмножеством интервала [beg,end).

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1,elem2).

О Перед вызовом оба интервала должны быть упорядочены но одному критерию сортировки,

о Сложность линейная (не более 2x(numberOfElements+searchElements)-\ сравнений).

Пример использования алгоритма lncludes():

algo/includes.cpp #include algostuff.hpp using namespace std:

int malnO {

llst<int> coll; vector<1nt> search;

INSERT ELEMENTS(coll.l.9): PRiNTJLEMENTSCcoll. coll: ):

search,pushjack(3) search,pushjack(4) search,push Jack(7) PRINTJLEMENTSCsearch, search: );

Проверка вхождения всех элементов search в coll if (includes (coll ,begin(). coll.endO.

search.beginO. search.endO)) { cout all elements of search are also in coll endl;

else {

cout not all elements of search are also in coll endl;

Результат выполнения программы выглядит так;

coll: 12 3 4 5 6 7 8 9 search: 3 4 7

all elements of search are also in coll

Поиск первой или последней возможной позиции

Forwardlterator

lowerjound (Forwardlterator beg. Forwardlterator end. const T& value) Forwardlterator

lowerjound (Forwardlterator beg, Forwardlterator end. const T& value, BinaryPredicate op)

Forwardlterator

upperjound (Forwardlterator beg, Forwardlterator end. const T& value) Forwardlterator

upperjound (Forwardlterator beg. Forwardlterator end, const T& value. BinaryPredicate op)

О Алгоритм lower bound() возвращает позицию первого элемента со значением, большим либо равным value. Результат определяет первую позицию, в которой элемент со значением value вставляется без нарушения упорядоченности интервала [beg,end).

О Алгоритм upper bound() возвращает позицию первого элемента со значением, большим value. Результат определяет первую позицию, в которой элемент со значением value вставляется без нарушения упорядоченности интервала [begjend).

О Если позицию найти не удалось, оба алгоритма возвращают end.

О В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки: op(elem1relem2).

О Перед вызовом интервал должен быть упорядочен но соответствующему критерию сортировки.

О Чтобы одновременно получить результаты алгоритмов lower bound() и upper boundQ, воспользуйтесь алгоритмом equal range(), который возвращает оба значения (см. далее).

О В ассоциативных контейнерах (множество, мультимножество, отображение и мультиотображение) определены эквивалентные функции, которые работают более эффективно (см. с. 239).

О Сложность логарифмическая для итераторов произвольного доступа, линейная в остальных случаях (не более \og(numberOfElements)+l сравнений, но для итераторов, не являющихся итераторами произвольного доступа, выполняется линейное количество операций перебора, вследствие чего сложность оказывается линейной).

Пример использования алгоритмов lower bound() и upper bound():

algo/boundsl.cpp #include algostuff,hpp using namespace std;

int mainO {

list<int> coll:

INSERTJLEMENTS(col 1.1.9); INSERT ELEMENTS(C011,1.9); coll .sort 0; PRlNT ELEMENTS(coll):

Вывод первой и последней позиций, в которых может быть вставлен элемент со значением 5 list<int>::iterator posl. pos2:

posl = lower bound (coll.beginO. coll.endO.

pos2 = upper bound (coll.beginO, coll.endO.