* - но обычно работает вдвое медленнее sortO

partial 5ort (coll.beginO. coll.endO. coll.endO):

О stable sort(). Исторически этот алгоритм основан на механизме сортировки со слиянием. Он сортирует все элементы переданного интервала:

/* Сортировка всех элементов

* - сложность n*log(n) или n*log(n)*log(n) */

stablejort (coll.beginO. coll.endO):

Для достижения сложности nxlog(n) необходима дополнительная память, в противном случае алгоритм выполняется со сложностью nxlog(n)xlog(n). Достоинством stable sort() является сохранение порядка следования равных элементов.

Итак, теперь вы приблизительно представляете, какой алгоритм лучше всего подходит для ваших целей, однако это не все. Стандарт гарантирует лишь сложность, но не реализацию алгоритма Это сделано для того, чтобы проектировщики могли использовать новые разработки в области алгоритмов и совершенствовать реализации без нарушения стандартов. Например, алгоритм sort() в реализации STL от SGI использует механизм интроспективной сортировки - новый алгоритм, который по умолчанию работает кзк быстрая сортировка, но в случаях с квадратичной сложностью переключается на сортировку в куче. Впрочем, у того факта, что стандарт не диктует реализацию алгоритма, есть и недостаток - можно реализовать очень плохой алгоритм, который соответствует стандарту. Например, реализация sort() на базе сортировки в куче будет считаться соответствующей стандарту. Конечно, оптимальный алгоритм можно выбрать на основании тестирования, однако нельзя гарантировать, что программный код хронометража будет работать на других платформах.

Помимо перечисленных существуют и другие ажоритмы сортировки элементов. Например, алгортггмы сортировки в куче вызывают функции, непосредственно работающие с кучей (то есть с бинарным деревом, используемым в реализации этих алгоритмов). Алгоритмы сортировки в куче заложены в основу эффективной реализации приоритетньгх очередей (см. с. 438). Вызовы этих алгоритмов, сортирующие все элементы коллекции, выглядят так:

/* сортировка всех элементов * - сложность n+n*log(n) */

niake heap (coll.beginO. coll.endO): sort heap (coll.beginO. coll.endO):

3a дополнительной информацией о кучах и алгоритмах сортировки в куче обращайтесь на с. 396.

Алгоритмы nth element() существуют на тот случай, если вам нужен только Пй упорядоченный элемент или подмножество из п старших или младших зле-

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

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

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

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

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

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

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

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

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

bind2ndCless<int>C).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 efric d iff erenceO

inplace mergeO

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

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

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

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

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

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

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

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

интервалов

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

интервалов

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

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

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

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

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

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

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

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

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