его правильнее было бы включить в список алгоритмов упорядоченных интервалов (см. с. 330). Но на практике алгоритм merge() также успешно справляется со слиянием неупорядоченных интервалов. Конечно, результат тоже оказывается неупорядоченным. И все же для надежности стоит вызывать merge() только для упорядоченных интервалов.

Учтите, что элементы ассоциативных алгоритмов объявляются константными, чтобы алгоритм не мог нарушить порядок следования элементов вследствие модификации их значений. Это означает, что ассоциативные контейнеры ие могут выступать в качестве приемника для модифицирующих алгоритмов.

Кроме модифицирующих алгоритмов в стандартной библиотеке C+-i- выделена отдельная группа модифицирующих алгоритмов для упорядоченных интервалов. Подробности приведены иа с. 330.

Алгоритмы удаления

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

Таблица 9.4. Алгоритмы удаления

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

Перестановочные алгоритмы

Перестановочными алгоритмами называются алгоритмы, изменяющие порядок следования элементов (но не их значения) посредством присваивания и пере-

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

Таблица 9.5. Перестановочные алгоритмы

Алгоритмы сортировки

Алгоритмы сортировки являются частным случаем перестановочных алгоритмов, поскольку они тоже изменяют порядок следования элементов. Тем не менее сортировка является более сложной операцией и обычно занимает больше времени, чем простые перестановки. На практике эти алгоритмы обычно имеют сложность выше линейной и требуют поддержки итераторов произвольного доступа (для приемника). Алгоритмы сортировки перечислены в табл. 9.6.

Сложность операций рассматривается на с, 37.

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

О sort(). Исторически этот алгоритм основан иа механизме быстрой сортировки, гараитируюгдем хорошую среднестатистическую сложность (nxlog(n)), но очень плохую (квадратичную) сложность в худшем случае:

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

* - средняя сложность n*log(n)

* - квадратичная сложность п*л в худшем случае */

sort (coll .beginO. coll.endO):

Если в вашей ситуации очень важно избежать худших случаев, воспользуйтесь другим алгоритмом, например partial sort() или stable sort().

О partiaLsort(). Исторически этот алгоритм основан на механизме сортировки в куче (heapsort), гарантирующем сложность nxlog(n) в .любом случае. Тем не менее обычно сортировка в куче выполняется в 2-5 раз медленнее быстрой сортировки. Итак, с учетом реализаций sort() и partial SGrt(), алгоритм partiaLsort() лучше по сложности, по по скорости работы sort() обычно превосходит его. Преимущество алгоритма partiaLsort() заключается в том, что сложность nxlog(n) гарантирована и никогда не ухудшается до квадратичной сложности.

Алгоритм partial sort() также обладает особым свойством: он прекращает сортировку, когда требуется отсортировать только п первых элементов. Чтобы отсортировать все элементы, передайте конец последовательности во втором и в последнем аргументах:

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

* - всегда сложность n*log(n)