О Во второй форме вызов бинарного предиката op(elem,searchElern) для соответствующих элементов искомого интервала и подинтервала должен возвращать true.

О Если подходящий элемент пе найден, обе формы возвращают end.

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

О Предикат ор не должен изменять передаваемые аргументы.

О Проблема поиска интервала по известным значениям начального и конечного элементов рассматривается на с. 109.

О Эти алгоритмы не входили в исходную версию STL. К сожалению, им было присвоено имя find end() вместо search end(), что было бы гораздо логичнее, поскольку алгоритм поиска первого подинтервала называется search().

О Сложность линейная (не более numberOfElementsx.numberofSearchElements сравнений или вызовов ор соответственно).

Следующий пример показывает, как найти последнее вхождение серии элементов внутри другой последовательности (сравните с примером использования алгоригма search() на с. 345):

algo/flndendl.cpp #1nclude "algostuff.hpp" using namespace std;

Int ma1n()

deque<int> col 1; 11st<"int> subcoll;

INSERT ELEMENTS(coll.l.7): INSERT ELEMENTS(C0ll.l.7);

INSERTJLEMENTS(subcoll.3.6);

PRiNTJLEMENTSCcoll. "coll: "); PRINTJLEMENTSCsubCOl 1. "subcol 1 : ");

Поиск поспеднего вхождения subcoll в coll deque<1nt>::Iterator pos;

pos - f1nd end Ccoll .beginO. coll.endO. Интервал ,

subcoll .beginC). subcoll .endO); Подинтервал

Цикл повторяется до тех пор. пока внутри coll успешно находится очередное вхождение подинтервала deque<int>;;Iterator endCcoll.endC)): while (pos != end) {

Вывод позиции первого элемента

cout « "Subcoll found starting with element " « dIstanceCcoll .beginO.pos) + 1 « endl:

Поиск следующего вхождения subcoll end = pos:

pos - find end (coll.beginO. end. Интервал

subcoll.beginO. subcoll .endO): Подинтервал

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

coll; 12 3 4 5 6 7 8 9 subcoll; 3 4 5 6

subcoll found starting with element 10 subcoll found starting with element 3

Что касается второй формы алгоритма, обратитесь к примеру использования второй формы алгоритма search() на с. 346 - алгоритм find end() применяется аналогичным образом.

Поиск первого из нескольких возможных значений

Forwardlterator

f1nd first of (Forwardlteratorl beg. Forwardlteratorl end.

ForwardIterator2 searchBeg. ForwardIterator2 searchEnd)

Forwardlterator

f1nd first of (Forwardlteratorl beg. Forwardlteratorl end.

ForwardIterator2 searchBeg. ForwardIterator2 searchEnd. BinaryPredicate op)

О Первая форма возвращает позицию первого элемента в интервале [beg,€nd), значение которого также встречается в интервале [searchBeg,searchEnd).

О Вторая форма возвращает позицию первого элемента в интервале [beg,end), для которого вызов предиката op(etem,searchElem) с элементами интервала \searchBeg,searchEnd) возвращает true.

О Если подходящий элемент не найден, обе формы возвращают end.

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

О Предикат ор не должен изменять передаваемые аргументы.

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

О Алгоритмы не входили в исходную версию STL.

О Сложность линейная (не более numberOfElementsnumberofSearchElements сравнений или вызовов ор соответственно).

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

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

1nt mainC) {

vector<int> col 1: I1st<int> searchcoll:

INSERT ELEMENTS(coll.1.11): INSERT ELEMENTS(searchcoll.3.5):

PRiNTJLEMENTSCcoll, "coll: "):

PRINTJLEMENTSCsearchcoll ."searchcoll: ");

Поиск в coll первого вхождения элемента из searchcoll vector<1nt>;;iterator pos;

pos = findJ1rst of (coll.beginO. coll.endO. Интервал

searchcoll,beginO. Начало искомых значений searchcoll.endO): Конец искомых значений cout « "first element of searchcoll in coll is element " « distance(coll .beginO.pos) + 1 « endl:

Поиск в coll последнего вхождения search элемента из searchcoll vector<i nt>::reverse i terator rpos:

rpos = findJirst of (coll .rbeginO. coll.rendO. Интервал

searchcol1.beginC). Начало искомых значений searchcoll .endO): Конец искомых значений cout « "last element of searchcoll in coll is element " « distanceCcoll .beginO.rpos.baseO) « endl:

Второй вызов использует обратные итераторы для поиска последнего элемента со значением, равным значению одного из элементов searchcolL При выводе позиции элемента вызывается функция base(), которая преобразует обратный итератор в обычный (чтобы позиция отсчитывалась от начала коллекции). Обычно к результату distanceO прибавляется 1, так как для первого элемента расстояние равно О, однако base() смещает логическую позицию, на которую ссылается итератор, что приводит к желаемому эффекту (функция base() описана на с. 274).

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

coll: 1 2 3 4 5 6 7 8 9 10 11

searchcoll: 3 4 5

first element of searchcoll in coll is element 3 last element of searchcoll in coll is element 5