Поиск элементов. Поиск двух смежных элементов с равными значениями

   
На этом шаге мы рассмотрим алгоритмы, осуществляющие поиск двух смежных элементов с равными значениями.

   
Для организации такого поиска имеются следующие алгоритмы:

  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. Результат работы приложения

   
Со следующего шага мы начнем рассматривать алгоритмы сравнения интервалов.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий