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

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

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

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

  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. Результат работы приложения

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

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