template< class ForwardIterator, class Type > ForwardIterator

upper bound( ForwardIterator first,

ForwardIterator last, const Type &value );

template< class ForwardIterator, class Type, class Compare > ForwardIterator

upper bound( ForwardIterator first,

ForwardIterator last, const Type &value,

Алгоритм upper bound()

Compare comp );

upper bound() возвращает итератор, указывающий на последнюю позицию в отсортированной последовательности [first,last) , в которую еще можно вставить значение value, не нарушая упорядоченности. Значения всех элементов, начиная с этой позиции и далее, будут больше, чем value. Например, если дана последовательность:

int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};

то обращение к upper bound() с value=21 вернет итератор, указывающий на значение 22, а обращение с value=22 - на значение 23. В первом варианте для сравнения используется оператор меньше , определенный для типа элементов контейнера; во втором - заданная программистом операция comp.

#include <algorithm> #include <vector> #include <assert.h> #include <iostream.h>

template <class Type>

void print elements( Type elem ) { cout << elem << ; }

void (*pfi)( int ) = print elements;

int main() {

int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

vector<int,allocator> vec(ia,ia+l2);

sort(ia,ia+12);

int *iter = upper bound(ia,ia+l2,l9);

sort( vec.begin(), vec.end(), greater<int>() ); vector<int,allocator>::iterator iter vec;

iter vec = upper bound( vec.begin(), vec.end(), 27, greater<int>() );

assert( *iter vec == 26 );

печатается: 51 40 35 29 27 26 23 22 20 19 17 15 12 vec.insert( iter vec, 27 );

for each( vec.begin(), vec.end(), pfi ); cout << \n\n ;

Алгоритмы для работы с хипом

В стандартной библиотеке используется макс-хип. Макс-хип - это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SBflCSS). Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:

x T O G S M N A E R A I

В данном примере X - это корневой узел, слева от него находится T, а справа - O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S - потомки узла T, а M и N - потомки узла O. Аналогично A и E - потомки G, R и A - потомки S, I - левый потомок M, а N - листовой узел без потомков.

Четыре обобщенн1х алгоритма для работы с хипом: make heap(), pop heap(), push heap() и sort heap() - поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная

template< class RandomAccessIterator > void

make heap( RandomAccessIterator first, RandomAccessIterator last );

template< class RandomAccessIterator, class Compare > void

make heap( RandomAccessIterator first,

Алгоритм make heap()

RandomAccessIterator last, Compare comp );

make heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор меньше , определенный для типа элементов контейнера, а во втором - операция comp.

template< class RandomAccessIterator > void

pop heap( RandomAccessIterator first, RandomAccessIterator last );

template< class RandomAccessIterator, class Compare > void

pop heap( RandomAccessIterator first,

Алгоритм pop heap()

RandomAccessIterator last, Compare comp );

pop heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1) . После этого вытолкнутый элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop back() . В первом варианте при сравнении используется оператор меньше , определенный для типа элементов контейнера, а во втором - операция comp.

парой итераторов, - действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop heap () и push heap(), так как они требуют изменения размера контейнера. М1 опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.