Язык программирования C++. Вводный курс

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


Допустим, мы задумали написать книжку для детей и хотим понять, какой словарный состав наиболее подходит для такой цели. Чтобы ответить на этот вопрос, нужно прочитать несколько детских книг, сохранить текст в отдельных векторах строк (см. раздел 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. Этот объект чуть сложнее, так как позволяет пользователю задать размер, с которым производится сравнение. Мы сохраняем размер в члене класса и инициализируем его с помощью конструктора (по умолчанию – значением 6):



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

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



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() применяет указатель на функцию или объект-функцию к каждому элементу контейнера из диапазона, ограниченного парой итераторов. В нашем случае объект-функция PrintElem копирует один элемент в стандартный вывод:



class PrintElem {

public:

   PrintElem( int lineLen = 8 )

      : _line_length( lineLen ), _cnt( 0 )

   {}

   void operator()( const string &elem )

   {

      ++_cnt;

      if ( _cnt % _line_length == 0 )

         { cout << '\n'; }

      cout << elem << " ";

   }

private:

   int _line_length;

   int _cnt;
<


};



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 << '\n'; }

      cout << elem << " ";

   }

private:

   int _line_length;

   int _cnt;
};



class LessThan {

public:

   bool operator()( const string & s1,

                   const string & s2 )

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

};

typedef vector<string, allocator> textwords;

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

{

   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 << "\n\n";   // разделить части выведенного текста

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

   vector<string, allocator>::iterator it;

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

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

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

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

   cout << "\n\n";

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

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

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

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

   cout << "\n\n";

   // подсчитать число строк, длина которых больше 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 << "\n\n";

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

}

// difference_type - это тип, с помощью которого можно хранить результат

// вычитания двух итераторов одного и того же контейнера

// - в данном случае вектора строк ...

// обычно это предполагается по умолчанию

typedef vector<string,allocator>::difference_type diff_type;

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

#include <fstream.h>

main()

{

     vector<textwords, allocator> sample;

     vector<string,allocator> t1, t2;

     string t1fn, t2fn;

           // запросить у пользователя имена входных файлов ...

           // в реальной программе надо бы выполнить проверку

     cout << "text file #1: "; cin >> t1fn;

     cout << "text file #2: "; cin >> t2fn;

           // открыть файлы

     ifstream infile1( t1fn.c_str());

     ifstream infile2( t2fn.c_str());

           // специальная форма итератора

           // обычно diff_type подразумевается по умолчанию ...

     istream_iterator< string, diff_type > input_set1( infile1 ), eos;

     istream_iterator< string, diff_type > input_set2( infile2 );

           // специальная форма итератора

     copy( input_set1, eos, back_inserter( t1 ));

     copy( input_set2, eos, back_inserter( t2 ));

     sample.push_back( t1 ); sample.push_back( t2 );

     process_vocab( &sample );

<


}

Упражнение 12.2

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

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

Упражнение 12.3

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


Содержание раздела