С++ для начинающих - Учебное пособие

12. обобщенные алгоритмы

В нашу реализацию класса Array (см. главу 2) мы включили функции-члены для поддержки операций min(), max() и sort(). Однако в стандартном классе vector эти, на первый взгляд фундаментальные, операции отсутствуют. Для нахождения минимального  или  максимального  значения  элементов  вектора  следует  вызвать один из обобщенных алгоритмов. Алгоритмами они называются потому, что реализуют такие распространенные операции, как min(), max(), find() и sort(), а  обобщенными  (generic) –  потому,  что  применимы  к различным  контейнерным типам:  векторам,  спискам,  массивам.  Контейнер  связывается  с  применяемым  к нему обобщенным алгоритмом посредством пары итераторов (мы говорили о них в разделе  6.5),  указывающих,  какие  элементы  следует  посетить  при  обходе контейнера. Специальные объекты-функции позволяют переопределить семантику операторов в обобщенных алгоритмах. Итак, в этой главе рассматриваются обобщенные алгоритмы, объекты-функции и итераторы.

12.1. Краткий обзор

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

1.   По очереди исследовать каждый элемент.

2.   Если элемент равен искомому значению, то вернуть его позицию в коллекции.

3.   В  противном  случае  анализировать  следующий  элемент  Повторять  шаг  2,  пока значение не будет найдено либо пока не будет просмотрена вся коллекция.

4.   Если  мы  достигли  конца  коллекции  и  не  нашли  искомого,  то  вернуть  некоторое значение, показывающее, что нужного элемента нет.

Алгоритм, как мы и утверждали, не зависит ни от типа контейнера, к которому применяется, ни от типа искомого значения, однако для его использования необходимы:

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

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

некоторый обобщенный тип для представления позиции элемента внутри контейнера и специального признака на случай, если элемент не найден. Обычно мы возвращаем индекс элемента либо указатель на него. В ситуации, когда поиск неудачен, возвращается –1 вместо индекса или 0 вместо указателя.

 

Обобщенные алгоритмы решают первую проблему, обход контейнера, с помощью абстракции итератора – обобщенного указателя, поддерживающего оператор инкремента для  доступа   к  следующему  элементу,   оператор   разыменования   для  получения  его значения и операторы равенства и неравенства для определения того, совпадают ли два итератора. Диапазон, к которому применяется алгоритм, помечается парой итераторов: first адресует первый элемент, а last – тот, который следует за последним. К самому элементу,   адресованному   итератором   last,   алгоритм   не   применяется;   он   служит стражем,  прекращающим  обход.  Кроме  того,  last используется  как  возвращаемое значение с семантикой “отсутствует”. Если же значение получено, то возвращается итератор, помечающий позицию найденного элемента.

Имеется по две версии каждого обобщенного алгоритма: в одной для сравнения применяется   оператор   равенства,   а   в   другой –   объект-функция   или   указатель   на функцию, реализующую сравнение. (Объекты-функции рассматриваются в разделе 12.3.) Вот,  например,  реализация  обобщенного  алгоритма  find(),  в  котором  используется

template < class ForwardIterator, class Type > ForwardIterator

find( ForwardIterator first, ForwardIterator last, Type value )

{

for ( ; first != last; ++first )

if ( value == *first )

return first;

return last;

оператор сравнения для типов хранимых в контейнере элементов:

}

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

Алгоритмы достигают независимости от типов за счет того, что никогда не обращаются к элементам  контейнера   непосредственно;   доступ  и  обход  элементов  осуществляются только с помощью итераторов. Неизвестны ни фактический тип контейнера, ни даже то, является ли он контейнером или встроенным массивом. Для работы со встроенным типом массива обобщенному алгоритму можно передать не только обычные указатели, но и итераторы.  Например,  алгоритм  find() для  встроенного  массива  элементов  типа  int можно использовать так:

 

#include <algoritm>

#include <iostream>

int main()

{

int search_value;

int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };

cout << "enter search value: ";

cin >> search_value;

int *presult = find( &ia[0], &ia[6], search_value );

cout << "The value " << search_value

<< ( presult == &ia[6]

? " is not present" : " is present" )

<< endl;

}

Если возвращенный указатель равен адресу &ia[6] (который расположен за последним элементом массива), то поиск оказался безрезультатным, в противном случае значение найдено.

Вообще говоря, при передаче адресов элементов массива обобщенному алгоритму мы можем написать

int *presult = find( &ia[0], &ia[6], search_value );

или

int *presult = find( ia, ia+6, search_value );

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

// искать только среди элементов ia[1] и ia[2]

массива нумеруются с нуля):

int *presult = find( &ia[1], &ia[3], search_value );

А вот пример использования контейнера типа vector с алгоритмом find():

 

#include <algorithm>

#include <vector>

#include <iostream>

int main()

{

int search_value;

int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };

vector<int> vec( ia, ia+6 );

cout << "enter search value: ";

cin >> search_value;

vector<int>::iterator presult;

presult = find( vec.begin(), vec.end(), search_value );

cout << "The value " << search_value

<< ( presult == vec.end()

? " is not present" : " is present" )

<< endl;

}

#include <algorithm>

#include <list>

#include <iostream>

int main()

{

int search_value;

int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };

list<int> ilist( ia, ia+6 );

cout << "enter search value: ";

cin >> search_value;

list<int>::iterator presult;

presult = find( ilist.begin(), ilist.end(), search_value );

cout << "The value " << search_value

<< ( presult == ilist.end()

? " is not present" : " is present" )

<< endl;

find() можно применить и к списку:

}

(В следующем разделе мы обсудим построение программы, в которой используются различные обобщенные алгоритмы, а затем рассмотрим объекты-функции. В разделе 12.4 мы  подробнее  расскажем  об  итераторах.  Развернутое  введение  в  обобщенные алгоритмы –   предмет   раздела   12.5,   а   их   детальное   обсуждение   и   иллюстрация применения вынесено в Приложение. В конце главы речь пойдет о случаях, когда применение обобщенных алгоритмов неуместно.)

Упражнение 12.1

Обобщенные алгоритмы критикуют за то, что при всей элегантности дизайна проверка корректности возлагается на программиста. Например, если передан неверный итератор или  пара  итераторов,  помечающая  неверный  диапазон,  то  поведение  программы  не

 

определено.  Вы  согласны  с такой  критикой?  Следует  ли  оставить  применение обобщенных  алгоритмов  только  наиболее  квалифицированным  специалистам?  Может быть, нужно запретить использование потенциально опасных конструкций, таких, как обобщенные алгоритмы, указатели и явные приведения типов?

12.2. Использование обобщенных алгоритмов

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

1.   Создать копию каждого вектора.

2.   Слить все векторы в один.

3.   Отсортировать его в алфавитном порядке.

4.   Удалить все дубликаты.

5.   Снова отсортировать, но уже по длине слов.

6.   Подсчитать  число  слов,  длина  которых  больше шести  знаков  (предполагается,  что длина – это некоторая мера сложности, по крайней мере, в терминах словаря).

7.   Удалить  семантически  нейтральные  слова  (например,  союзы  and  (и),  if  (если),  or

(или), but (но) и т.д.).

8.   Напечатать получившийся вектор.

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

Аргументом нашей функции является вектор из векторов строк. Мы принимаем указатель

#include <vector>

#include <string>

typedef vector<string, allocator> textwords;

void process_vocab( vector<textwords, allocator> *pvec )

{

if ( ! pvec ) {

// выдать предупредительное сообщение

return;

}

// ...

на него, проверяя, не является ли он нулевым:

}

Нужно создать один вектор, включающий все элементы исходных векторов. Это делается с   помощью   обобщенного   алгоритма   copy() (для   его   использования   необходимо включить заголовочные файлы algorithm и iterator):

 

#include <algorithm>

#include <iterator>

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

vector< string > texts;

vector<textwords, allocator>::iterator iter = pvec->begin();

for ( ; iter != pvec->end(); ++iter )

copy( (*iter).begin(), (*iter).end(), back_inserter( texts ));

// ...

}

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

12.4.).

Алгоритм unique() удаляет из контейнера дубликаты, расположенные рядом. Если дана последовательность 01123211, то результатом будет 012321, а не 0123. Чтобы получить вторую последовательность, необходимо сначала отсортировать вектор с помощью алгоритма  sort();  тогда  из  последовательности  01111223 получится  0123.  (Хотя  на самом деле получится 01231223.)

unique() не  изменяет  размер  контейнера.  Вместо этого  каждый  уникальный  элемент помещается в очередную свободную позицию, начиная с первой. В нашем примере физический   результат –  это  последовательность   01231223;   остаток  1223 –  это,  так сказать,  “отходы”  алгоритма.  unique() возвращает  итератор, указывающий  на начало этого  остатка.  Как  правило,  этот  итератор  затем  передается  алгоритму  erase() для удаления  ненужных  элементов.  (Поскольку  встроенный  массив  не поддерживает операции erase(), то семейство алгоритмов unique() в меньшей степени подходит для

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

// отсортировать вектор texts

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

// удалить дубликаты

vector<string, allocator>::iterator it;

it = unique( texts.begin(), texts.end() );

texts.erase( it, texts.end() );

// ...

работы с ним.) Вот соответствующий фрагмент функции:

}

Ниже   приведен   результат   печати   вектора   texts,   объединяющего   два   небольших текстовых файла, после применения sort(), но до применения unique():

 

a a a a alice alive almost

alternately ancient and and and and and and

and as asks at at beautiful becomes bird

bird blows blue bounded but by calling coat

daddy daddy daddy dark darkened darkening distant each

either emma eternity falls fear fiery fiery flight

flowing for grow hair hair has he heaven,

held her her her her him him home

houses i immeasurable immensity in in in in inexpressibly is is is it it it its

journeying lands leave leave life like long looks magical mean more night, no not not not

now now of of on one one one

passion puts quite red rises row same says

she she shush shyly sight sky so so

star star still stone such tell tells tells

that that the the the the the the

the there there thing through time to to

to to trees unravel untamed wanting watch what

when wind with with you you you you

your your

После применения  unique() и последующего  вызова erase() вектор texts выглядит следующим образом:

a alice alive almost alternately ancient

and as asks at beautiful becomes bird blows

blue bounded but by calling coat daddy dark

darkened darkening distant each either emma eternity falls

fear fiery flight flowing for grow hair has he heaven, held her him home houses i

immeasurable immensity in inexpressibly is it its journeying lands leave life like long looks magical mean

more night, no not now of on one

passion puts quite red rises row same says

she shush shyly sight sky so star still

stone such tell tells that the there thing

through time to trees unravel untamed wanting watch what when wind with you your

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

bool less_than( const string & s1, const string & s2 )

{

return s1.size() < s1.size();

}

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

// отсортировать элементы вектора texts по длине,

// сохранив также прежний порядок

stable_sort( texts.begin(), texts.end(), less_than );

// ...

сравнения “меньше”. Один из возможных способов таков:

}

 

Нужный  результат  при  этом  достигается,  но  эффективность  существенно  ниже,  чем хотелось   бы.   less_than() реализована   в   виде   одной   инструкции.   Обычно   она вызывается как встроенная (inline) функция. Но, передавая указатель на нее, мы не даем компилятору сделать ее встроенной. Способ, позволяющий добиться этого, –применение

// объект-функция - операция реализована с помощью перегрузки

// оператора operator()

class LessThan {

public:

bool operator()( const string & s1, const string & s2 )

{ return s1.size() < s2.size(); }

объекта-функции:

};

Объект-функция – это класс, в котором перегружен оператор вызова operator(). В теле этого оператора и реализуется логика функции, в данном случае сравнение “меньше”. Определение оператора вызова выглядит странно из-за двух пар скобок. Запись

operator()

говорит компилятору, что мы перегружаем оператор вызова. Вторая пара скобок

( const string & s1, const string & s2 )

задает передаваемые ему формальные параметры. Если сравнить это определение с предыдущим  определением  функции  less_than(),  мы  увидим,  что,  за  исключением замены less_than на operator(), они совпадают.

Объект-функция  определяется  так  же,  как  обычный  объект  класса  (правда,  в  данном случае нам не понадобился конструктор: нет членов, подлежащих инициализации):

LessThan lt;

Для  вызова  экземпляра  перегруженного  оператора  мы  применяем  оператор  вызова  к

string st1( "shakespeare" );

string st2( "marlowe" );

// вызывается lt.operator()( st1, st2 );

нашему объекту класса, передавая необходимые аргументы. Например:

bool is_shakespeare_less = lt( st1, st2 );

Ниже   показана   исправленная    функция   process_vocab(),    в   которой    алгоритму

stable_sort() передается безымянный объект-функция LessThan():

 

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

stable_sort( texts.begin(), texts.end(), LessThan() );

// ...

}

Внутри  stable_sort() перегруженный  оператор  вызова  подставляется  в  текст программы  как  встроенная  функция.  (В  качестве  третьего  аргумента  stable_sort() может   принимать   как  указатель   на   функцию   less_than(),   так  и   объект   класса LessThan,  поскольку  аргументом  является  параметр-тип  шаблона.  Подробнее  об объектах-функциях мы расскажем в разделе 12.3.)

Вот результат применения stable_sort() к вектору texts:

a i

as at by he in is it no

of on so to and but for has

her him its not now one red row

she sky the you asks bird blue coat

dark each emma fear grow hair held home

life like long mean more puts same says

star such tell that time what when wind

with your alice alive blows daddy falls fiery

lands leave looks quite rises shush shyly sight still stone tells there thing trees watch almost

either flight houses night, ancient becomes bounded calling distant flowing heaven, magical passion through unravel untamed

wanting darkened eternity beautiful darkening immensity journeying alternately immeasurable inexpressibly

Подсчитать число слов, длина которых больше шести символов, можно с помощью обобщенного алгоритма count_if() и еще одного объекта-функции – GreaterThan. Этот объект чуть сложнее, так как позволяет пользователю задать размер, с которым производится сравнение. Мы сохраняем размер в члене класса и инициализируем его с

#include <iostream>

class GreaterThan {

public:

GreaterThan( int size = 6 ) : _size( size ){}

int size() { return _size; }

bool operator()( const string & s1 )

{ return s1.size() > 6; }

private:

int _size;

помощью конструктора (по умолчанию – значением 6):

};

Использовать его можно так:

 

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

// подсчитать число строк, длина которых больше 6

int cnt = count_if( texts.begin(), texts.end(), GreaterThan() );

cout << "Number of words greater than length six are "

<< cnt << endl;

// ...

}

Этот фрагмент программы выводит такую строку:

Number of words greater than length six are 22

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

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

static string rw[] = { "and", "if", "or", "but", "the" };

vector< string > remove_words( rw, rw+5 );

vector< string >::iterator it2 = remove_words.begin();

for ( ; it2 != remove_words.end(); ++it2 ) {

// просто для демонстрации другой формы count()

int cnt = count( texts.begin(), texts.end(), *it2 );

cout << cnt << " instances removed:  "

<< (*it2) << endl;

texts.erase( remove(texts.begin(),texts.end(),*it2 ), texts.end()

);

}

// ...

которые мы не хотим сохранять:

}

Результат применения remove():

1 instances removed:  and

0 instances removed:  if

0 instances removed:  or

1 instances removed:  but

1 instances removed:  the

 

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

class PrintElem {

public:

PrintElem( int lineLen = 8 )

: _line_length( lineLen ), _cnt( 0 )

{}

void operator()( const string &elem )

{

++_cnt;

if ( _cnt \% _line_length == 0 )

{ cout << ' '; }

cout << elem << " ";

}

private:

int _line_length;

int _cnt;

PrintElem копирует один элемент в стандартный вывод:

void process_vocab( vector<textwords, allocator> *pvec )

{

// ...

for_each( texts.begin(), texts.end(), PrintElem() );

};

}

Вот  и  все.  Мы  получили  законченную  программу,  для  чего  пришлось  лишь последовательно   записать   обращения   к   нескольким   обобщенным   алгоритмам.   Для удобства   мы  приводим   ниже  полный  листинг  вместе  с  функцией   main() для  ее тестирования (здесь используются специальные типы итераторов, которые будут обсуждаться только в разделе 12.4). Мы привели текст реально исполнявшегося кода, который  не  полностью  удовлетворяет  стандарту  C++.  В  частности,  в  нашем распоряжении  были лишь устаревшие реализации  алгоритмов  count() и count_if(), которые не возвращают результат, а требуют передачи дополнительного аргумента для вычисленного  значения.  Кроме того, библиотека  iostream отражает  предшествующую принятию стандарта реализацию, в которой требуется заголовочный файл iostream.h.

 

#include <vector>

#include <string>

#include <algorithm>

#include <iterator>

// предшествующий принятию стандарта синтаксис <iostream>

#include <iostream.h>

class GreaterThan {

public:

GreaterThan( int size = 6 ) : _size( sz ){}

int size() { return _size; }

bool operator()(const string &s1)

{ return s1.size() > _size; }

private:

int _size;

};

class PrintElem {

public:

PrintElem( int lineLen = 8 )

: _line_length( lineLen ), _cnt( 0 )

{}

void operator()( const string &elem )

{

++_cnt;

if ( _cnt \% _line_length == 0 )

{ cout << ' '; }

cout << elem << " ";

}

private:

int _line_length;

int _cnt;

};

public:

bool operator()( const string & s1,

const string & s2 )

С++ дл{я нreачtuиrнnаюsщ1.иsхize() < s2.size();    }

};

typedef vector<string, allocator> textwords;

void process_vocab( vector<textwords, allocator> *pvec )

{

555

 

if ( ! pvec ) {

// вывести предупредительное сообщение

return;

}

vector< string, allocator > texts;

vector<textwords, allocator>::iterator iter;

for ( iter = pvec->begin() ; iter != pvec->end(); ++iter )

copy( (*iter).begin(), (*iter).end(),

back_inserter( texts ));

// отсортировать вектор texts

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

// теперь посмотрим, что получилось

for_each( texts.begin(), texts.end(), PrintElem() );

cout << " "; // разделить части выведенного текста

// удалить дубликаты

vector<string, allocator>::iterator it;

it = unique( texts.begin(), texts.end() );

texts.erase( it, texts.end() );

// посмотрим, что осталось

for_each( texts.begin(), texts.end(), PrintElem() );

cout << " ";

// отсортировать элементы

// stable_sort сохраняет относительный порядок равных элементов

stable_sort( texts.begin(), texts.end(), LessThan() );

for_each( texts.begin(), texts.end(), PrintElem() );

cout << " ";

// подсчитать число строк, длина которых больше 6 int cnt = 0;

// устаревшая форма count - в стандарте используется другая

count_if( texts.begin(), texts.end(), GreaterThan(), cnt );

cout << "Number of words greater than length six are "

<< cnt << endl;

static string rw[] = { "and", "if", "or", "but", "the" };

vector<string,allocator> remove_words( rw, rw+5 );

vector<string, allocator>::iterator it2 = remove_words.begin();

for ( ; it2 != remove_words.end(); ++it2 )

{

int cnt = 0;

// устаревшая форма count - в стандарте используется другая

count( texts.begin(), texts.end(), *it2, cnt );

cout << cnt      << " instances removed: "

<< (*it2) << endl;

texts.erase(

remove(texts.begin(),texts.end(),*it2), texts.end()

);

}

cout << " ";

for_each( texts.begin(), texts.end(), PrintElem() );

}

 

}

Упражнение 12.2

Длина слова – не единственная и, вероятно, не лучшая мера трудности текста. Другой возможный  критерий –  это длина  предложения.  Напишите  программу,  которая читает текст   из   файла   либо   со   стандартного   ввода,   строит   вектор   строк   для   каждого предложения и передает его алгоритму count(). Выведите предложения в порядке сложности. Любопытный способ сделать это – сохранить каждое предложение как одну большую строку во втором векторе строк, а затем передать этот вектор алгоритму sort() вместе с объектом-функцией, который считает, что чем строка короче, тем она меньше. (Более  подробно  с  описанием  конкретного  обобщенного  алгоритма,  а  также  с иллюстрацией его применения вы может ознакомиться в Приложении, где все алгоритмы перечислены в алфавитном порядке.)

Упражнение 12.3

Более надежную оценку уровня трудности текста дает анализ структурной сложности предложений.  Пусть  каждой  запятой  присваивается  1  балл,  каждому  двоеточию  или точке  с  запятой –  2  балла,  а  каждому  тире –  3  балла.  Модифицируйте  программу  из упражнения 12.2 так, чтобы она подсчитывала сложность каждого предложения. Воспользуйтесь алгоритмом count_if() для нахождения каждого из знаков препинания в векторе предложений. Выведите предложения в порядке сложности.

12.3. Объекты-функции

Наша  функция  min() дает  хороший  пример  как  возможностей,  так  и  ограничений

template <typename Type>

const Type&

min( const Type *p, int size )

{

Type minval = p[ 0 ];

for ( int ix = 1; ix < size; ++ix )

if ( p[ ix ] < minval )

minval = p[ ix ];

return minval;

механизма шаблонов:

}

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

Это ограничение вызвано использованием оператора “меньше”: в некоторых случаях базовый   тип   его   не   поддерживает.   Так,   класс   изображения   Image может   и   не предоставлять реализации такого оператора, но мы об этом не знаем и пытаемся найти минимальный кадр анимации в данном массиве изображений. Однако попытка конкретизировать min() для такого массива приведет к ошибке компиляции:

error: invalid types applied to the < operator: Image < Image

(ошибка: оператор < применен к некорректным типам: Image < Image)

 

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

Традиционное  решение  состоит  в  том,  чтобы  параметризовать  оператор  сравнения.  В

данном случае это можно сделать, объявив указатель на функцию, принимающую два

template < typename Type,

bool (*Comp)(const Type&, const Type&)>

const Type&

min( const Type *p, int size, Comp comp )

{

Type minval = p[ 0 ];

for ( int ix = 1; ix < size; ++ix )

if ( Comp( p[ ix ] < minval ))

minval = p[ ix ];

return minval;

аргумента и возвращающую значение типа bool:

}

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

Альтернативная стратегия параметризации заключается в применении объекта-функции вместо  указателя  (примеры  мы  видели  в  предыдущем  разделе).  Объект-функция – это класс, перегружающий оператор вызова (operator()). Такой оператор инкапсулирует семантику обычного вызова функции. Объект-функция, как правило, передается обобщенному алгоритму в качестве аргумента, хотя можно определять и независимые объекты-функции.   Например,   если   бы   был   определен   объект-функция   AddImages, который принимает  два изображения,  объединяет их некоторым образом и возвращает новое изображение, то мы могли бы объявить его следующим образом:

AddImages AI;

Чтобы   объект-функция   удовлетворял   нашим  требованиям,   мы  применяем  оператор

Image im1("foreground.tiff"), im2("background.tiff");

// ...

// вызывает Image AddImages::operator()(const Image1&, const Image2&);

вызова, предоставляя необходимые операнды в виде объектов класса Image:

Image new_image = AI (im1, im2 );

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

 

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

Ниже приведена  измененная  реализация шаблона min() (отметим,  что это объявление

template < typename Type, typename Comp >

const Type&

min( const Type *p, int size, Comp comp )

{

Type minval = p[ 0 ];

for ( int ix = 1; ix < size; ++ix )

if ( Comp( p[ ix ] < minval ))

minval = p[ ix ];

return minval;

допускает также и передачу указателя на функцию, но без проверки прототипа):

}

Как правило, обобщенные алгоритмы поддерживают обе формы применения операции: как использование встроенного (или перегруженного) оператора, так и применение указателя на функцию либо объекта-функции.

Есть три источника появления объектов-функций:

1.   из    набора    предопределенных    арифметических,    сравнительных    и    логических объектов-функций стандартной библиотеки;

2.   из  набора  предопределенных  адаптеров  функций,  позволяющих  специализировать или расширять предопределенные (или любые другие) объекты-функции;

3.   определенные   нами   собственные   объекты-функции   для   передачи   обобщенным алгоритмам. К ним можно применять и адаптеры функций.

В этом разделе мы рассмотрим все три источника объектов-функций.

12.3.1. Предопределенные объекты-функции

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

#include <functional>

Например, объект-функция, поддерживающий сложение, – это шаблон класса с именем

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

#include <functional>

написать:

plus< int > intAdd;

Для выполнения операции сложения мы применяем перегруженный  оператор вызова к

intAdd точно так же, как и к классу AddImage в предыдущем разделе:

 

int ival1 = 10, ival2 = 20;

// эквивалентно int sum = ival1 + ival2;

int sum = intAdd( ival1, ival2 );

Реализация  шаблона  класса  plus вызывает  оператор  сложения,  ассоциированный  с типом  своего  параметра –  int.  Этот  и  другие  предопределенные  объекты-функции применяются прежде всего в качестве аргументов обобщенных алгоритмов и обычно замещают  подразумеваемую  по умолчанию  операцию.  Например,  по умолчанию алгоритм sort() располагает элементы контейнера в порядке возрастания с помощью оператора   “меньше”   базового   типа.   Для   сортировки   по   убыванию   мы   передаем

vector< string > svec;

// ...

предопределенный шаблон класса greater, который вызывает оператор “больше”:

sort( svec.begin(), svec.end(), greater<string>() );

Предопределенные объекты-функции перечислены в следующих разделах и разбиты на категории: арифметические, логические и сравнительные. Применение каждого из них иллюстрируется как в качестве именованного, так и в качестве безымянного объекта, передаваемого функции. Мы пользуемся следующими определениями объектов, включая и определение простого класса (перегрузка операторов подробно рассматривается в главе

class Int {

public:

Int( int ival = 0 ) : _val( ival ) {}

int operator-() { return -_val; }

int operator\%(int ival)  { return -_val \% ival;  }

bool operator<(int ival) { return -_val < ival; }

bool operator!()           { return -_val == 0;     }

private:

int _val;

};

vector< string > svec; string sval1, sval2, sres; complex cval1, cval2, cres; int          ival1, ival2, ires; Int    Ival1, Ival2, Ires;

15):

double  dval1, dval2, dres;

Кроме  того,   мы   определяем   два   шаблона   функций,  которым   передаем   различные безымянные объекты-функции:

 

template <class FuncObject, class Type>

Type UnaryFunc( FuncObject fob, const Type &val )

{ return fob( val ); }

template <class FuncObject, class Type> Type BinaryFunc( FuncObject fob,

const Type &val1, const Type &val2 )

{ return fob( val1, val2 ); }

12.3.2. Арифметические объекты-функции

Предопределенные  арифметические  объекты-функции  поддерживают  операции сложения, вычитания, умножения, деления, взятия остатка и вычисления противоположного    по    знаку    значения.    Вызываемый    оператор –    это    экземпляр, ассоциированный с типом Type. Если тип является классом, предоставляющим перегруженную реализацию оператора, то именно эта реализация и вызывается.

plus<string> stringAdd;

// вызывается string::operator+()

sres = stringAdd( sval1, sval2 );

Сложение: plus<Type>

dres = BinaryFunc( plus<double>(), dval1, dval2 );

minus<int> intSub;

ires = intSub( ival1, ival2 );

Вычитание: minus<Type>

dres = BinaryFunc( minus<double>(), dval1, dval2 );

multiplies<complex> complexMultiplies;

cres = complexMultiplies( cval1, cval2 );

Умножение: multiplies<Type>

dres = BinaryFunc( multiplies<double>(), dval1, dval2 );

divides<int> intDivides;

ires = intDivides( ival1, ival2 );

Деление: divides<Type>

dres = BinaryFunc( divides<double>(), dval1, dval2 );

Взятие остатка: modulus<Type>

 

modulus<Int> IntModulus;

Ires = IntModulus( Ival1, Ival2 );

ires = BinaryFunc( modulus<int>(), ival1, ival2 );

negate<int> intNegate;

ires = intNegate( ires );

Вычисление противоположного значения: negate<Type>

Ires = UnaryFunc( negate<Int>(), Ival1 );

12.3.3. Сравнительные объекты-функции

Сравнительные   объекты-функции   поддерживают   операции   равенства,   неравенства,

больше, больше или равно, меньше, меньше или равно.

equal_to<string> stringEqual;

sres = stringEqual( sval1, sval2 );

ires = count_if( svec.begin(), svec.end(),

Равенство: equal_to<Type>

equal_to<string>(), sval1 );

not_equal_to<complex> complexNotEqual; cres = complexNotEqual( cval1, cval2 ); ires = count_if( svec.begin(), svec.end(),

Неравенство: not_equal_to<Type>

not_equal_to<string>(), sval1 );

greater<int> intGreater;

ires = intGreater( ival1, ival2 );

ires = count_if( svec.begin(), svec.end(),

Больше: greater<Type>

greater<string>(), sval1 );

greater_equal<double> doubleGreaterEqual; dres = doubleGreaterEqual( dval1, dval2 ); ires = count_if( svec.begin(), svec.end(),

Больше или равно: greater_equal<Type>

 

greater_equal <string>(), sval1 );

less<Int> IntLess;

Ires = IntLess( Ival1, Ival2 );

ires = count_if( svec.begin(), svec.end(),

Меньше: less<Type>

less<string>(), sval1 );

less_equal<int> intLessEqual;

ires = intLessEqual( ival1, ival2 );

ires = count_if( svec.begin(), svec.end(),

Меньше или равно: less_equal<Type>

less_equal<string>(), sval1 );

12.3.4. Логические объекты-функции

Логические объекты-функции поддерживают операции “логическое И” (возвращает true, если  оба  операнда  равны  true, –  применяет  оператор  &&,  аcсоциированный  с  типом Type),  “логическое  ИЛИ”  (возвращает  true,  если  хотя  бы  один  из  операндов  равен true, –  применяет  оператор  ||,  аcсоциированный  с  типом  Type)  и  “логическое  НЕ” (возвращает true, если операнд равен false, – применяет оператор !, аcсоциированный с типом Type)

logical_and<int> intAnd;

ires = intLess( ival1, ival2 );

Логическое И: logical_and<Type>

dres = BinaryFunc( logical_and<double>(), dval1, dval2 );

logical_or<int> intSub;

ires = intSub( ival1, ival2 );

Логическое ИЛИ: logical_or<Type>

dres = BinaryFunc( logical_or<double>(), dval1, dval2 );

logical_not<Int> IntNot;

ires = IntNot( Ival1, Ival2 );

Логическое НЕ: logical_not<Type>

dres = UnaryFunc( logical_or<double>(), dval1 );

 

12.3.5. Адаптеры функций для объектов-функций

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

связыватели (binders). Это адаптеры, преобразующие бинарный объект-функцию в унарный объект, связывая один из аргументов с конкретным значением. Например, для подсчета в контейнере всех элементов, которые меньше или равны 10, следует передать  алгоритму  count_if() объект-функцию  less_equal,  один из аргументов которого равен 10. В следующем разделе мы покажем, как это сделать;

отрицатели (negators). Это адаптеры, изменяющие значение истинности объекта- функции на противоположное. Например, для подсчета всех элементов внутри контейнера, которые больше 10, мы могли бы передать алгоритму count_if() отрицатель объекта-функции less_equal, один из аргументов которого равен 10. Конечно, в данном случае проще передать связыватель объекта-функции greater, ограничив один из аргументов со значением 10.

В стандартную библиотеку входит два предопределенных адаптера-связывателя: bind1st и  bind2nd,   причем  bind1st связывает   некоторое  значение  с  первым  аргументом бинарного  объекта-функции,  а  bind2nd –  со вторым.  Например,  для подсчета  внутри контейнера  всех  элементов,  которые  меньше  или  равны  10,  мы  могли  бы  передать

count_if( vec.begin(), vec.end(),

алгоритму count_if() следующее:

bind2nd( less_equal<int>(), 10 ));

В стандартной библиотеке также есть два предопределенных адаптера-отрицателя: not1 и not2.   not1 инвертирует   значение   истинности   унарного   предиката,   являющегося объектом-функцией,    а    not2 –    значение    бинарного    предиката.    Для    отрицания рассмотренного   выше   связывателя   объекта-функции   less_equal можно   написать

count_if( vec.begin(), vec.end(),

 

 

следующее:

not1( bind2nd( less_equal<int>(), 10 )));

 

 

Другие примеры использования связывателей и отрицателей приведены в Приложении,

вместе с примерами использования каждого алгоритма.

12.3.6. Реализация объекта-функции

При  реализации   программы   в  разделе  12.2  нам  уже  приходилось   определять  ряд объектов-функций. В этом разделе мы изучим необходимые шаги и возможные вариации при  определении  класса  объекта-функции.  (В  главе  13  определение  класса рассматривается детально; в главе 15 обсуждается перегрузка операторов.)

 

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

// простейшая форма класса объекта-функции

class less_equal_ten {

public:

bool operator() ( int val )

{ return val <= 10; }

некоторое значение меньше или равно 10:

};

Теперь такой объект-функцию можно использовать точно так же, как предопределенный. Вызов алгоритма count_if() с помощью нашего объекта-функции выглядит следующим образом:

count_if( vec.begin(), vec.end(), less_equal_ten() );

Разумеется,   возможности   этого   класса   весьма   ограничены.   Попробуем   применить

count_if( vec.begin(), vec.end(),

отрицатель, чтобы подсчитать, сколько в контейнере элементов, больших 10:

not1(less_equal_then ()));

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

class less_equal_value {

public:

less_equal_value( int val ) : _val( val ) {}

bool operator() ( int val ) { return val <= _val; }

private:

int _val;

указанной пользователем величиной:

};

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

count_if( vec.begin(), vec.end(), less_equal_value( 25 ));

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

с которым производится сравнение:

 

template < int _val > class less_equal_value { public:

bool operator() ( int val ) { return val <= _val; }

};

Вот как надо было бы вызвать такой класс для подсчета числа элементов, меньших или равных 25:

count_if( vec.begin(), vec.end(), less_equal_value<25>());

(Другие    примеры    определения    собственных    объектов-функций    можно    найти    в

Приложении.)

Упражнение 12.4

Используя предопределенные объекты-функции  и адаптеры, создайте объекты-функции для решения следующих задач:

(a)  Найти все значения, большие или равные 1024. (b)  Найти все строки, не равные "pooh".

(c)  Умножить все значения на 2.

Упражнение 12.5

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

12.4. Еще раз об итераторах

Следующая  реализация  шаблона  функции  не  компилируется.  Можете  ли  вы  сказать,

// в таком виде это не компилируется

template < typename type >

int

count( const vector< type > &vec, type value )

{

int count = 0;

vector< type >::iterator iter = vec.begin();

while ( iter != vec.end() )

if ( *iter == value )

++count;

return count;

почему?

}

Проблема в том, что у ссылки vec есть спецификатор const, а мы пытаемся связать с ней итератор без такого спецификатора. Если бы это было разрешено, то ничто не помешало бы   нам   модифицировать    с   помощью   этого   итератора    элементы   вектора.   Для

 

предотвращения подобной ситуации язык требует, чтобы итератор, связанный с const-

// правильно: это компилируется без ошибок

вектором, был константным. Мы можем сделать это следующим образом:

vector< type>::const_iterator iter = vec.begin();

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

Операции begin() и end() перегружены и возвращают константный или неконстантный итератор в зависимости от наличия спецификатора const в объявлении контейнера. Если

vector< int > vec0;

дана такая пара объявлений:

const vector< int > vec1;

то при обращениях к begin() и end() для vec0 будет возвращен неконстантный, а для

vector< int >::iterator iter0 = vec0.begin();

vec1 – константный итератор:

vector< int >::const_iterator iter1 = vec1.begin();

Разумеется,  присваивание  константному  итератору  неконстантного  разрешено  всегда.

// правильно: инициализация константного итератора неконстантным

Например:

vector< int >::const_iterator iter2 = vec0.begin();

12.4.1. Итераторы вставки

Вот еще один фрагмент программы, в котором есть тонкая, но серьезная ошибка. Видите

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

vector< int > ivec( ia, ia+8 ), vres;

// ...

// поведение программы во время выполнения не определено

ли вы, в чем она заключается?

unique_copy( ivec.begin(), ivec.end(), vres.begin() );

 

Проблема  вызвана  тем,  что  алгоритм  unique_copy() использует  присваивание  для копирования значения каждого элемента из вектора ivec, но эта операция завершится неудачно, поскольку в vres не выделено место для хранения девяти целых чисел.

Можно было бы написать две версии алгоритма unique_copy(): одна присваивает элементы, а вторая вставляет их. Эта последняя версия должна, в таком случае, поддерживать вставку в начало, в конец или в произвольное место контейнера.

Альтернативный  подход,  принятый  в  стандартной  библиотеке,  заключается  в определении трех адаптеров, которые возвращают специальные итераторы вставки:

back_inserter() вызывает   определенную   для   контейнера   операцию   вставки

push_back() вместо   оператора    присваивания.    Аргументом    back_inserter()

// правильно: теперь unique_copy() вставляет элементы с помощью

// vres.push_back()...

unique_copy( ivec.begin(), ivec.end(),

является сам контейнер. Например, вызов unique_copy() можно исправить, написав:

back_inserter( vres ) );

front_inserter() вызывает   определенную   для   контейнера   операцию   вставки push_front() вместо оператора присваивания. Аргументом front_inserter() тоже является  сам  контейнер.   Заметьте,   однако,   что  класс  vector не  поддерживает

// увы, ошибка:

// класс vector не поддерживает операцию push_front()

// следует использовать контейнеры deque или list

unique_copy( ivec.begin(), ivec.end(),

push_front(), так что использовать такой адаптер для вектора нельзя:

front_inserter( vres ) );

inserter() вызывает  определенную  для  контейнера  операцию  вставки  insert()

вместо   оператора   присваивания.   inserter() принимает   два   аргумента:   сам

unique_copy( ivec.begin(), ivec.end(),

контейнер и итератор, указывающий позицию, с которой должна начаться вставка:

inserter( vres ), vres.begin() );

Итератор, указывающий на позицию начала вставки, сдвигается вперед после каждой вставки,  так  что  элементы  располагаются  в  нужном  порядке,  как  если  бы  мы

vector< int >::iterator iter = vres.begin(), iter2 = ivec.begin();

for ( ; iter2 != ivec.end() ++ iter, ++iter2 )

написали:

vres.insert( iter, *iter2 );

 

12.4.2. Обратные итераторы

Операции  begin() и  end() возвращают  соответственно  итераторы,  указывающие  на первый элемент и на элемент, расположенный за последним. Можно также вернуть обратный итератор, обходящий контейнер от последнего элемента к первому. Во всех контейнерах  для  поддержки  такой  возможности  используются  операции  rbegin() и

vector< int > vec0;

const vector< int > vec1;

vector< int >::reverse_iterator r_iter0 = vec0.rbegin();

rend(). Есть константные и неконстантные версии обратных итераторов:

vector< int >::const_reverse_iterator r_iter1 = vec1.rbegin();

Обратный итератор применяется так же, как прямой. Разница состоит в реализации операторов перехода к следующему и предыдущему элементам. Для прямого итератора оператор ++ дает доступ к следующему элементу контейнера, тогда как для обратного – к

// обратный итератор обходит вектор от конца к началу

vector< type >::reverse_iterator r_iter;

for ( r_iter = vec0.rbegin();     // r_iter указывает на последний элемент

r_iter != vec0.rend();   // пока не достигли элемента перед первым

r_iter++ )         // переходим к предыдущему элементу

предыдущему. Например, для обхода вектора в обратном направлении следует написать:

{ /* ... */ }

Инвертирование семантики операторов инкремента и декремента может внести путаницу, но зато позволяет программисту передавать алгоритму пару обратных итераторов вместо прямых.  Так,  для  сортировки  вектора  в  порядке  убывания  мы  передаем  алгоритму

// сортирует вектор в порядке возрастания

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

// сортирует вектор в порядке убывания

sort() пару обратных итераторов:

sort( vec0.rbegin(), vec0.rend() );

12.4.3. Потоковые итераторы

Стандартная   библиотека   предоставляет  средства   для  работы  потоковых   итераторов чтения и записи совместно со стандартными контейнерами и обобщенными алгоритмами. Класс istream_iterator поддерживает итераторные операции с классом istream или одним  из  производных  от  него,  например  ifstream для  работы  с  потоком  ввода  из файла. Аналогично ostream_iterator поддерживает итераторные операции с классом ostream или одним из производных от него, например ofstream для работы с потоком вывода в файл. Для использования любого из этих итераторов следует включить заголовочный файл

 

#include <iterator>

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

#include <iostream>

#include <iterator>

#include <algorithm>

#include <vector>

#include <functional>

/*

* вход:

* 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

*

* выход:

* 109 90 89 56 45 34 23 12 8 6

*/

int main()

{

istream_iterator< int > input( cin );

istream_iterator< int > end_of_stream;

vector<int> vec;

copy ( input, end_of_stream, inserter( vec, vec.begin() ));

sort( vec.begin(), vec.end(), greater<int>() );

ostream_iterator< int > output( cout, " " );

unique_copy( vec.begin(), vec.end(), output );

unique_copy():

}

12.4.4. Итератор istream_iterator

 

В общем виде объявление потокового итератора чтения istream_iterator имеет форму:

istream_iterator<Type> identifier( istream& );1.

 

Примечание [O.A.3]: Нумера ция сносок сбита.

 

 

1.   Если   имеющийся   у   Вас   компилятор   пока   не   поддерживает   параметр шаблонов  по  умолчанию,   то  конструктору   istream_iterator необходимо будет  явно  передать  также  и второй аргумент:  тип difference_type, способный хранить результат вычитания двух итераторов контейнера, куда помещаются элементы. Например, в разделе 12.2 при изучении программы, которая  должна  транслироваться  компилятором,  не  поддерживающим параметры шаблонов по умолчанию, мы писали:

typedef vector<string,allocator>::difference_type diff_type istream_iterator< string, diff_type > input_set1( infile1 ), eos; istream_iterator< string, diff_type > input_set2( infile2 );

 

где  Type –  это  любой  встроенный  или  пользовательский  тип  класса,  для  которого определен оператор ввода. Аргументом конструктора может быть объект либо класса istream,   например   cin,   либо   производного   от   него   класса   с   открытым   типом

#include <iterator>

#include <fstream>

#include <string>

#include <complex>

// прочитать последовательность объектов типа complex

// из стандартного ввода

istream_iterator< complex > is_complex( cin );

// прочитать последовательность строк из именованного файла

ifstream infile( "C++Primer" );

наследования – ifstream:

istream_iterator< string > is_string( infile );

При  каждом  применении  оператора  инкремента  к  объекту  типа  istream_iterator читается следующий элемент из входного потока, для чего используется оператор operator>>(). Чтобы сделать то же самое в обобщенных алгоритмах, необходимо предоставить пару итераторов, обозначающих начальную и конечную позицию в файле. Начальную     позицию     дает     istream_iterator,     инициализированный     объектом istream, –   такой,   скажем,   как  is_string.   Для   получения   конечной   позиции   мы

// конструирует итератор end_of_stream, который будет служить маркером

// конца потока в итераторной паре

istream_iterator< string > end_of_stream

vector<string> text;

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

copy( is_string, end_of_stream,

inserter( text, text.begin() ));

используем специальный конструктор по умолчанию класса istream_iterator:

12.4.5. Итератор ostream_iterator

Объявление потокового итератора записи ostream_iterator может быть представлено в двух формах:

Если бы компилятор полностью удовлетворял стандарту C++, достаточно было бы написать так:

istream_iterator< string > input_set1( infile1 ), eos;

istream_iterator< string > input_set2( infile2 );

 

ostream_iterator<Type> identifier( ostream& )

ostream_iterator<Type> identifier( ostream&, char * delimiter )

где  Type –  это  любой  встроенный  или  пользовательский  тип  класса,  для  которого определен    оператор    вывода    (operator<<).    Во   второй    форме   delimiter –   это разделитель,  то  есть  C-строка  символов,  которая  выводится  в  файл  после  каждого элемента. Такая строка должна заканчиваться двоичным нулем, иначе поведение программы не определено (скорее всего, она аварийно завершит выполнение). В качестве аргумента  ostream может  выступать  объект  класса  ostream,  например  cout,  либо

#include <iterator>

#include <fstream>

#include <string>

#include <complex>

// записать последовательность объектов типа complex

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

ostream_iterator< complex > os_complex( cin, " " );

// записать последовательность строк в именованный файл

ofstream outfile( "dictionary" );

производного от него класса с открытым типом наследования, скажем ofstream:

ostream_iterator< string > os_string( outfile, " " );

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

#include <iterator>

#include <algorithm>

#include <iostream>

int main()

{

copy( istream_iterator< int >( cin ), istream_iterator< int >(), ostream_iterator< int >( cout, " " ));

с помощью безымянных потоковых итераторов и обобщенного алгоритма copy():

}

Ниже  приведена  небольшая  программа,  которая  открывает  указанный  пользователем файл  и  копирует  его  на  стандартный  вывод,  применяя  для  этого  алгоритм  copy() и потоковый итератор записи ostream_iterator:

 

#include <string>

#include <algorithm>

#include <fstream>

#include <iterator>

 

 

main()

{

string file_name;

cout << "please enter a file to open: ";

cin >> file_name;

if ( file_name.empty() || !cin ) {

cerr << "unable to read file name "; return -1;

}

ifstream infile( file_name.c_str());

if ( !infile ) {

cerr << "unable to open " << file_name << endl;

return -2;

}

istream_iterator< string > ins( infile ), eos; ostream_iterator< string > outs( cout, " " ); copy( ins, eos, outs );

 

 

}

12.4.6. Пять категорий итераторов

Для поддержки полного набора обобщенных алгоритмов стандартная библиотека определяет пять категорий итераторов, положив в основу классификации множество операций. Это итераторы чтения (InputIterator), записи (OutputIterator), однонаправленные (ForwardIterator) и двунаправленные итераторы (BidirectionalIterator), а также итераторы с произвольным доступом (RandomAccessIterators). Ниже приводится краткое обсуждение характеристик каждой категории:

итератор чтения можно использовать для получения элементов из контейнера, но поддержка  записи  в  контейнер  не  гарантируется.  Такой  итератор  должен обеспечивать следующие операции (итераторы, поддерживающие также дополнительные операции, можно употреблять в качестве итераторов чтения при условии, что они удовлетворяют минимальным требованиям): сравнение двух итераторов  на  равенство  и  неравенство,  префиксная  и  постфиксная  форма инкремента итератора для адресации следующего элемента (оператор ++), чтение элемента   с  помощью   оператора   разыменования   (*).   Такого   уровня   поддержки требуют,   в   частности,   алгоритмы   find(),   accumulate() и   equal().   Любому алгоритму,   которому   необходим   итератор   чтения,   можно   передавать   также   и итераторы категорий, описанных в пунктах 3, 4 и 5;

итератор  записи  можно  представлять  себе  как  противоположный  по функциональности итератору чтения. Иными словами, его можно использовать для записи элементов контейнера, но поддержка чтения из контейнера не гарантируется. Такие итераторы обычно применяются в качестве третьего аргумента алгоритма (например, copy()) и указывают на позицию, с которой надо начинать копировать.

 

Любому алгоритму, которому необходим итератор записи, можно передавать также и итераторы других категорий, перечисленных в пунктах 3, 4 и 5;

однонаправленный  итератор можно использовать для чтения и записи в контейнер, но только в одном направлении обхода (обход в обоих направлениях поддерживается итераторами  следующей  категории).  К  числу  обобщенных  алгоритмов,  требующих как минимум однонаправленного итератора, относятся adjacent_find(), swap_range() и  replace().   Конечно,  любому  алгоритму,  которому  необходим подобный  итератор,  можно  передавать  также  и  итераторы  описанных  ниже категорий;

двунаправленный итератор может читать и записывать в контейнер, а также перемещаться по нему в обоих направлениях. Среди обобщенных алгоритмов, требующих как минимум двунаправленного итератора, выделяются place_merge(), next_permutation() и reverse();

итератор  с  произвольным  доступом,  помимо  всей  функциональности, поддерживаемой  двунаправленным  итератором,  обеспечивает  доступ  к любой позиции  внутри  контейнера  за  постоянное  время.  Подобные  итераторы  требуются таким   обобщенным   алгоритмам,   как   binary_search(),   sort_heap() и   nth- element().

Упражнение 12.6

Объясните, почему некорректны следующие примеры. Какие ошибки обнаруживаются во

(a) const vector<string> file_names( sa, sa+6 );

vector<string>::iterator it = file_names.begin()+2;

(b) const vector<int> ivec;

fill( ivec.begin(), ivec.end(), ival );

(c) sort( ivec.begin(), ivec.end() ); (d) list<int> ilist( ia, ia+6 );

binary_search( ilist.begin(), ilist.end() );

время компиляции?

(e) sort( ivec1.begin(), ivec3.end() );

Упражнение 12.7

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

12.5. Обобщенные алгоритмы

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

 

(иногда   его   называют   интервалом   с   включенной   левой   границей)   обозначается

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

// кроме последнего

следующим образом:

[ first, last )

Эта запись говорит о том, что диапазон начинается с элемента first и продолжается до элемента last, исключая последний. Если

first == last

то говорят, что диапазон пуст.

К паре итераторов предъявляется следующее требование: если начать с элемента first и последовательно применять оператор инкремента, то возможно достичь элемента last. Однако компилятор не в состоянии проверить выполнение этого ограничения; если оно нарушается, поведение программы не определено, обычно все заканчивается аварийным остановом и дампом памяти.

В объявлении каждого алгоритма указывается минимально необходимая категория итератора (см. раздел 12.4). Например, для алгоритма find(), реализующего однопроходный  обход  контейнера  с  доступом  только  для  чтения,  требуется  итератор чтения, но можно передать и однонаправленный или двунаправленный итератор, а также итератор  с  произвольным  доступом.  Однако  передача  итератора  записи  приведет  к ошибке.   Не  гарантируется,   что  ошибки,  связанные  с  передачей   итератора  не  той категории, будут обнаружены во время компиляции, поскольку категории итераторов – это не собственно типы, а лишь параметры-типы, передаваемые шаблону функции.

Некоторые  алгоритмы  существуют  в  нескольких  версиях:  в одной  используется встроенный оператор, а во второй – объект-функция или указатель на функцию, которая предоставляет  альтернативную  реализацию  оператора.  Например,  unique() по умолчанию сравнивает два соседних элемента с помощью оператора равенства, определенного для типа объектов в контейнере. Но если такой оператор равенства не определен или мы хотим сравнивать элементы иным способом, то можно передать либо объект-функцию, либо указатель на функцию, обеспечивающую нужную семантику. Встречаются  также  алгоритмы  с  похожими,  но  разными  именами.  Так,  предикатные версии всегда имеют имя, оканчивающееся на _if, например find_if(). Скажем, есть алгоритм replace(), реализованный с помощью встроенного оператора равенства, и replace_if(), которому передается объект-предикат или указатель на функцию.

Алгоритмы, модифицирующие контейнер, к которому они применяются, обычно имеют две  версии:  одна  преобразует  содержимое  контейнера  по  месту,  а  вторая  возвращает копию исходного контейнера, в которой и отражены все изменения. Например, есть алгоритмы  replace() и  replace_copy() (имя  версии  с  копированием  всегда заканчивается на _copy). Однако не у всех алгоритмов, модифицирующих контейнер, имеется такая версия. К примеру, ее нет у алгоритма sort(). Если же мы хотим, чтобы сортировалась копия, то создать и передать ее придется самостоятельно.

Для использования любого обобщенного алгоритма необходимо включить в программу заголовочный файл

#include <algorithm>

 

А   для    любого    из    четырех    численных    алгоритмов –   adjacent_differences(),

accumulate(), inner_product() и partial_sum() – включить также заголовок

#include <numeric>

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

12.5.1. Алгоритмы поиска

Тринадцать алгоритмов поиска предоставляют различные способы нахождения определенного значения в контейнере. Три алгоритма equal_range(), lower_bound() и upper_bound() выполняют ту или иную форму двоичного поиска. Они показывают, в

adjacent_find(), binary_search(), count(),count_if(), equal_range(), find(), find_end(), find_first_of(), find_if(), lower_bound(),

какое место контейнера можно вставить новое значение, не нарушая порядка сортировки.

upper_bound(), search(), search_n()

12.5.2. Алгоритмы сортировки и упорядочения

Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения  элементов  контейнера.  Разбиение  (partition) –  это  разделение  элементов контейнера   на   две   группы:   удовлетворяющие   и   не   удовлетворяющие   некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый (stable)  алгоритм  сохраняет  относительный  порядок  элементов  с  одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:

{ "pshew", "honey", "Tigger", "Pooh" }

то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует   последовательность,   в   которой   относительный   порядок   слов   в   каждой категории сохранен:

{ "Tigger", "Pooh", "pshew", "honey" }

При     использовании          неустойчивой            версии            алгоритма      сохранение    порядка          не гарантируется.  (Отметим,  что  алгоритмы  сортировки  нельзя  применять  к  списку  и

inplace_merge(), merge(), nth_element(), partial_sort(), partial_sort_copy(), partition(), random_shuffle(), reverse(), reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),

ассоциативным контейнерам, таким, как множество (set) или отображение (map).)

stable_partition()

 

12.5.3. Алгоритмы удаления и подстановки

Пятнадцать  алгоритмов  удаления  и  подстановки  предоставляют  различные  способы замены  или  исключения  одного  элемента  или  целого  диапазона.  unique() удаляет одинаковые    соседние    элементы.    iter_swap() обменивает    значения    элементов,

copy(), copy_backwards(), iter_swap(), remove(), remove_copy(), remove_if(),remove_if_copy(), replace(), replace_copy(), replace_if(), replace_copy_if(), swap(), swap_range(), unique(),

адресованных парой итераторов, но не модифицирует сами итераторы.

unique_copy()

12.5.4. Алгоритмы перестановки

Рассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шесть различных  перестановок:  abc,  acb,  bac,  bca,  cab и  cba,  лексикографически упорядоченных   на   основе   оператора   “меньше”.   Таким   образом,   abc –  это  первая перестановка,  потому  что  каждый  элемент  меньше  последующего.  Следующая перестановка –  acb,  поскольку  в  начале  все  еще  находится  a –  наименьший  элемент последовательности.  Соответственно  перестановки,  начинающиеся  с  b,  предшествуют тем,   которые   начинаются   с   с.   Из   bac и   bca меньшей   является   bac,   так   как последовательность ac лексикографически меньше, чем ca. Если дана перестановка bca, то можно сказать, что предшествующей  для нее будет bac, а последующей – cab. Для перестановки abc нет предшествующей, а для cba – последующей.

next_permutation(), prev_permutation()

12.5.5. Численные алгоритмы

Следующие  четыре  алгоритма  реализуют  численные  операции  с контейнером.  Для их использования необходимо включить заголовочный файл <numeric>.

accumulate(), partial_sum(), inner_product(), adjacent_difference()

12.5.6. Алгоритмы генерирования и модификации

Шесть  алгоритмов  генерирования  и  модификации  либо  создают  и  заполняют  новую последовательность, либо изменяют значения в существующей.

fill(), fill_n(), for_each(), generate(),generate_n(), transform()

12.5.7. Алгоритмы сравнения

Семь   алгоритмов   дают   разные   способы   сравнения   одного   контейнера   с   другим

(алгоритмы    min()    и          max()   сравнивают    два      элемента).      Алгоритм

 

lexicographical_compare() выполняет лексикографическое (словарное) упорядочение

equal(), includes(), lexicographical_compare(), max(), max_element(),

(см. также обсуждение перестановок и Приложение).

min(), min_element(), mismatch()

12.5.8. Алгоритмы работы с множествами

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

set_union(), set_intersection(), set_difference(),

но не обоим.

set_symmetric_difference()

12.5.9. Алгоритмы работы с хипом

Хип   (heap) –   это   разновидность   двоичного   дерева,   представленного   в   массиве. Стандартная  библиотека  предоставляет  такую  реализацию  хипа,  в  которой  значение ключа в любом узле больше либо равно значению ключа в любом потомке этого узла.

make_heap(), pop_heap(), push_heap(), sort_heap()

12.6.    Когда нельзя использовать обобщенные алгоритмы

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

Контейнер  list (список)  реализован  в  виде  двусвязного  списка:  в  каждом  элементе, помимо   собственно   данных,   хранятся   два   члена-указателя –   на   следующий   и   на предыдущий  элементы.  Основное  преимущество  списка –  это  эффективная  вставка  и удаление  одного   элемента   или  целого  диапазона   в  произвольное  место  списка,  а недостаток – невозможность произвольного доступа. Например, можно написать:

vector<string>::iterator vec_iter = vec.begin() + 7;

 

Такая форма вполне допустима и инициализирует vec_iter адресом восьмого элемента

// ошибка: арифметические операции над итераторами

// не поддерживаются списком

вектора, но запись

list<string>::iterator list_iter = slist.begin() + 7;

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

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

list::merge() объединяет два отсортированных списка list::remove() удаляет элементы с заданным значением list::remove_if()удаляет элементы, удовлетворяющие некоторому условию list::reverse() переставляет элементы списка в обратном порядке list::sort() сортирует элементы списка

list::splice() перемещает элементы из одного списка в другой

list::unique() оставляет один элемент  из каждой  цепочки  одинаковых смежных элементов

void list::merge( list rhs );

template <class Compare>

12.6.1. Операция list_merge()

void list::merge( list rhs, Compare comp );

Элементы   двух   упорядоченных   списков   объединяются   либо   на   основе   оператора “меньше”, определенного для типа элементов в контейнере, либо на основе указанной пользователем операции сравнения. (Заметьте, что элементы списка rhs перемещаются в список, для которого вызвана функция-член  merge(); по завершении операции список rhs будет пуст.) Например:

 

int array1[ 10 ] = { 34, 0, 8, 3, 1, 13, 2, 5, 21, 1 };

int array2[ 5 ] = { 377, 89, 233, 55, 144 };

list< int > ilist1( array1, array1 + 10 );

list< int > ilist2( array2, array2 + 5 );

// для объединения требуется, чтобы оба списка были упорядочены

ilist1.sort(); ilist2.sort();

ilist1.merge( ilist2 );

После выполнения операции merge() список ilist2 пуст, а ilist1 содержит первые 15

чисел Фибоначчи в порядке возрастания.

12.6.2. Операция list::remove()

void list::remove( const elemType &value );

Операция remove() удаляет все элементы с заданным значением:

ilist1.remove( 1 );

template < class Predicate >

12.6.3. Операция list::remove_if()

void list::remove_if( Predicate pred );

Операция  remove_if() удаляет  все  элементы,  для  которых  выполняется  указанное

class Even {

public:

bool operator()( int elem ) { return ! (elem \% 2 ); }

};

условие, т.е. предикат pred возвращает true. Например:

ilist1.remove_if( Even() );

удаляет все четные числа из списка, определенного при рассмотрении merge().

12.6.4. Операция list::reverse()

void list::reverse();

 

Операция       reverse()          изменяет         порядок          следования     элементов      списка            на противоположный:

ilist1.reverse();

void list::sort();

template <class Compare>

12.6.5. Операция list::sort()

void list::sort( Compare comp );

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

list1.sort();

упорядочивает list1 по возрастанию, а

list1.sort( greater<int>() );

упорядочивает list1 по убыванию, используя оператор “больше”.

void list::splice( iterator pos, list rhs );

void list::splice( iterator pos, list rhs, iterator ix );

void list::splice( iterator pos, list rhs,

12.6.6. Операция list::splice()

iterator first, iterator last );

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

int array[ 10 ] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };

list< int > ilist1( array, array + 10 );

непосредственно перед ней. Если даны два списка:

list< int > ilist2( array, array + 2 );      // содержит 0, 1

то  следующее  обращение  к  splice() перемещает  первый  элемент  ilist1 в  ilist2.

Теперь ilist2 содержит элементы 0, 1 и 0, тогда как в ilist1 элемента 0 больше нет.

 

// ilist2.end() указывает на позицию, куда нужно переместить элемент

// элементы вставляются перед этой позицией

// ilist1 указывает на список, из которого перемещается элемент

// ilist1.begin() указывает на сам перемещаемый элемент

ilis2.splice( ilist2.end(), ilist1, ilist1.begin() );

В         следующем    примере          применения   splice()             передаются    два      итератора,

list< int >::iterator first, last;

first = ilist1.find( 2 );

last = ilist1.find( 13 );

ограничивающие диапазон перемещаемых элементов:

ilist2.splice( ilist2.begin(), ilist1, first, last );

В данном  случае элементы  2,  3,  5 и  8 удаляются  из ilist1 и  вставляются  в начало

ilist2. Теперь ilist1 содержит пять элементов 1, 1, 13, 21 и 34. Для их перемещения

list< int >::iterator pos = ilist2.find( 5 );

в ilist2 можно воспользоваться третьей вариацией операции splice():

ilist2.splice( pos, ilist1 );

Итак,  список  ilist1 пуст.  Последние  пять  элементов  перемещены  в  позицию  списка

ilist2, предшествующую той, которую занимает элемент 5.

void list::unique();

template <class BinaryPredicate>

12.6.7. Операция list::unique()

void list::unique( BinaryPredicate pred );

Операция   unique() удаляет   соседние   дубликаты.   По   умолчанию   при   сравнении используется  оператор  равенства,  определенный  для типа элементов  контейнера. Например,  если даны  значения  {0,2,4,6,4,2,0},  то после применения  unique() список останется таким же, поскольку в соседних позициях дубликатов нет. Но если мы сначала отсортируем список, что даст {0,0,2,2,4,4,6}, а потом применим unique(), то получим четыре различных значения {0,2,4,6}.

ilist.unique();

Вторая форма unique() принимает альтернативный оператор сравнения. Например,

 

class EvenPair {

public:

bool operator()( int val1, val2 )

{ return ! (val2 \% val1 );         }

};

ilist.unique( EvenPair() );

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

Эти операции, являющиеся членами класса, следует предпочесть соответствующим обобщенным алгоритмам при работе со списками. Остальные обобщенные алгоритмы, такие,  как  find(),  transform(),  for_each() и  т.д.,  работают  со  списками  так  же эффективно, как и с другими контейнерами (еще раз напомним, что подробно все алгоритмы рассматриваются в Приложении).

Упражнение 12.8

Измените программу из раздела 12.2, используя список вместо вектора.