Глава 14. Алгоритмы 361

tempiate<class For>

For min_element(For first, For last); tempiate<class For. class Compare>

For min_element(For first. For last. Compare comp); tempiate<class For>

For max_element(For first. For last); tempiate<class For. class Compare>

For max_element(For first. For last. Compare comp);

merge

Алгоритм merge выполняет слияние отсортированных последовательностей.

tempiate<class Inl. class In2. class 'Out>

Out mergednl firstl. Inl lastl. In2 first2. In2 last2. Out result); tempiate<class Inl, class In2. class Out. class Compare> Out mergednl firstl. Inl lastl. In2 first2, In2 last2, Out result. Compare comp);

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

Пример:

#include <iostream> #include <algorithm> using namespace std; int main(){

const int m = 5;

doublea[m] = {3. 4, 8, 17, 20}.

b[m] = {5. 6. 8. 10, 35}. c[m * 2]; int i:

merge(a. a + m. b. b + m, c); for (i = 0; i < m * 2; i++)

cout « c[i] « " "; //345688 10 17 20 35 cout « endl; return 0; }

next_permutation, prevpermutation

Элементы любой последовательности можно расположить разными способами. Для последовательности длины п таких перестановок существует п! (1*2*...*п). Алгоритм next_permutation производит очередную перестановку в лексикографическом порядке, а алгоритм prev_permutation — предыдущую. Алгоритмы возвращают булевское значение true, если следующая перестановка существует, и false в противном случае.

362

Часть III. Стандартная библиотека

tempiate<class Bi>

bool next_permutation(Bi first. Bi last); tempiate<class Bi. class Compare>

bool next_permutation(Bi first. Bi last. Compare comp); tempiate<class Bi>

bool prev_permutation(Bi first. Bi last); tempiate<class Bi. class Compare>

bool prev_permutation(Bi first. Bi last. Compare comp);

Пример:

#include <iostream> #include <algorithm> using namespace std; int main(){

const int m = 3;

int a[m]={l, 4. 2}. b[m];

int i;

copy(a. a + m. b);

cout « " next_permutation(a. a + m);" « endl;

while (next_permutation(a. a + m)){

for (i = 0; i < m; i++) cout « a[i] « " cout « endl;} cout « " prev_permutation(b. b + m):^M « endl; while (prev_permutation(b. b + m)){

for (i = 0; i < m; i++) cout « b[i] « " cout « endl;} return 0;

} Результат работы программы:

next_permutation(a. a + m):

2 1 4

2 4 1

4 1 2

4 2 1

prev_permutation(b. b + m):

12 4

nth_element

Алгоритм выполняет частичную сортировку массива. После выполнения алгоритма значение элемента, заданного итератором nth, будет таким же, как после полной сортировки, то есть все элементы левее этой позиции будут меньше него, а все, что правее, — больше.

tempiate<class Ran>

void nth_element(Ran first. Ran nth. Ran last); tempiate<class Ran, class Compare>