Таблица M.S(продолжение)

Алгоритм

Назначение

rotate

rotate copy search

search n

set difference

set lntersectlon

set sy m m et r) c d if fe re nee

set unJon

sort

sort heap stable partitJon

stabie sort

swap

swap ranges transform

unique unique copy

upper bound

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

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

Выполняет поиск последовательности заданного числа одинаковых элементов

Создает последовательность, которая содержит различающиеся участки двух упорядоченных наборов-

Создает последовательность, которая содержит одинаковые участки двух упорядоченных наборов

Создает последовательность, которая содержит симметричные различающиеся участки двух упорядоченных наборов

Создает последовательность, которая содержит объединение (union) двух упорядоченных наборов

Сортирует диапазон

Сортирует пирамиду внутри диапазона

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

Сортирует диапазон. Одинаковые элементы не пе-, реставляются

Меняет местами два значения

Меняет местами элементы в диапазоне

Назначает функцию диапазону элементов и сохраняет результат в новой последовательности

Удаляет повторяющиеся элементы из диапазона

Обнаруживает последнее значение в последовательности, которое не больше некоторого значения

[ Пример

1. Одними из самых простых алгоритмов являются алгоритмы countO и coimt if(). Ниже представлены их основные формы:

tefflplate<class Inlter, class T>

size t count(Inlter начало,

Jnlte vdKxre, const Т йзначенкф) ;

int main ( )

vector<int> v; i . . int i;

for(i=0,- i<20; (

if(i%2) v,push back(l) ; else v.push back(2); .

cout Последовательность: ;

for(i=0; i<v.sizeO; i++) cout v[i] ;

cout endl;

int n;

n = count (v.begin 0 , v.end(), 1) ;

cou n элементов равно l\n ;

f (v.begin () d[), even); cou n четных элементов\п ;

return 0;

t -iraplate<clas8 Inltar, class T>

size t count (Inlter начало,

Inlter окончание, UnPred й* предлмт) ; -

Алгоритм ntO возвращает число элементов в последовательности, начиная ента, обозначенного итератором начало, и заканчивав нтом, обозначенным итератором окончание, значение которхх равно параметру значение. Алгоритм t if() возвращает число элементов в последовательности, начиная с элемента начало и заканчивая элементом окончание, для которых унарный предикат возвращает истину.

В следующей программе демонстрируются алгоритмы count() и couiit if().

Демонстрация алгоритмов count и count if

ftinclude <iostream>

ttinclude <vector>

#include <algoritm> *

using namespace std;

/* это унарные икат, который определяет, является ли значение четным

bool even (int х) <

{ . .

return ! (х%2);

458 Самоучитель ~ С++

После выполнения программы на экране появится следующее:

Последовательность: 21212121212121212121 10 элементов равно 1

10 четных элементов . ........ .ty:.

Программа начинается с создание шентного вектора, содержащего чередующиеся значения 1и 2. Для подсчета единиц используется алгоритм count О, а для подсчета четных элементов - алгоритм couiit if() Отметьте, как программируется унарный предикат even(). Все унарные предикаты получают в качестве параметра объект, тип которого тот же, что и тип объектов контейнера, для работы с которым предназначен предикат. В зависимости от значения этого объекта унарный предикат должен возвращать истину либо ложь.

2. Иногда полезно генерировать новую последовательность, состоящую только из определенных фрагментов исходной последовательности. Одним из предназначенных для этого алгоритмов является алгоритм remove copy(), основная форма которого представлена ниже:

templatiKclaas Inlter, clas Wter, class T> /

Outiter removeGopy (inlter нavaлo,

Inlter ание, Outlte я-аз?, const Т fiaHaveawe) ;

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

В следующем примере показана работа алгоритма те сору(). Сначала в программе создается чередующаяся последовательность значений 1и 2. Затем из последовательности удаляются все единицы.

Демонстрация алгоритма

ttinclude <iostream>

tfinclude <vector> .....

ttinclude <algorithin> using namespace std;

int main ( )

vector<int>v, v2(20) ; ... . , .

int i;

for(i=0; i<20; i++) f ,. -

if(i%2) v.push back(l) ; els back(2) ;