printdt. it + BSZ. find first of , ): it = find first of(v.begin(), v.endO.

b. b + BSZ. PlusOneO); print(it,it + BSZ. find first of PlusOne , ); it = search(v.begin(), v.endO. b, b + BSZ); print(it, it + BSZ. search . ); int c[] = { 5, 6, 7 }; const int CSZ = sizeof с / sizeof *c; printCc. с + CSZ, c , );

it = search(v.beginO. v.endO. c, с + CSZ. PlusOneO);

print(it. it + CSZ. search PlusOne . );

int d[] = { 11, 11. 11 };

const int DSZ = sizeof d / sizeof *d;

printed, d + DSZ. d , );

it = find end(v.begin(). v.endO, d. d + DSZ);

print(it, v.end(). find end . );

int e[] = { 9. 9 };

print(e. e + 2. e , );

it = find end(v.begin(). v.endO. e. e + 2. PlusOneO); print(it. v.end(), find end PlusOne . ); it = search n(v.begin(). v.endO. 3. 7); print(it, it + 3. search n 3. 7 , ); it = search n(v.begin(). v.endO.

6. 15. MulMoreThan(lOO)); printCit. it + 6.

search n 6, 15. MulMoreThan(lOO) . ) cout min element;

*min element(v.begin(). v.endO) endl cout max element;

*max element(v.begin(). v.endO) endl vector<int> v2;

replace copy(v.begin(). v.endO.

back inserter(v2), 8, 47); print(v2.beginO. v2.end(). replace copy 8 ->47 . ); replace if(v.begin(), v.endO,

bind2nd(greater equal<int>(). 7), -1); printCv.beginO, v.endO. replace if >= 7 -> -1 . ); } /;-

В начале примера определяются два предиката. Бинарный предикат PlusOne возвращает true, если второй аргумент на 1 больше второго аргумента, а MulMoreThan возвращает true, если первый аргумент равен произведению на второй аргумент значения, хранящегося в объекте.

Функция main() создает массив а и передает его конструктору vector<int> v. Этот вектор используется для выполнения операций поиска и замены. Обратите внимание на присутствие дубликатов - они обнаруживаются некоторыми алгоритмами поиска и замены.

Первый тест демонстрирует алгоритм find() на примере поиска значения 4 в v. Возвращаемое значение представляет собой итератор, указывающий на первое вхождение 4 или на конец входного интервала (v.end()), если искомое значение не найдено.

Алгоритм find if() использует предикат для проверки элементов. В нашем примере предикат строится на месте при помощи стандартного объекта функции greater<int> (то есть проверяет, что первый аргумент типа int больше второго аргумента ) и адаптера bind2nd(), который фиксирует второй аргумент равным 8. Таким образом, предикат возвращает true, если значение v больше 8.

Поскольку вектор v содержит несколько смежных пар одинаковых объектов, тест adjacent find() спроектирован так, чтобы найти все дубликаты. Поиск начинается от начала интервала и продолжается в цикле до тех пор, пока итератор it не достигнет конца исходного интервала (когда других совпадений заведомо не остается). Цикл выводит информацию о каждом найденном совпадении, после чего снова вызывает adjacent find() с первым аргументом it + 1. Такая реализация позволяет найти две пары в последовательности из трех элементов.

При взгляде на цикл while кажется, что его можно записать изящнее:

whiledt != V.endO) { cout adjacent find: *it++

, *it++ endl; it = adjacent findOt, v.endO):

Именно это мы попытались сделать в первом варианте программы. Однако нам не удалось получить ожидаемый результат ни на одном компиляторе! Дело в отсутствии гарантированного порядка выполнения инкрементов в этом выражении.

В следующем тесте алгоритм adjacent find() используется в сочетании с предикатом PlusOne. Тест обнаруживает все пары, в которых следующий элемент на 1 больще предыдущего. Как и в описанном тесте, цикл while находит все вхождения.

Алгоритму find first of() передается второй интервал с объектами, которые ищутся в первом интервале. В нащем примере это массив Ь. Поскольку первый и второй интервалы find first of() определяются разными аргументами шаблонов, они могут относиться к контейнерам разного типа, как в данном случае. Также в программе тестируется вторая форма find first of() с использованием предиката PlusOne.

Алгоритм search О находит в первом интервале точную копию содержимого второго интервала с тем же порядком следования элементов. Вторая форма search() использует предикат, который обычно определяет некоторую форму проверки эквивалентности, но существуют и другие интересные возможности - в нашей программе предикат PlusOne позволяет найти интервал {4,5,6}.

Тест find end() находит последнее вхождение всей последовательности {11,11,11}. Чтобы доказать, что найдено действительно последнее вхождение, мы выводим оставшиеся элементы v, начиная с it.

Первый тест search n() ищет первые 3 экземпляра значения 7, находит и выводит их. Во второй версии search n() предикат обычно проверяет эквивалентность двух элементов. Однако мы пошли нестандартным путем и воспользовались объектом функции, который умножает значение в интервале на 15 и проверяет, окажется ли результат больше 100. Другими словами, тест с search n() означает: Найти 6 последовательных значений, которые при умножении на 15 дают число больше 100 . На практике такие решения встречаются не так часто, но возможно, оно все же пригодится вам, когда вы в очередной раз столкнетесь с нетипичной задачей поиска.

Алгоритмы min element() и max element() просты и понятны, хотя на первый взгляд разыменование функции символом * выглядит странно. На самом деле мы разыменовываем возвращаемый итератор, чтобы получить значение для вывода.

Тестирование алгоритмов замены начинается с алгоритма гер1асе сору(), не изменяющего исходный вектор. Мы заменяем все вхождения 8 значением 47. Обратите внимание на использование функции back inserter() с пустым вектором v2.

Для демонстрации алгоритма replacejf() мы создаем на базе стандартного шаблона greater equal с адаптером bind2nd() объект функции для замены всех элементов, больших либо равных 7, значением -1.

Сравнение интервалов

На первый взгляд может показаться, что по функциональности алгоритмы группы сравнения интервалов напоминают алгоритмом search(). Однако search() сообщает, где второй интервал находится внутри первого, а equal() и lexicographicaLcompare() - в каком отношении между собой находятся два интервала. Алгоритм niismatch() указывает, где начинается расхождение в содержимом двух интервалов, но для этого интервалы должны иметь одинаковую длину.

bool equal(Inputlterator firstl. Inputlterator lastl.

Inputlterator first2); bool equal(Inputlterator firstl. Inputlterator lastl.

Inputlterator first2. BinaryPredicate binary pred):

В обоих алгоритмах первый интервал задается в канонической форме [firstl,lastl). Второй интервал начинается с first2, но парного конечного итератора last2 не существует, потому что его длина определяется длиной первого интервала. Функция equal() возвращает true, если оба интервала точно совпадают (содержат одни и те же элементы, следующие в одинаковом порядке). В первой форме элементы сравниваются оператором ==, а во второй эквивалентность определяется бинарным предикатом binary pred.

bool lexicographical compare(InputIteratorl firstl.

Inputlteratorl lastl. InputIterator2 first2.

InputIterator2 last2): bool lexicographical compare(InputIteratorl firstl.

Inputlteratorl lastl. InputIterator2 first2.

InputIterator2 last2, BinaryPredicate binary pred):

Алгоритм проверяет, меньше ли первый интервал, чем второй по лексикографическому критерию (если интервал 1 меньше интервала 2, алгоритм возвращает true, а если нет - возвращается false). Лексикографическое сравнение производится по тому же принципу, по которому мы ищем слова в словаре, то есть последовательным сравнением элементов. Если первые элементы различаются, то их отношение определяет результат сравнения. Но если элементы равны, алгоритм переходит к следующей паре элементов и рассматривает их. Это продолжается до тех пор, пока не будет найдено расхождение. На этой стадии алгоритм сравнивает различающиеся элементы, и если элемент из первого интервала меньше элемента из второго, алгоритм lexicographical compare() возвращает true; в противном случае - false.

Если интервалы имеют разную длину, отсутствующий элемент одного интервала считается предшествующим существующему элементу второго интервала, то есть аЬс предшествует abcd . Если алгоритм достигает конца одного из интервалов, не обнаружив расхождений, более короткий интервал считается меньшим. Если первый интервал имеет меньшую длину, то результат равен true; в противном случае он равен false.

В первой форме алгоритма элементы сравниваются оператором <, а во второй эквивалентность определяется бинарным предикатом binary pred.