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

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

  bool
  includes (InputIterator1 beg, InputIterator1 end,
            InputIterator2 searchBeg, InputIterator2 searchEnd)

  bool
  includes (InputIterator1 beg, InputIterator1 end,
            InputIterator2 searchBeg, InputIterator2 searchEnd,
            BinaryPredicate op)

Обе формы проверяют, содержит ли упорядоченный интервал [beg,end) все элементы упорядоченного интервала [searchBeg,searchEnd), и возвращают результат в виде логической величины. Иначе говоря, для каждого элемента интервала [searchBeg,searchEnd) должен существовать равный элемент в интервале [beg, end). Если некоторые элементы интервала [searchBeg,searchEnd) равны, то в интервале [beg,end) должно присутствовать такое же количество дубликатов. Таким образом, интервал [searchBeg,searchEnd) должен быть подмножеством интервала [beg,end).

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

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

Сложность линейная (не более 2*(numberOfElements+searchElements)-1 сравнений).

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

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

#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;
  vector<int> search;

  INSERT_ELEMENTS(coll,1,9);
  PRINT_ELEMENTS(coll,"Исходная коллекция:\n");

  search.push_back(3);
  search.push_back(4);
  search.push_back(7);
  PRINT_ELEMENTS(search,"Вектор:\n");

  // Проверка вхождения всех элементов search в coll
  if (includes (coll.begin(), coll.end(),
                search.begin(), search.end())) {
      cout << ToRus("Все элементы вектора входят в коллекцию")
           << endl;
  }
  else {
      cout << ToRus("Не все элементы вектора входят в коллекцию")
           << endl;
  }


  getch();
  return 0;
}

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

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

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

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

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

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