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

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

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

  ForwardIterator
  find_first_of (ForwardIterator1 beg, ForwardIterator1 end,
                 ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
  ForwardIterator
  find_first_of (ForwardIterator1 beg, ForwardIterator1 end,
                 ForwardIterator2 searchBeg, ForwardIterator2 seerchEnd,
                 BinaryPredicate op)

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

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

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

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

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

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

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

//---------------------------------------------------------------------------

#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;
}


int main()
{
  vector<int> coll;
  list<int> searchcoll;

  INSERT_ELEMENTS(coll,1,11);
  INSERT_ELEMENTS(searchcoll,3,5);

  PRINT_ELEMENTS(coll,      "Последовательность:\n");
  PRINT_ELEMENTS(searchcoll,"Подпоследовательность:\n");

  // Поиск в coll первого вхождения элемента из searchcoll
  vector<int>::iterator pos;
  pos = find_first_of (coll.begin(), coll.end(),     // Интервал
                       searchcoll.begin(),   // Начало искомых значений
                       searchcoll.end());    // Конец искомых значений
  cout << ToRus("Первый элемент из подпоследовательности находится на\n")
       << distance(coll.begin(),pos) + 1
       << ToRus(" позиции в последовательности.") << endl;

  // Поиск в coll последнего вхождения search элемента из searchcoll
  vector<int>::reverse_iterator rpos;
  rpos = find_first_of (coll.rbegin(), coll.rend(),  // Интервал
                        searchcoll.begin(),  // Начало искомых значений
                        searchcoll.end());   // Конец искомых значений
  cout << ToRus("Последний элемент из подпоследовательности находится на\n")
       << distance(coll.begin(),rpos.base())
       << ToRus(" позиции в последовательности.") << endl;


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять 222 шаге).

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


Рис.1. Результат работы приложения

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



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

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