tmp = static cast<double>(rand())

/ static cast<double>CRAND MAX): return static cast<ptrdiff t>(ttiip * max;

int mainO

vector<1nt> coH;

IN5ERT ELEMENT5(coll .1.9): PRINT ELEM£NTS(coll. coll: ):

Случайная перестановка элементов random shuffle (col 1 .beginO. coll.endO):

PRINTJLEMENTSCcol 1. shuffled: ):

Повторная сортировка

sort (coll .beginO. coll.endO):

PRINT ELEMENTS(col1. sorted: ):

/* Случайная перестановка элементов

* с пользовательским генератором случайных чисеп

* - для передачи 1-значения необходимо использовать временный обьект */

MyRandotn rd;

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

rd); Генератор случайных чисел

PRINT ELEMENTS(coll. shuffled: ):

При втором вызове алгоритма random shuffle() используется пользовательский генератор случайных чисел rd(). Он представляет собой объект вспомогательного класса MyRandom, который задействует алгоритм построения случайных чисел, часто обеспечивающий лучший результат по сравнению с прямым вызовом randO

Возможный (но не гарантированный) результат выполнения программы выглядит так:

coll: 123456789 shuffled: 2 6 9 5 4 3 17 8 sorted: 12 3 4 5 6 7 8 9 shuffled; 2 6 9 3 18 7 4 5

Алгоритм построения случайных чисел, используемый в MyRandom, представлен и описан в книге Бьярна Страуструпа ТЬе С-и- Programming Language*, 3rd Edition.

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

Bidirectionallterator

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

Bidirectionallterator

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

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

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

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

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

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

О Сложность:

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

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

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

algo/partl.срр #include algostuff.hpp using namespace std;

int mainO {

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

INSERT ELEMENTS(colll.l.9); INSERT FLEMENTS(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 part1tion(coll2.beginO. coll2.endC). Интервал

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 С0112: 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)