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

Для организации такого поиска бибилиотека 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;
}

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

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

Второй вызов использует обратные итераторы для поиска последнего элемента со значением, равным значению одного из элементов searchcoll. При выводе позиции элемента вызывается функция base(), которая преобразует обратный итератор в обычный (чтобы позиция отсчитывалась от начала коллекции). Обычно к результату distance() прибавляется 1, так как для первого элемента расстояние равно 0, однако base() смещает логическую позицию, на которую ссылается итератор, что приводит к желаемому эффекту (функция base() описана на 222 шаге).

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

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

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

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