<< Пред.           стр. 54 (из 121)           След. >>

Список литературы по разделу

 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;
 }
 Как правило, обобщенные алгоритмы поддерживают обе формы применения операции: как использование встроенного (или перегруженного) оператора, так и применение указателя на функцию либо объекта-функции.
 Есть три источника появления объектов-функций:
 из набора предопределенных арифметических, сравнительных и логических объектов-функций стандартной библиотеки;
 из набора предопределенных адаптеров функций, позволяющих специализировать или расширять предопределенные (или любые другие) объекты-функции;
 определенные нами собственные объекты-функции для передачи обобщенным алгоритмам. К ним можно применять и адаптеры функций.
 В этом разделе мы рассмотрим все три источника объектов-функций.
 12.3.1. Предопределенные объекты-функции
 Предопределенные объекты-функции подразделяются на арифметические, логические и сравнительные. Каждый объект – это шаблон класса, параметризованный типами операндов. Для использования любого из них необходимо включить заголовочный файл:
 #include
 Например, объект-функция, поддерживающий сложение, – это шаблон класса с именем plus. Для определения экземпляра, способного складывать два целых числа, нужно написать:
 #include
 plus< int > intAdd;
 Для выполнения операции сложения мы применяем перегруженный оператор вызова к intAdd точно так же, как и к классу AddImage в предыдущем разделе:
 int ival1 = 10, ival2 = 20;
 
 // эквивалентно int sum = ival1 + ival2;
 int sum = intAdd( ival1, ival2 );
 Реализация шаблона класса plus вызывает оператор сложения, ассоциированный с типом своего параметра – int. Этот и другие предопределенные объекты-функции применяются прежде всего в качестве аргументов обобщенных алгоритмов и обычно замещают подразумеваемую по умолчанию операцию. Например, по умолчанию алгоритм sort() располагает элементы контейнера в порядке возрастания с помощью оператора “меньше” базового типа. Для сортировки по убыванию мы передаем предопределенный шаблон класса greater, который вызывает оператор “больше”:
 vector< string > svec;
 // ...
 sort( svec.begin(), svec.end(), greater() );
 Предопределенные объекты-функции перечислены в следующих разделах и разбиты на категории: арифметические, логические и сравнительные. Применение каждого из них иллюстрируется как в качестве именованного, так и в качестве безымянного объекта, передаваемого функции. Мы пользуемся следующими определениями объектов, включая и определение простого класса (перегрузка операторов подробно рассматривается в главе 15):
 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;
 double dval1, dval2, dres;
 Кроме того, мы определяем два шаблона функций, которым передаем различные безымянные объекты-функции:
 template
  Type UnaryFunc( FuncObject fob, const Type &val )
  { return fob( val ); }
 
 template
  Type BinaryFunc( FuncObject fob,
  const Type &val1, const Type &val2 )
  { return fob( val1, val2 ); }
 12.3.2. Арифметические объекты-функции
 Предопределенные арифметические объекты-функции поддерживают операции сложения, вычитания, умножения, деления, взятия остатка и вычисления противоположного по знаку значения. Вызываемый оператор – это экземпляр, ассоциированный с типом Type. Если тип является классом, предоставляющим перегруженную реализацию оператора, то именно эта реализация и вызывается.
 Сложение: plus
 plus stringAdd;
 
 // вызывается string::operator+()
 sres = stringAdd( sval1, sval2 );
 dres = BinaryFunc( plus(), dval1, dval2 );
 Вычитание: minus
 minus intSub;
 ires = intSub( ival1, ival2 );
 dres = BinaryFunc( minus(), dval1, dval2 );
 Умножение: multiplies
 multiplies complexMultiplies;
 cres = complexMultiplies( cval1, cval2 );
 dres = BinaryFunc( multiplies(), dval1, dval2 );
 Деление: divides
 divides intDivides;
 ires = intDivides( ival1, ival2 );
 dres = BinaryFunc( divides(), dval1, dval2 );
 Взятие остатка: modulus
 modulus IntModulus;
 Ires = IntModulus( Ival1, Ival2 );
 ires = BinaryFunc( modulus(), ival1, ival2 );
 Вычисление противоположного значения: negate
 negate intNegate;
 ires = intNegate( ires );
 Ires = UnaryFunc( negate(), Ival1 );
 12.3.3. Сравнительные объекты-функции
 Сравнительные объекты-функции поддерживают операции равенства, неравенства, больше, больше или равно, меньше, меньше или равно.
 Равенство: equal_to
 equal_to stringEqual;
 sres = stringEqual( sval1, sval2 );
 ires = count_if( svec.begin(), svec.end(),
  equal_to(), sval1 );
 Неравенство: not_equal_to
 not_equal_to complexNotEqual;
 cres = complexNotEqual( cval1, cval2 );
 ires = count_if( svec.begin(), svec.end(),
  not_equal_to(), sval1 );
 Больше: greater
 greater intGreater;
 ires = intGreater( ival1, ival2 );
 ires = count_if( svec.begin(), svec.end(),
  greater(), sval1 );
 Больше или равно: greater_equal
 greater_equal doubleGreaterEqual;
 dres = doubleGreaterEqual( dval1, dval2 );
 ires = count_if( svec.begin(), svec.end(),
  greater_equal (), sval1 );
 Меньше: less
 less IntLess;
 Ires = IntLess( Ival1, Ival2 );
 ires = count_if( svec.begin(), svec.end(),
  less(), sval1 );
 Меньше или равно: less_equal
 less_equal intLessEqual;
 ires = intLessEqual( ival1, ival2 );
 ires = count_if( svec.begin(), svec.end(),
  less_equal(), sval1 );
 12.3.4. Логические объекты-функции
 Логические объекты-функции поддерживают операции “логическое И” (возвращает true, если оба операнда равны true, – применяет оператор &&, аcсоциированный с типом Type), “логическое ИЛИ” (возвращает true, если хотя бы один из операндов равен true, – применяет оператор ||, аcсоциированный с типом Type) и “логическое НЕ” (возвращает true, если операнд равен false, – применяет оператор !, аcсоциированный с типом Type)
 Логическое И: logical_and
 logical_and intAnd;
 ires = intLess( ival1, ival2 );
 dres = BinaryFunc( logical_and(), dval1, dval2 );
 Логическое ИЛИ: logical_or
 logical_or intSub;
 ires = intSub( ival1, ival2 );
 dres = BinaryFunc( logical_or(), dval1, dval2 );
 Логическое НЕ: logical_not
 logical_not IntNot;
 ires = IntNot( Ival1, Ival2 );
 dres = UnaryFunc( logical_or(), 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() следующее:
 count_if( vec.begin(), vec.end(),
  bind2nd( less_equal(), 10 ));
 В стандартной библиотеке также есть два предопределенных адаптера-отрицателя: not1 и not2. not1 инвертирует значение истинности унарного предиката, являющегося объектом-функцией, а not2 – значение бинарного предиката. Для отрицания рассмотренного выше связывателя объекта-функции less_equal можно написать следующее:
 count_if( vec.begin(), vec.end(),
  not1( bind2nd( less_equal(), 10 )));
 Другие примеры использования связывателей и отрицателей приведены в Приложении, вместе с примерами использования каждого алгоритма.
 12.3.6. Реализация объекта-функции
 При реализации программы в разделе 12.2 нам уже приходилось определять ряд объектов-функций. В этом разделе мы изучим необходимые шаги и возможные вариации при определении класса объекта-функции. (В главе 13 определение класса рассматривается детально; в главе 15 обсуждается перегрузка операторов.)
 В самой простой форме определение класса объекта-функции сводится к перегрузке оператора вызова. Вот, например, унарный объект-функция, определяющий, что некоторое значение меньше или равно 10:
 // простейшая форма класса объекта-функции
 class less_equal_ten {
 public:
  bool operator() ( int val )
  { return val <= 10; }
 };
 Теперь такой объект-функцию можно использовать точно так же, как предопределенный. Вызов алгоритма count_if() с помощью нашего объекта-функции выглядит следующим образом:
 count_if( vec.begin(), vec.end(), less_equal_ten() );
 Разумеется, возможности этого класса весьма ограничены. Попробуем применить отрицатель, чтобы подсчитать, сколько в контейнере элементов, больших 10:
 count_if( vec.begin(), vec.end(),
  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
 Используя предопределенные объекты-функции и адаптеры, создайте объекты-функции для решения следующих задач:
 Найти все значения, большие или равные 1024.
 Найти все строки, не равные "pooh".
 Умножить все значения на 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 будет возвращен неконстантный, а для vec1 – константный итератор:
 vector< int >::iterator iter0 = vec0.begin();
 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() можно исправить, написав:
 // правильно: теперь unique_copy() вставляет элементы с помощью
 // vres.push_back()...
 unique_copy( ivec.begin(), ivec.end(),
  back_inserter( vres ) );
 front_inserter() вызывает определенную для контейнера операцию вставки push_front() вместо оператора присваивания. Аргументом front_inserter() тоже является сам контейнер. Заметьте, однако, что класс vector не поддерживает push_front(), так что использовать такой адаптер для вектора нельзя:
 // увы, ошибка:
 // класс vector не поддерживает операцию push_front()
 // следует использовать контейнеры deque или list
 unique_copy( ivec.begin(), ivec.end(),
  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() и rend(). Есть константные и неконстантные версии обратных итераторов:
 vector< int > vec0;
 const vector< int > vec1;
 
 vector< int >::reverse_iterator r_iter0 = vec0.rbegin();
 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() пару обратных итераторов:
 // сортирует вектор в порядке возрастания
 sort( vec0.begin(), vec0.end() );
 
 // сортирует вектор в порядке убывания
 sort( vec0.rbegin(), vec0.rend() );
 12.4.3. Потоковые итераторы
 Стандартная библиотека предоставляет средства для работы потоковых итераторов чтения и записи совместно со стандартными контейнерами и обобщенными алгоритмами. Класс istream_iterator поддерживает итераторные операции с классом istream или одним из производных от него, например ifstream для работы с потоком ввода из файла. Аналогично ostream_iterator поддерживает итераторные операции с классом ostream или одним из производных от него, например ofstream для работы с потоком вывода в файл. Для использования любого из этих итераторов следует включить заголовочный файл
 #include
 В следующей программе мы пользуемся потоковым итератором чтения для получения из стандартного ввода последовательности целых чисел в вектор, а затем применяем потоковый итератор записи в качестве целевого в обобщенном алгоритме unique_copy():
 #include
 #include
 #include
 #include
 #include
 
 /*
  * вход:
  * 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 vec;
  copy ( input, end_of_stream, inserter( vec, vec.begin() ));
 
  sort( vec.begin(), vec.end(), greater() );
 
  ostream_iterator< int > output( cout, " " );
  unique_copy( vec.begin(), vec.end(), output );
 }
 12.4.4. Итератор istream_iterator
 В общем виде объявление потокового итератора чтения istream_iterator имеет форму:
 istream_iterator identifier( istream& );1.
 где Type – это любой встроенный или пользовательский тип класса, для которого определен оператор ввода. Аргументом конструктора может быть объект либо класса istream, например cin, либо производного от него класса с открытым типом наследования – ifstream:

<< Пред.           стр. 54 (из 121)           След. >>

Список литературы по разделу