ным . Алгоритм nt element() гарантирует лишь то, что выбранная позмгмя является точкой разбиения, то есть все элементы в интервале [first,nth) удовлетворяют бинарному предикату (как обычно, по умолчанию используется оператор <), а для всех элементов в интервале [nth,last) это условие не выполняется. Тем не менее, ни в одном из подынтервалов элементы не располагаются в определенном порядке, тогда как алгоритм partiaLsort() сортирует первый интервал.

Если такого (очень слабого упорядочения) достаточно, например, при вычислении медиан, процентилей и т. д., этот алгоритм удобнее, так как он работает быстрее алгоритма partiaLsort().

Поиск элементов в отсортированных интервалах

Отдельная группа алгоритмов предназначена для поиска элементов в отсортированных интервалах. В следующих описаниях всегда присутствуют две формы, в первой форме при сортировке используется внутренний оператор <, а во второй - объект функции сравнения. При поиске должен применяться тот же способ сравнения, что и при сортировке; в противном случае результат работы алгоритма не определен. Попытка применения этих алгоритмов к несортированным интервалам также приводит к неопределенным результатам.

bool binary search(ForwarclIterator first, Forwardlterator last, const T& value);

bool binary search(Forwardlterator first. Forwardlterator last, const T& value. StrictWeakOrdering binary pred):

Алгоритм сообщает, присутствует ли заданное значение в сортированном интервале [firstlast).

Forwardlterator lower bound(ForwardIterator first.

Forwardlterator last, const T& value); Forwardlterator lower bound(ForwardIterator first.

Forwardlterator last, const T& value. StrictWeakOrdering binary pred);

Алгоритм возвращает итератор, установленный в позицию первого вхождения value в отсортированный интервал [firstlast). Если значение value отсутствует в интервале, возвращается last

Forwardlterator upper bound(Forwardlterator first.

Forwardlterator last, const T& value); Forwardlterator upper bound(ForwardIterator first,

Forwardlterator last, const T& value. StrictWeakOrdering binary pred);

Алгоритм возвращает итератор, установленный в позицию за последним вхождением value в отсортированный интервал [firstlast). Если значение value отсутствует в интервале, возвращается last.

pair<ForwardIterator. ForwardIterator>

equal range(Forwardlterator first. Forwardlterator last,

const T& value); pai r<ForwardIterator, ForwardIterator> equal range(ForwardIterator first. Forwardlterator last,

const T& value, StrictWeakOrdering binary pred):

Алгоритм фактически объединяет lower bound() с upper bound() и возвращает объект pair с итераторами для позиций первого вхождения и на одну позицию за последним вхождением value в отсортированный интервал [firstlast). Если

Алгоритм может определить тип переданного итератора по его тегу (см. следующую главу).

значение value отсутствует в интервале, оба итератора указывают на ту позицию, в которой оно должно было бы находиться.

Возможно, вас удивит, что алгоритмы бинарного поиска получают прямой итератор вместо итератора произвольного доступа (обычно все объяснения бинарного поиска основаны на индексации). Помните, что итератор произвольного доступа является частным случаем прямого итератора и всегда может использоваться вместо него. Если итератор, переданный одному из этих алгоритмов, действительно поддерживает прямой доступ, имеет место эффективный поиск с логарифмической сложностью, а если нет, - линейный поиск*.

Следующая программа преобразует каждое слово входных данных в объект NString и включает его в vector<NString>. Затем полученный вектор используется для демонстрации различных алгоритмов сортировки и поиска.

: C06:SorteclSearchTest.cpp

Тестирование поиска в отсортированных интервалах

NString

linclude <algorithm> linclude <cassert> linclude <ctime> linclude <cstdlib> linclude <cstddef> linclude <fstream> linclude <iostream> linclude <iterator> linclude <vector> linclude NString.h linclude PrintSequence.h linclude ../require.h using namespace std:

int main(int argc. char* argv[]) { typedef vector<NString>::iterator sit: char* fname - test.txt : if(argc > 1) fname = argv[l]: ifstream in(fname): assure(in. fname): srand(time(0)): cout.setf(ios::boolalpha): vector<NString> original: copy(i streamj terator<stri ng>(in).

istream iterator<string>(). back inserter(original)): require(original.SizeO >= 4. Must have four elements ): vector<NString> v(original .beginO. original .endO).

wCoriginal .sizeO / 2): sort(v.beginO. v.endO): print(v.beginO. v.endO. sort ):

V = original:

stable sort(v.beginO. v.endO):

print(V.beginO. v.endO. stable sort ):

V = original:

sit it = V.beginO. it2:

Перемещение итератора в середину интервала for(size t 1 = 0: 1 < v.sizeO / 2; 1t++;

partial sort(v.beginO. it. v.endO): cout middle = *it endl: print(v.beginO, v.endO. partial sort ): v = original:

Перемещение итератора на четверть интервала it = V.beginO:

for(size t i = 0: i < v.sizeO / 4: i++) it++;

Количество копируемых элементов в источнике меньше, чем в приемнике

partial sort copy(v.begiп(). it. w.beginO. w.endO): print(w.begin(), w.endO. partial sort copy ): Недостаточно свободного места в приемнике partial sort copy(v.begin(), v.endO, w.beginO, W.endO):

print(w.beginO. w.endO. w partial sort copy ): Состояние v остается неизменным assert(v == original): nth element(v.begin(), it. v.endO): cout The nth element = *it endl: printCv.beginO. v.endO. nth element ): string f = original [randO % original .sizeO]: cout binary search:

binary search(v.beginO, v.endO. f)

endl: sortCv.beginO. v.endO): it = lower boundCv.beginC). v.endO. f): it2 = upper bound(v.beginO. v.endO. f): printCit. it2. found range ): pair<sit. sit> ip =

equal rangeCv.beginC), v.endO, f): printCip.first, ip.second.

equal range ): } /:-

В этом примере используется упоминавшийся ранее класс NString. Этот класс сохраняет вместе с копией строки номер ее вхождения в контейнер. Вызов stable sort() демонстрирует сохранение исходного порядка следования объектов с одинаковыми строками. Также из результатов теста видно, что происходит при неполной сортировке (у элементов, оставшихся несортированными, нет определенного порядка следования). У неполной сортировки не сушествует устойчивой версии.

Какой бы ни была позиция п при вызове nth element() (а она будет новой при каждом запуске программы из-за генератора случайных чисел URandGen), элементы до позиции п заведомо меньше элемента в этой позиции, а элементы за позицией п больше него; других гарантий относительно порядка следования элементов этот алгоритм не дает. Благодаря генератору URandGen контейнер не содержит дубликатов, но если бы генератор допускал их присутствие, то элементы до п-го были бы меньше элемента в п-й позиции или равны ему.

В приведенном примере также продемонстрированы все три алгоритма бинарного поиска. Как уже отмечалось, алгоритм lower bound() возвращает итератор для первого элемента с заданным ключом, алгоритм upper bound() - итератор для позиции за последним вхождением элемента с заданным ключом, а алгоритм equaLrange() - эти два результата в виде пары.