CharGen g:

generate(v. v + SZ. g):

generate(v2. v2 + SZ. g):

sort(v. V + SZ);

sort(v2. v2 + SZ):

print(v, V + SZ. v . ):

pr1nt(v2. v2 + SZ. v2 . ):

bool b = includes(v. v + SZ, v + SZ/2, v + SZ):

cout.setf(ios::boolalpha):

cout includes: b endl:

char v3[SZ*2 + 1], *end:

end = set union(v, v + SZ. v2. v2 + SZ. v3):

print(v3. end. set union , ):

end = setJntersGCtion(v. v + SZ.

v2. v2 + SZ. v3): print(v3, end. set intersection . ): end = set difference(v. v + SZ. v2. v2 + SZ. v3): pnnt(v3. end, set difference . ): end = set symmetric difference(v. v + SZ.

v2. v2 + SZ. v3): print(v3. end. set symmetric difference . ); } III:-

После заполнения, сортировки и вывода векторов v и v2 алгоритм includes() проверяет, содержится ли вторая половина вектора v во всем интервале v. Естественно, это условие заведомо выполняется, поэтому проверка всегда дает положительный результат. Просмотрите результаты вызова алгоритмов set umon(), setJntersection(), set difference() и set symmetric difference() и убедитесь в том, что они работают так, как положено.

Операции с кучей

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

Как и в случае с операциями сортировки, каждый алгоритм существует в двух версиях. Первая версия предполагает, что при сравнении используется внутренний оператор <. Вторая форма проверяет условие а<Ь при помощи операторной функции operatorO(а,Ь) объекта StrictWeakOrdering.

void make heap(RandomAccessIterator first.

RandomAccessIterator last): void make heap(RandomAccessIterator first.

RandomAccessIterator last, StrictWeakOrdering binary pred):

Алгоритм преобразует произвольный интервал в кучу.

void push heap(RandomAccessIterator first.

RandomAccessIterator last): void push hGap(RandomAccessIterator first.

RandomAccessIterator last. StrictWeakOrdering binary pred):

Алгоритм включает элемент *(last-l) в кучу, определяемую интервалом [firstlast-1). Иначе говоря, последний элемент помещается в правильную позицию кучи.

void pop heap(RandomAccessIterator first.

RandomAccessIterator last): void pop heap(RandomAccessIterator first.

RandomAccessIterator last, StrictWeakOrdering binary pred):

Алгоритм помещает наибольщий элемент (который перед выполнением этой операции находится в позиции *first по самому определению кучи) в позицию (last-1) и переупорядочивает остальные элементы так, чтобы они сохраняли правильный порядок следования. Если ограничиться простой выборкой с позиции *first, то следующий элемент не будет следующим по величине элементом кучи. По этой причине необходимо использовать алгоритм pop heap(), чтобы в куче сохранялся правильный порядок следования элементов приоритетной очереди.

void sort heap(RandomAccessIterator first.

RandomAccessIterator last): void sort heap(RandomAccessIterator first,

RandomAccessIterator last. StrictWeakOrdering binary pred):

Алгоритм может рассматриваться как обратный по отношению к mal<e heap(): он берет интервал, элементы которого размещены в порядке кучи, и переупорядочивает его в обычном порядке сортировки, так что интервал перестает быть кучей. Это означает, что после вызова sort heap() для интервала уже нельзя вызывать функции push heap() и pop heap() (вернее, можно, но ничего разумного они уже не сделают). Итоговая сортировка не является устойчивой, то есть относительный порядок следования элементов не сохраняется.

Применение операции к каждому элементу интервала

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

UnaryFunction for each(InputIterator first. Inputlterator last. UnaryFunction f):

Алгоритм применяет объект функции f к каждому элементу интервала [firstlast). Возвращаемое значение каждого отдельного применения f игнорируется. Если f является обычным указателем на функцию, возвращаемое значение обычно интереса не представляет; но если f является объектом с внутренним состоянием, он может накапливать результаты применения f к элементам интервала. Окончательным возвращаемым значением алгоритма for each() является f.

Outputlterator transform(Inputlterator first,

Inputlterator last. Outputlterator result. UnaryFunction f): Outputlterator transform(Inputlteratorl first,

Inputlteratorl last, InputIterator2 f1rst2.

Outputlterator result, BinaryFunction f):

Алгоритм transform(), как и for each(), применяет объект функции f к каждому элементу интервала [firstlast). Но вместо того чтобы игнорировать результаты вызовов функции, transform() копирует их (оператором =) в *result и инкремен-тирует result после каждого копирования. Интервал, на который ссылается ите-

ратор result, должен содержать достаточное количество элементов. Если вы не уверены в этом, используйте итератор вставки и создавайте новые элементы вместо присваивания.

Первая форма transforni() просто вызывает f(*first), где first последовательно перебирает элементы исходного интервала. Вторая форма вызывает f(*firstl,*first2) (длина второго интервала определяется длиной первого интервала). Возвращаемое значение в обоих случаях представляет собой конечный итератор полученного интервала.

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

Начнем с алгоритма for each(). Он перебирает содержимое интервала, последовательно берет каждый элемент и передает его объекту функции, переданному при вызове. В принципе for each() делает то, что вы могли бы запрограммировать вручную; определение for each() в заголовочном файле компилятора выглядит примерно так:

template <class Inputlterator. class Funct1on>

Function for each(Inputlterator first. Inputlterator last, Function f) { while (first != last)

f(*first++): return f:

Следующий пример демонстрирует некоторые нестандартные возможности применения этого алгоритма. Для начала нам потребуется класс, который отслеживает созданные объекты и сообщает об их уничтожении:

: СОб:Counted.h

Класс, отслеживающий свои объекты #ifndef COUNTED H #define COUNTED H #i nclude <vector> #include <iostream>

class Counted {

static int count:

char* ident: public:

Counted(char* id) : ident(id) { count++: } -CountedO { std::cout ident count = --count std::endl:

class CountedVector : public std::vector<Counted*> { public: CountedVector(char* id) { for(int i = 0: i < 5: i++) push back(new Counted(id)):

#endif COUNTED H /:-

: C06:Counter.cpp {0} #include Counted.h