Поиск первого подинтервала

Forwardlteratorl

search (Forwardlteratorl beg. Forwardlteratorl end.

ForwardIterator2 searchBeg. ForwardIterator2 searchEnd)

Forwardlteratorl

search (Forwardlteratorl beg. Forwardlteratorl end.

ForwardIterator2 searchBeg. ForwardIterator2 searchEnd. BinaryPredicate op)

О Обе формы возвращают позицию первого элемента в первом Подинтервале интервала [beg,end), совпадающем с искомым интервалом [searchBegsearchEnd).

О В первой форме элементы найденного подинтервала должны быть равны элементам искомого интервала.

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

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

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

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

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

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

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

algo/searchl.cpp finclude "algostuff.hpp" using namespace std:

int mainO {

deque<int> coll; llst<int> subcoll:

INSERTJLEMENTS(C011.1.7): INSERT ELEMENTS(C0ll.l.7);

INSERT ELEMENTS(subcoll.3.6):

PRINT ELEMENTS(coll. "coll: "): PRINT ELEMENTS(SubColl."subcoll: "):

Поиск первого вхождения subcoll в coll deque<int>;:iterator pos;

pos = search Ccoll .beginO, coll.endO. Интервал

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

Цикл повторяется до тех пор. пока внутри coll успешно находится очередное вхождение subcoll while Cpos != coll .endO) {

Вывод позиции первого элемента cout « "subcoll found starting with element " « distanceCcoU-beginO.pos) + 1 « endl;

Поиск следующего вхождения subcoll ++pos;

pos = search (pos. coll.endO, Интервал

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

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

coll: 12345671234567 subcoll; 3 4 5 6

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

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

algo/-search2.cpp finclude "algostuff.hpp" using namespace std;

Проверка элемента на четность bool checkEven (int elem. bool even) {

if (even) {

return elem 2 == 0;

else {

return elem 2 == 1;

int mainO {

vector<1nt> coll;

INSERT ELEMENTSCcoll.1.9):

PRINTJLEMENTSCcoll."coll: "): /* Аргументы checkEvenO

* - проверка последовательности "чет нечет чет" */

bool checkEvenArgs[3] = { true, false, true };

Поиск первого подинтервала в coll vector<int>::1terator pos:

pos = search Ccoll.beginC). coll.endO. Интервал

checkEvenArgs. checkEvenArgs+3. Значения подинтервала checkEven); Критерий

Цикл повторяется до тех пор. пока внутри coll

успешно находится очередное вхождение подинтервала

while (pos != coll .endO) {

Вывод позиции первого элемента cout « "subrange found starting with element " « distance(coll-beginO.pos) + 1 « endl:

Поиск следующего подинтервала в coll

pos = search (++pos, coll.endO, Интервал

CheckEvenArgs. checkEvenArgs+3. Значения checkEven): Критерий

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

coll: 123456789 subrange found starting with element 2 subrange found starting with element 4 subrange found starting with element 6

Поиск последнего подинтервала

Forwardlterator

flnd end (Forwardlterator beg. Forwardlterator end.

Forwardlterator searchBeg. Forwardlterator searchEnd)

Forwardlterator

f1nd end (Forwardlterator beg. Forwardlterator end.

Forwardlterator searchBeg. Forwardlterator searchEnd. BinaryPredicate op)

О Обе формы возвращают позицию первого элемента в последнем подинтервале интервала [beg,end), совпадающем с искомьшл интервалом [searchBeg,searchEnd).

О В первой форме элементы найденного подинтерва.т1а должны быть равны элементам искомого интервала.