Поиск элементов. Проверка присутствия элемента

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

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

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

  bool
  binary_search (ForwardIterator beg, ForwardIterator end, 
                 const T& value)

  bool
  binary_search (ForwardIterator beg, ForwardIterator end, 
                 const T& value, BinaryPredicate op)

   
Обе формы проверяют, содержит ли упорядоченный интервал [beg,end) элемент со значением value.

   
В необязательном параметре ор передается бинарный предикат, определяющий критерий сортировки:
op(elem1,elem2).

   
Чтобы определить позицию искомого элемента, воспользуйтесь функциями lower_bound(), upper_bound() и
equal_range().

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

   
Сложность логарифмическая для итераторов произвольного доступа, линейная в остальных случаях (не более
log(numberOfElements)+2 сравнений, но для итераторов, не являющихся итераторами произвольного доступа,
выполняется линейное количество операций перебора, вследствие чего сложность оказывается линейной).

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

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

#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);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  // Проверка существования элемента со значением 5
  if (binary_search(coll.begin(), coll.end(), 5)) {
      cout << ToRus("Число 5 присутствует") << endl;
  }
  else {
      cout << ToRus("Число 5 отсутствует") << endl;
  }

  // Проверка существования элемента со значением 42
  if (binary_search(coll.begin(), coll.end(), 42)) {
      cout << ToRus("Число 42 присутствует") << endl;
  }
    else {
        cout << ToRus("Число 42 отсутствует") << endl;
    }


  getch();
  return 0;
}

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

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

   
Результат выполнения программы выглядит так:


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

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



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

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