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

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

  pair<ForwardIterator,ForwardIterator>
  equal_range (ForwardIterator beg, ForwardIterator end, 
               const T& value)

  pair<ForwardIterator,ForwardIterator>
  equal_range (ForwardIterator beg, ForwardIterator end, 
               const T& value, BinaryPredicate op)

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

Алгоритм эквивалентен вызову

  make_pair(lower_bound(...),upper_bound(...))

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

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

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

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

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

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

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

  // Вывод первой и последней позиций, в которых может быть
  // вставлен элемент со значением 5
  pair<list<int>::iterator,list<int>::iterator> range;

  range = equal_range (coll.begin(), coll.end(),
                       5);

  cout << ToRus("Число 5 может быть вставлено с ")
       << distance(coll.begin(),range.first) + 1
       << ToRus(" по ")
       << distance(coll.begin(),range.second) + 1
       << ToRus("\nпозицию без нарушения упорядоченности.") << endl;


  getch();
  return 0;
}

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

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

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

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

Со следующего шага мы будум рассматривать слияние интервалов.

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