Язык программирования C++. Вводный курс. С для начинающих
Скачать 5.41 Mb.
|
552 } Этот фрагмент программы выводит такую строку: Number of words greater than length six are 22 Алгоритм remove() ведет себя аналогично unique(): он тоже не изменяет размер контейнера, а просто разделяет элементы на те, что следует оставить (копируя их по очереди в начало контейнера), и те, что следует удалить (перемещая их в конец контейнера). Вот как можно воспользоваться им для исключения из коллекции слов, которые мы не хотим сохранять: } Результат применения remove(): 1 instances removed: and 0 instances removed: if 0 instances removed: or 1 instances removed: but 1 instances removed: the void process_vocab( vector { // ... // подсчитать число строк, длина которых больше 6 int cnt = count_if( texts.begin(), texts.end(), GreaterThan() ); cout << "Number of words greater than length six are " << cnt << endl; // ... void process_vocab( vector { // ... 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() ); } // ... С++ для начинающих 553 Теперь нам нужно распечатать содержимое вектора. Можно обойти все элементы и вывести каждый по очереди, но, поскольку при этом обобщенные алгоритмы не используются, мы считаем такое решение неподходящим. Вместо этого проиллюстрируем работу алгоритма for_each() для вывода всех элементов вектора. for_each() применяет указатель на функцию или объект-функцию к каждому элементу контейнера из диапазона, ограниченного парой итераторов. В нашем случае объект-функция PrintElem копирует один элемент в стандартный вывод: }; } Вот и все. Мы получили законченную программу, для чего пришлось лишь последовательно записать обращения к нескольким обобщенным алгоритмам. Для удобства мы приводим ниже полный листинг вместе с функцией main() для ее тестирования (здесь используются специальные типы итераторов, которые будут обсуждаться только в разделе 12.4). Мы привели текст реально исполнявшегося кода, который не полностью удовлетворяет стандарту C++. В частности, в нашем распоряжении были лишь устаревшие реализации алгоритмов count() и count_if(), которые не возвращают результат, а требуют передачи дополнительного аргумента для вычисленного значения. Кроме того, библиотека iostream отражает предшествующую принятию стандарта реализацию, в которой требуется заголовочный файл iostream.h. 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 { // ... for_each( texts.begin(), texts.end(), PrintElem() ); С++ для начинающих 554 }; #include #include #include #include // предшествующий принятию стандарта синтаксис #include 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; С++ для начинающих 555 public: bool operator()( const string & s1, const string & s2 ) { return s1.size() < s2.size(); } }; typedef vector { if ( ! pvec ) { // вывести предупредительное сообщение return; } vector< string, allocator > texts; vector // отсортировать вектор texts sort( texts.begin(), texts.end() ); // теперь посмотрим, что получилось for_each( texts.begin(), texts.end(), PrintElem() ); cout << "\n\n"; // разделить части выведенного текста // удалить дубликаты vector // посмотрим, что осталось 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 { 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() ); } С++ для начинающих 556 } Упражнение 12.2 Длина слова – не единственная и, вероятно, не лучшая мера трудности текста. Другой возможный критерий – это длина предложения. Напишите программу, которая читает текст из файла либо со стандартного ввода, строит вектор строк для каждого предложения и передает его алгоритму count(). Выведите предложения в порядке сложности. Любопытный способ сделать это – сохранить каждое предложение как одну большую строку во втором векторе строк, а затем передать этот вектор алгоритму sort() вместе с объектом-функцией, который считает, что чем строка короче, тем она меньше. (Более подробно с описанием конкретного обобщенного алгоритма, а также с иллюстрацией его применения вы может ознакомиться в Приложении, где все алгоритмы перечислены в алфавитном порядке.) Упражнение 12.3 Более надежную оценку уровня трудности текста дает анализ структурной сложности предложений. Пусть каждой запятой присваивается 1 балл, каждому двоеточию или точке с запятой – 2 балла, а каждому тире – 3 балла. Модифицируйте программу из упражнения 12.2 так, чтобы она подсчитывала сложность каждого предложения. Воспользуйтесь алгоритмом count_if() для нахождения каждого из знаков препинания в векторе предложений. Выведите предложения в порядке сложности. 12.3. Объекты-функции Наша функция min() дает хороший пример как возможностей, так и ограничений механизма шаблонов: } Достоинство этого механизма – возможность определить единственный шаблон min(), который конкретизируется для бесконечного множества типов. Ограничение же заключается в том, что даже при такой конкретизации min() будет работать не со всеми. Это ограничение вызвано использованием оператора “меньше”: в некоторых случаях базовый тип его не поддерживает. Так, класс изображения Image может и не предоставлять реализации такого оператора, но мы об этом не знаем и пытаемся найти минимальный кадр анимации в данном массиве изображений. Однако попытка конкретизировать min() для такого массива приведет к ошибке компиляции: error: invalid types applied to the < operator: Image < Image ( ошибка: оператор < применен к некорректным типам: Image < Image) template { Type minval = p[ 0 ]; for ( int ix = 1; ix < size; ++ix ) if ( p[ ix ] < minval ) minval = p[ ix ]; return minval; С++ для начинающих 557 Возможна и другая ситуация: оператор “меньше” существует, но имеет неподходящую семантику. Например, если мы хотим найти наименьшую строку, но при этом принимать во внимание только буквы, не учитывая регистр, то такой реализованный в классе оператор не даст нужного результата. Традиционное решение состоит в том, чтобы параметризовать оператор сравнения. В данном случае это можно сделать, объявив указатель на функцию, принимающую два аргумента и возвращающую значение типа bool: } Такое решение вместе с нашей первой реализацией на основе встроенного оператора “меньше” обеспечивает универсальную поддержку для любого типа, включая и класс Image , если только мы придумаем подходящую семантику для сравнения двух изображений. Основной недостаток указателя на функцию связан с низкой эффективностью, так как косвенный вызов не дает воспользоваться преимуществами встроенных функций. Альтернативная стратегия параметризации заключается в применении объекта-функции вместо указателя (примеры мы видели в предыдущем разделе). Объект-функция – это класс, перегружающий оператор вызова (operator()). Такой оператор инкапсулирует семантику обычного вызова функции. Объект-функция, как правило, передается обобщенному алгоритму в качестве аргумента, хотя можно определять и независимые объекты-функции. Например, если бы был определен объект-функция AddImages, который принимает два изображения, объединяет их некоторым образом и возвращает новое изображение, то мы могли бы объявить его следующим образом: AddImages AI; Чтобы объект-функция удовлетворял нашим требованиям, мы применяем оператор вызова, предоставляя необходимые операнды в виде объектов класса Image: Image new_image = AI (im1, im2 ); У объекта-функции есть два преимущества по сравнению с указателем на функцию. Во- первых, если перегруженный оператор вызова – это встроенная функция, то компилятор может выполнить ее подстановку, обеспечивая значительный выигрыш в производительности. Во-вторых, объект-функция способен содержать произвольное 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; Image im1("foreground.tiff"), im2("background.tiff"); // ... // вызывает Image AddImages::operator()(const Image1&, const Image2&); С++ для начинающих 558 количество дополнительных данных, например кэш или информацию, полезную для выполнения текущей операции. Ниже приведена измененная реализация шаблона min() (отметим, что это объявление допускает также и передачу указателя на функцию, но без проверки прототипа): } Как правило, обобщенные алгоритмы поддерживают обе формы применения операции: как использование встроенного (или перегруженного) оператора, так и применение указателя на функцию либо объекта-функции. Есть три источника появления объектов-функций: 1. из набора предопределенных арифметических, сравнительных и логических объектов-функций стандартной библиотеки; 2. из набора предопределенных адаптеров функций, позволяющих специализировать или расширять предопределенные (или любые другие) объекты-функции; 3. определенные нами собственные объекты-функции для передачи обобщенным алгоритмам. К ним можно применять и адаптеры функций. В этом разделе мы рассмотрим все три источника объектов-функций. 12.3.1. Предопределенные объекты-функции Предопределенные объекты-функции подразделяются на арифметические, логические и сравнительные. Каждый объект – это шаблон класса, параметризованный типами операндов. Для использования любого из них необходимо включить заголовочный файл: #include Например, объект-функция, поддерживающий сложение, – это шаблон класса с именем plus . Для определения экземпляра, способного складывать два целых числа, нужно написать: plus< int > intAdd; Для выполнения операции сложения мы применяем перегруженный оператор вызова к intAdd точно так же, как и к классу AddImage в предыдущем разделе: 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; #include С++ для начинающих 559 int sum = intAdd( ival1, ival2 ); Реализация шаблона класса plus вызывает оператор сложения, ассоциированный с типом своего параметра – int. Этот и другие предопределенные объекты-функции применяются прежде всего в качестве аргументов обобщенных алгоритмов и обычно замещают подразумеваемую по умолчанию операцию. Например, по умолчанию алгоритм sort() располагает элементы контейнера в порядке возрастания с помощью оператора “меньше” базового типа. Для сортировки по убыванию мы передаем предопределенный шаблон класса greater, который вызывает оператор “больше”: sort( svec.begin(), svec.end(), greater Предопределенные объекты-функции перечислены в следующих разделах и разбиты на категории: арифметические, логические и сравнительные. Применение каждого из них иллюстрируется как в качестве именованного, так и в качестве безымянного объекта, передаваемого функции. Мы пользуемся следующими определениями объектов, включая и определение простого класса (перегрузка операторов подробно рассматривается в главе 15): double dval1, dval2, dres; Кроме того, мы определяем два шаблона функций, которым передаем различные безымянные объекты-функции: int ival1 = 10, ival2 = 20; // эквивалентно int sum = ival1 + ival2; vector< string > svec; // ... 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; С++ для начинающих 560 { return fob( val1, val2 ); } 12.3.2. Арифметические объекты-функции Предопределенные арифметические объекты-функции поддерживают операции сложения, вычитания, умножения, деления, взятия остатка и вычисления противоположного по знаку значения. Вызываемый оператор – это экземпляр, ассоциированный с типом Type. Если тип является классом, предоставляющим перегруженную реализацию оператора, то именно эта реализация и вызывается. • Сложение: plus • Вычитание: minus • Умножение: multiplies • Деление: divides • Взятие остатка: modulus Type UnaryFunc( FuncObject fob, const Type &val ) { return fob( val ); } template Type BinaryFunc( FuncObject fob, const Type &val1, const Type &val2 ) plus // вызывается string::operator+() sres = stringAdd( sval1, sval2 ); minus С++ для начинающих 561 ires = BinaryFunc( modulus • Вычисление противоположного значения: negate Ires = UnaryFunc( negate 12.3.3. Сравнительные объекты-функции Сравнительные объекты-функции поддерживают операции равенства, неравенства, больше, больше или равно, меньше, меньше или равно. • Равенство: equal_to • Неравенство: not_equal_to • Больше: greater • Больше или равно: greater_equal Ires = IntModulus( Ival1, Ival2 ); negate С++ для начинающих 562 greater_equal • Меньше: less • Меньше или равно: less_equal 12.3.4. Логические объекты-функции Логические объекты-функции поддерживают операции “логическое И” (возвращает true, если оба операнда равны true, – применяет оператор &&, аcсоциированный с типом Type ), “логическое ИЛИ” (возвращает true, если хотя бы один из операндов равен true , – применяет оператор ||, аcсоциированный с типом Type) и “логическое НЕ” (возвращает true, если операнд равен false, – применяет оператор !, аcсоциированный с типом Type) • Логическое И: logical_and • Логическое ИЛИ: logical_or • Логическое НЕ: logical_not Ires = IntLess( Ival1, Ival2 ); ires = count_if( svec.begin(), svec.end(), less_equal |