На этом шаге мы рассмотрим алгоритмы, осуществляющие поиск двух смежных элементов с равными значениями.
Для организации такого поиска имеются следующие алгоритмы:
InputIterator adjacent_find (InputIterator beg, InputIterator end) InputIterator adjacent_find (InputIterator beg, InputIterator end, BinaryPredicate op)
Первая форма возвращает позицию первого элемента со значением следующего элемента.
Вторая форма возвращает позицию первого элемента в интервале [beg,end), для которого предикат op(elem,nextElem) возвращает true.
Если подходящий элемент не найден, обе формы возвращают end.
Предикат ор не должен изменять свое состояние во время вызова и передаваемые аргументы.
Сложность линейная (не более numberOfElements сравнений или вызовов ор соответственно).
Следующая программа демонстрирует обе формы алгоритма adjacent_find():
//--------------------------------------------------------------------------- #include <vcl.h> #include <iterator> #include "algostuff.hpp" #include <conio.h> //необходимо для getch() #pragma hdrstop //--------------------------------------------------------------------------- #pragma argsused using namespace std; std::string ToRus(const std::string &in) { char *buff = new char [in.length()+1]; CharToOem(in.c_str(),buff); std::string out(buff); delete [] buff; return out; } // Функция проверяет, что значение следующего объекта вдвое больше // значения предыдущего bool doubled (int elem1, int elem2) { return elem1 * 2 == elem2; } int main() { vector<int> coll; coll.push_back(1); coll.push_back(3); coll.push_back(2); coll.push_back(4); coll.push_back(5); coll.push_back(5); coll.push_back(0); PRINT_ELEMENTS(coll,"Вектор:\n"); // Поиск первых двух элементов с одинаковыми значениями vector<int>::iterator pos; pos = adjacent_find (coll.begin(), coll.end()); if (pos != coll.end()) { cout << ToRus("Первые два элемента с одинаковыми значениями находятся на\n") << distance(coll.begin(),pos) + 1 << ToRus(" позиции.") << endl; } // Поиск первых двух элементов, для которых значение второго // вдвое превышает значение первого pos = adjacent_find (coll.begin(), coll.end(), // Интервал doubled); // Критерий if (pos != coll.end()) { cout << ToRus("Первые два элемента, для которых значение второго\n") << ToRus("вдвое превышает значение первого, находятся на\n") << distance(coll.begin(),pos) + 1 << ToRus(" позиции.") << endl; } getch(); return 0; } //---------------------------------------------------------------------------
Первый вызов adjacent_find() ищет элементы с одинаковыми значениями. Вторая форма при помощи функции doubled() проверяет, что значение второго элемента вдвое больше значения первого. Программа выводит следующий результат:
Рис.1. Результат работы приложения
Со следующего шага мы начнем рассматривать алгоритмы сравнения интервалов.
