int mainO {

list<int> coll; vector<int> search;

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

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

Проверка вхождения всех элементов search в coll 1f (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; PRINTJLEMENTSCcoll):

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

posl = lowerjound (coll.beginO. coll.endO.

pos2 = upperjound (coll.beginO, coll.endO.

cout « "5 could get position "

« distanceCcoll.beginO,posl) + 1 « up to "

« distanceCcoll.beginO,pos2) + 1

« " without breaking the sorting" « endl:

Вставка 3 в первой возможной позиции без нарушения упорядоченности coll .insert Clower boundCcoll .beginO.coll .endO.

Вставка 7 в первой возможной позиции без нарушения упорядоченности coll.insert Cupper boundCcoll.beginC).coll.endC).

PRiNTJLEMENTSCcoll);

Программа выводит следующий результат: 112233445566778899

5 could get position 9 up to И without breaking the sorting 1122334455667778899

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

pai r<Forwa rdIterator.Forwardlterator>

equal range (Forwardlterator beg. Forwardlterator end. const T& value) pair<ForwardIterator.Forwardlterator>

equal range (Forwardlterator beg. Forwardlterator end. const T& value. BinaryPredicate op)

О Обе формы возвращают интервал значений, равных value. Интервал определяет nepBjno и последнюю позиции, в пределах которых элемент со значением value вставляется без нарушения упорядоченности интервала [beg,end).

О Алгоритм эквивалентен вызову

make pair(lower bound(...).upperJound(...))

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

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

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

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