Перемещение элементов в начало

Bidirectionallterator

partition (Bidirectionallterator йед, Bidirectionallterator encf. UnaryPredicate op)

Bidirectionallterator

stable partition (Bidirectionallterator beg. Bidirectionallterator end. UnaryPredicate op)

О Оба алгоритма перемещают в начало интервала [beg.end) все элементы, для которых унарный предикат ор{е1ет) возвращает true.

О Оба алгоритма возвращают первую позицию, для которой opQ возвращает false.

О Отличие partitionO от stable partitionO заключается в том, что stablepartitionO сохраняет относителытый порядок следования элементов (как соответствующих, так и не соответствующих критерию),

О Алгоритм может использоваться для разбиения элементов на две группы в соответствии с критерием сортировки. Аналогичной возможностью обладает алгоритм nth eementO. Отличия этих алгоритмов от nth element() описаны на с. 330.

О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303.

О Сложность:

□ PartitionO - линейная (numberOfElements вызовов ор() и не более питЬег-OfElements/2 обменов);

□ StablejDartitionO - линейная при наличии дополнительной памяти (numberOfElements вызовов орО и обменов), nxlog(n) в противном случае (питЬег-OfElementsy.log(numberOfElements) вызовов ор{)).

Следующая программа демонстрирует использование алгоритмов partitionO и stable partitionO, а также различия между ними:

algo/partl.срр finclude "algostuff.hpp" using namespace std;

int mainO {

vector<int> colli; vector<int> C0112:

INSERT ELEMENTS(colll.l.9); INSERT ELEMENTS(coll2.1.9): PRINTJLEMENTS (col 11. "col 11: ): PRINT ELEMENTS(col 12."col 12: "): cout « endl:

Перемещение всех нечетных элементов в начапо vector<int>::iterator posl. pos2;

posl = part1tion(colll.beginO. colli.end(). Интервал

notl(bind2nd(modulus<int>(),2))); Критерий

pos2 = stable partition(coll2.beginO . coll2.endO. Интервал

notl(bind2nd(tiiodulus<int>(),2))): Критерий

Вывод коллекций и первого нечетного элемента

PRINT ELEMENTSCcol11."col 11; "):

cout « "first odd element: " « *posl « endl;

PRINT ELEMENTS(coll2."coll2: "):

cout « "first odd element: " « *pos2 « endl;

Результат выполнения программы выглядит так:

colli: 12 3 4 5 6 7 8 9 C0112: 12 3 4 5 6 7 8 9

colli: 8 2 6 4 5 3 7 1 9 first odd element: 5 C0112: 246813679 first odd element: 1

Как видно из приведенного примера, stable partition(), в отличие от partition(), сохраняет относительный порядок следования четных и нечетных элементов.

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

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

Ассопиативные контейнеры сортируют свои элементы автоматически. Однако обычно эффективнее однажды выполнить сортировку элементов, а ие хранить их в упорядоченном виде постоянно (см. с. 232).

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

void

sort (RandomAccessIterator beg. RandomAccessIterator end) void

sort (RandomAccessIterator beg. RandomAccessIterator end. BinaryPredicate op)

void

stable sort (RandomAccessIterator beg, RandomAccessIterator end) void

stable sort (RandomAccessIterator beg, RandomAccessIterator end. BinaryPredicate op)

о Первые формы sort() и stable sort() сортируют все элементы интервала [beg,end) оператором <.

О Вторые формы sort() и stable sort() сортируют все элементы интервала, используя в качестве критерия сортировки бинарный предикат op(elemi,elem2).

О Предикат ор не должен изменять свое состояние во время вызова. За подробностями обращайтесь на с. 303.

О Отличие sort() от stable sort() заключается в том, что stable sort() сохраняет относительный порядок следования равных элементов.

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

О Алгоритм sort() гарантирует хорошее среднее быстродействие (nxlog(n)). Тем не менее если в вашей ситуации особенно важно избежать худших случаев, используйте алгоритм partial sort() или stable sort(). Сравнительный анализ алгоритмов сортировки приводится на с. 328.

О Сложность;

□ Sort() - в среднем nxlog(n) (примерно numberOfElementsx\og{numberOf-Elements) сравнений);

□ Stable sort() - nxlog(n) при наличии дополнительной памяти (питЬег-OfElementsx\og(nu7nberOfElements)), «xlog(n)xlog(n) в противном случае (numberOfElements:<\Qg(numberOfElementsy сравнений).

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

algo/sortl.cpp finclude "algostuff,hpp" using namespace std;

int mainO (

deque<int> coll;

INSERT ELEMENTS(coll.l.9); INSERT ELEMENTS(coll.l.9);

PRINT ELEMENTS(coll."on entry; "):

Сортировка эленентов

sort (coll.beginO. coll.endO):

PRINTJLEMENTS(C011 . "sorted: ");

Сортировка в обратной порядке

sort (coll.beginO, coll.endO. Интервал

greater<1nt>()): Критерий сортировки

PRINT ELEMENTS(C0ll."sorted >; ");