На этом шаге мы рассмотрим алгоритмы, выполняющие обратный поиск.

Ниже представлены алгоритмы, осуществляющие обратный поиск:

  ForwardIterator
  find_end (ForwardIterator beg, ForwardIterator end, 
            ForwardIterator searchBeg, ForwardIterator searchEnd)
  ForwardIterator
  find_end (ForwardIterator beg, ForwardIterator end,
            ForwardIterator searchBeg, ForwardIterator searchEnd,
            BinaryPredicate op)

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

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

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

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

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

Эти алгоритмы не входили в исходную версию STL. К сожалению, им было присвоено имя find_end() вместо search_end(), что было бы гораздо логичнее, поскольку алгоритм поиска первого подинтервала называется search().

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

Следующий пример показывает, как найти последнее вхождение серии элементов внутри другой последовательности (сравните с примером использовании алгоритма search() на 273 шаге):

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

#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()
{
  deque<int> coll;
  list<int> subcoll;

  INSERT_ELEMENTS(coll,1,7);
  INSERT_ELEMENTS(coll,1,7);

  INSERT_ELEMENTS(subcoll,3,6);

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

  // Поиск последнего вхождения subcoll в coll
  deque<int>::iterator pos;
  pos = find_end (coll.begin(), coll.end(),         // Интервал
                  subcoll.begin(), subcoll.end());  // Подинтервал

  // Цикл повторяется до тех пор, пока внутри coll
  // успешно находится очередное вхождение подинтервала
  deque<int>::iterator end(coll.end());
  while (pos != end) { 
      // Вывод позиции первого элемента
      cout << ToRus("Очередная подпоследовательность начинается с элемента ")
           << distance(coll.begin(),pos) + 1
           << "." << endl;

      // Поиск следующего вхождения subcoll
      end = pos;
      pos = find_end (coll.begin(), end,               // Интервал
                      subcoll.begin(), subcoll.end()); // Подинтервал
  }


  getch();
  return 0;
}

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

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

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

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

Что касается второй формы алгоритма, обратитесь к примеру использования второй формы алгоритма search() на 274 шаге - алгоритм find_end() применяется аналогичным образом.

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

Предыдущий шаг Содержание Следующий шаг