Поиск элементов. Поиск первого совпадающего элемента

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

   
Приведем две формы алгоритмов, выполняющх такой поиск:

  InputIterator
  find (InputIterator beg, InputIterator end, const T& value)
  InputIterator
  find_if (InputIterator beg, InputIterator end, UnaryPredicate op)

   
Первая форма возвращает позицию первого элемента со значением value в интервале [beg,end). Вторая форма
возвращает позицию первого элемента в интервале [beg,end), для которого предикат op(elem) возвращает true.
Если подходящий элемент не найден, обе формы возвращают end.

   
Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на 243 шаг.
Предикат ор не должен изменять передаваемые аргументы.

   
В упорядоченных интервалах рекомендуется использовать алгоритмы lower_bound(), upper_bound(), equal_range() и
binary_search().

   
В классах ассоциативных контейнеров (множества, мультимножества, отображения и мультиотображения) определена аналогичная
функция find(), которая имеет логарифмическую, а не линейную сложность (смотри 198 шаг).

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

   
В следующем примере алгоритм find() используется для поиска подинтервала, который начинается и заканчивается элементами со значением 4:

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

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

  INSERT_ELEMENTS(coll,1,9);
  INSERT_ELEMENTS(coll,1,9);

  PRINT_ELEMENTS(coll,"Исходный список:\n");

  // Поиск первого элемента со значением 4
  list<int>::iterator pos1;
  pos1 = find (coll.begin(), coll.end(),    // Интервал
               4);                          // Значение

  // Поиск второго элемента со значением 4
  //  - поиск начинается после позиции первого найденного элемента
  //  - со значением 4 (если он есть)
  list<int>::iterator pos2;
  if (pos1 != coll.end()) {
      pos2 = find (++pos1, coll.end(),      // Интервал
                   4);                      // Значение
  }

  // Вывод всех элементов от первого до второго элемента
  // со значением 4, включая оба элемента
  // - Итератор pos1 необходимо вернуть к позиции первого элемента
  //   со значением 4 (если он есть)
  // - конец интервала определяется позицией за вторым элементом
  //   со значением 4 (если он есть)
  cout << ToRus("Вывод всех элементов от первого до второго элемента\n")
       << ToRus("со значением 4, включая оба элемента:\n");
  if (pos1!=coll.end() && pos2!=coll.end()) {
      copy (--pos1, ++pos2,
            ostream_iterator<int>(cout," "));
      cout << endl;
  }


  getch();
  return 0;
}

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

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

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



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

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