C++ для начинающих

На самом деле поведение unique() интуитивно не совсем очевидно и напоминает remove(). В обоих случаях размер контейнера не изменяется: каждый уникальный элемент помещается в очередную позицию, начиная с first.

В нашем примере физически будет получено слово misisipippi, где ppi - остаток, "отходы" алгоритма. Возвращаемый итератор указывает на начало этого остатка и обычно передается алгоритму erase() для удаления ненужных элементов. (Поскольку для встроенного массива операция erase() не поддерживается, то лучше воспользоваться алгоритмом unique_copy().) Алгоритм unique_copy()

template class InputIterator, class OutputIterator

OutputIterator

unique_copy( InputIterator first, InputIterator last,

OutputIterator result );

template class InputIterator, class OutputIterator,

class BinaryPredicate

OutputIterator

unique_copy( InputIterator first, InputIterator last,

OutputIterator result, BinaryPredicate pred );

unique_copy() копирует входной контейнер в выходной, заменяя группы одинаковых соседних элементов на один элемент с тем же значением. О том, что понимается под равными элементами, говорилось при описании алгоритма unique(). Чтобы все дубликаты были гарантированно удалены, входной контейнер необходимо предварительно отсортировать. Возвращаемый итератор указывает на элемент за последним скопированным.

#include algorithm

#include vector

#include string

#include iterator

#include assert.h

template class Type

void print_elements( Type elem ) { cout elem " "; }

void (*pfi)( int ) = print_elements;

void (*pfs)( string ) = print_elements;

int main()

{

int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };

vectorint,allocator vec( ia, ia+10 );

vectorint,allocator::iterator vec_iter;

// последовательность не изменяется: нули не стоят рядом

// печатается: 0 1 0 2 0 3 0 4 0 5

vec_iter = unique( vec.begin(), vec.end() );

for_each( vec.begin(), vec.end(), pfi ); cout "\n\n";

// отсортировать вектор, затем применить unique: модифицируется

// печатается: 0 1 2 3 4 5 2 3 4 5

sort( vec.begin(), vec.end() );

vec_iter = unique( vec.begin(), vec.end() );

for_each( vec.begin(), vec.end(), pfi ); cout "\n\n";

// удалить из контейнера ненужные элементы

// печатается: 0 1 2 3 4 5

vec.erase( vec_iter, vec.end() );

for_each( vec.begin(), vec.end(), pfi ); cout "\n\n";

string sa[] = { "enough", "is", "enough",

"enough", "is", "good" };

vectorstring,allocator svec( sa, sa+6 );

vectorstring,allocator vec_result( svec.size() );

vectorstring,allocator::iterator svec_iter;

sort( svec.begin(), svec.end() );

svec_iter = unique_copy( svec.begin(), svec.end(),

vec_result.begin() );

// печатается: enough good is

for_each( vec_result.begin(), svec_iter, pfs );

cout "\n\n";

}

Алгоритм upper_bound()

templateclass 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,

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};

vectorint,allocator vec(ia,ia+12);

sort(ia,ia+12);

int *iter = upper_bound(ia,ia+12,19);

assert( *iter == 20 );

sort( vec.begin(), vec.end(), greaterint() );

vectorint,allocator::iterator iter_vec;

iter_vec = upper_bound( vec.begin(), vec.end(),

27, greaterint() );

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";

}

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

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