ментов (неупорядоченное). Алгоритм nth element() разделяет элементы на два подмножества в соответствии с критерием сортировки. Впрочем, задача также может быть решена алгоритмами partition() и stable partition(). Различия между этими алгоритмами заключаются в следующем.

О Алгоритму nth element() передается требуемое количество элементов в первой части (а следовательно, и во второй). Пример:

Перемещение четырех наименьших элементов в начало nthelement (coll.beginO. Начало интервала

coll .beg1nO+3. Позиция, отделяющая первую часть от второй

coll.endO): Конец интервала

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

О Алгоритму partitionO передается конкретный критерий сортировки, определяющий различия между первой и второй частями:

Перемещение всех элементов, меньших 7. в начало vector<int>::iterator pos:

pos = partition (colli.beginO. colli.endO. Интервал

b1nd2nd(less<lnt>().7)): Критерий

Ha этот раз после вызова невозможно сказать, сколько элементов входит в первую и вторую части. Возвращаемый итератор pos указывает на первый элемент второй части, которая содержит все элементы, не соответствующие кррггерию.

О Алгоритм stable partition() в целом аналогичен partition(), но он дополнительно гарантирует сохранение порядка следования элементов в обеих частях по отношению к другим элементам, входящим в ту же часть.

Любому алгоритму сортировки в необязательном аргументе всегда можно передавать критерий сортировки. По умолчанию критерием сортировки является объект функции lesso, а элементы сортируются по возрастанию значений.

Как и в случае с модифицирующими алгоритмами, приемником алгоритмов сортировки не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются константными.

Кроме того, алгоритмы сортировки не могут вызываться для списков, поскольку списки не поддерживают итераторы произвольного доступа. Впрочем, для сортировки элементов в списках определена функция sort() (см. с. 252).

Алгоритмы упорядоченных интервалов

Алгоритмы упорядоченных интервалов требуют, чтобы интервалы, с которыми они работают, были изначально упорядочены по соответствующему критерию. В табл. 9.7 перечислены все алгоритмы стандартной библиотеки С++, предназначенные для упорядоченных интервалов. Достоинством этих алгоритмов является невысокая сложность.

Таблица 9.7. Алгоритмы упорядоченных интервалов

Название

Описание

Страница

b[nary search() includesO

lower bound()

upper bound() .

equaLrangeO

mergeO set union()

setJntersectionO

set difference()

set sym m etric d iff erenceO

inplace mergeO

Проверяет, содержит ли интервал заданный элемент 400

Проверяет, что каждый элемент интервала также 401 является элементом другого интервала

Находит первый элемент со значением, большим 402 либо равным заданному

Находит первый элемент со значением, большим 402 заданного

Возвращает количество злементов в интервале, 404

равных заданному значению

Выполняет слияние элементов двух интервалов 406

Вычисляет упорядоченное объединение двух 407

интервалов

Вычисляет упорядоченное пересечение двух 408

интервалов

Вычисляет упорядоченный интервал, который 409

содержит все элементы интервала, не входящие в другой интервал

Вычисляет упорядоченный интервал, содержащий 410 все элементы, входящие только в один из двух интервалов

Выполняет слияние двух последовательных 413

упорядоченных интервалов

Первые пять алгоритмов упорядоченных интервалов, перечисленные в таблице, являются немодифицирующими, поскольку они ограничиваются поиском по заданному условию. Другие алгоритмы комбинируют два упорядоченных входных интервала и записывают результат в приемный интервал. Как правило, результат выполнения алгоритмов тоже упорядочен.

Численные алгоритмы

Численные алгоритмы выполняют разнообразную обработку числовых элементов. В табл. 9.8 приведен список численных алгоритмов стандартной библиотеки С++. Имена алгоритмов дают некоторое представление о том, что они делают, однако эти алгоритмы отличаются большей гибкостью и мощью, чем может показаться на первый взгляд. Например, алгоритм accumulate() по умолчанию вычисляет сумму элементов. Если элементами являются строки, то вычисляется их конкатенация. А если переключиться с оператора + на оператор *, алгоритм вычислит произведение элементов.

Алгоритмы accumulateO и inner prcduct() вычисляют и возвращают сводное значение без модификации интервалов. Другие алгоритмы записывают свои результаты в приемный интервал, количество элементов в котором соответствует количеству элементов в исходном интервале.

Вспомогательные функции

В оставшейся части этой главы приводятся подробные описания всех алгоритмов. Для каждого алгоритма дается минимум один пример. Следующие вспомогательные функции упрощают код примеров, чтобы читатель мог сосредоточиться на наиболее содержательных аспектах:

algo/algostuff,hpp #Tfndef ALGOSTUFF HPP fdefine ALGOSTUFF HPP

finclude <iostream> finclude <vector> fmclude <deque> #1nclude <llst> #1nclude <set> include <map> #1nclude <string> #1nclude <algorithni> finclude <functional> #1nclude <numer1c>

/* PRINTJLEMENTSO

* - вывод необязательной строки С. за которой выводятся

* - все элементы коллекции coll. разделенные пробелами. */

template <cla5s Т>

inline void PRINTJLEMENTS (const T& coll, const char* optC5tr="") {

typename T::const 1terator pos: std::cout « optcstr:

for (pos-col1.beginO: po5!=coll,end(): ++pos) { std::cout « *pos « ;

std::cout « std::endl;