On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 28.07.12 19:44. Заголовок: Адаптация лямбда-выражений при их использовании в алгоритмах


Эту тему можно рассматривать как учебный материал по лямбда-выражениям.

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

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

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

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

Вот как мог бы выглядеть код такого решения, написанный в рамках средсттв языка С++ до принятия стандарта С++ 2011 (использовался компилятор MS VC++ 2010).

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

class is_divisible_by
{
public:
is_divisible_by( int n ) : n( n ) {}
bool operator ()( int x ) const { return ( x % n == 0 ); }
private:
const int n;
};

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;


int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), is_divisible_by( divisor ) );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

return 0;
}


Если бы также потребовалось подсчитать число элементов последовательности, которые не делятся нацело на заданное число, то было бы целесообразно воспользоваться уже написанным предикатом, примения логическое отрицание к возвращаемому значению оператор-функцией этого предиката.
В стандартной библиотеке уже есть такой функциональный адаптер, который принимает предикат и выполняет логическое отрицание возвращаемого значения оператор-функцией этого предиката. Таким адаптером является шаблонный класс std::unary_negate, который легко создать с помощью вспомогательной стандартной функции std::not1.

Можно было бы записать вызов алгоритма std::count_if для новой задачи следующим образом

int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), std::not1( is_divisible_by( divisor ) ) );


Однако компилятор сообщит об ощибке, когда дойдет до анализа этой строчки. Дело в том, что использование адаптирующего предиката std::unary_negate требует наличия в исходном предикате, который он логически инвертирует, определений типов argument_type и result_type. Поэтому исходный предикат is_divisible_by потребуется переписать следующим образом, добавив требуемые объявления:

class is_divisible_by 
{
public:
typedef bool result_type;
typedef int argument_type;
is_divisible_by( int n ) : n( n ) {}
bool operator ()( int x ) const { return ( x % n == 0 ); }
private:
const int n;
};


Тогда результирующий код будет выглядеть следующим образом:

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

class is_divisible_by
{
public:
typedef bool result_type;
typedef int argument_type;
is_divisible_by( int n ) : n( n ) {}
bool operator ()( int x ) const { return ( x % n == 0 ); }
private:
const int n;
};

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;


int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), is_divisible_by( divisor ) );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), std::not1( is_divisible_by( divisor ) ) );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


Еще лучше было бы сделать предикат is_divisible_by производным от стандартного класса std::unary_function, который как раз и содержит необходимые объявления типов argument_type и result_type.

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

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

class is_divisible_by :public std::unary_function<int, bool>
{
public:
is_divisible_by( int n ) : n( n ) {}
bool operator ()( int i ) const { return i % n == 0; }
private:
const int n;
};

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;


int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), is_divisible_by( divisor ) );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), std::not1( is_divisible_by( divisor ) ) );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


На самом деле для решения этого простого задания можно было бы вообще не писать самостоятельно собственный предикат, а воспользоваться уже предоставляемым стандартной библиотекой С++ предикатом std::modulus, оператор-функция которого возвращает остаток от деления двух чисел. Различие в коде будет состоять в том, что в первоначальном решении "вручную" написанный предикат возвращал логическое значение true, если остаток от деления равен нулю, тогда как стандартный прредикат std::modulus возвращает сам остаток, и чтобы проверить, что он равен нулю, нужно применить к нему логическое отрицание.

Вот код с применением стандартного предиката std::modulus/.

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;


int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ),
std::not1( std::bind2nd( std::modulus<int>(), divisor ) ) );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), std::bind2nd( std::modulus<int>(), divisor ) );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


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

Возникает естественный вопрос, а что может измениться в этом коде с учетом новых возможностей, предоставляемых стандартом С++ 2011?

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

Сначала напишем код с применением лямбда-выражения для только подсчета чисел последовательности, которые нацело делятся на заданное число.

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;


auto n = std::count_if( std::begin( a ), std::end( a ),
[divisor]( int x ) { return ( x % divisor == 0 ); } );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

return 0;
}


В этом примере сразу же бросается в глаза использование глобальных стандартных функций, задающих диапазон обрабатываемой последовательности, std::begin() и std::end(), вместо задания диапазона "вручную", а также применение лямбда-выражения.

Эта программа успешно решает поставленную исходную задачу.

А что если нужно также подсчитать число элементов последовательности, не делящихся нацело на заданнное число, как это было ранее?
Казалось бы достаточно применить стандартный функциональный адаптер std::unary_negate с помощью заключения лямбда-выражения в круглые скобки в качестве аргумента вспомогательной стандартной функции std::not1 по аналогии с тем, когда использовались стандартный (std::modulus)или самостоятельно написаннный (is_divisible_by) предикаты. То есть напрашивается следующий вид вызова алгоритма std::count_if

n = std::count_if( std::begin( a ), std::end( a ), 
std::not1( [divisor]( int x ) { return ( x % divisor == 0 ); } ) );


Однако, увы, этот код не будет компилироваться по той же самой причине, как и не компилировался пример с использованием класса is_divisible_by, в котором не были объявлены типы argument_type и result_type. Казалось бы никакой сложности не составит объявить эти типы и в лямбда-выражении, например,

auto is_divisible_by = [divisor]( int x ) -> bool 
{
typedef int argument_type;
typedef bool result_type;
return ( x % divisor == 0 );
};


и подставить это лямбда-выражение в качестве аргумента функции std::not1.
Но компилятор снова не будет компилировать код и выдаст сообщение об ошибке, что не найден тип argument_type или result_type!
Проблема заключается в том, что все, что в лямбда-выражении заключено в фигурные скобки, относится к телу оператор-функции этого лямбда-выражения. Поэтому все объявления, включенные в фигурные скобки, являются локальными по отношению к этой неявной оператор-функции и за ее пределами не видны.

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

Что же делать? Выйти из тупиковой ситуации помогут новые, появившиеся в стандарте С++ 2011 функциональные адаптеры std::function. Просто объявляется объект этого класса, конструктору которого передается лямбда-выражение. А уже сам функциональный адаптер позаботится об объявлении требуемых типов argument_type и result_type. Вот как это будет выглядеть:

std::function<bool( int )> 
is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );


Теперь можно написать окончательный код программы полного решения задания.

 #include "stdafx.h" 
#include <iostream>
#include <algorithm>
#include <functional>

int _tmain(int argc, _TCHAR* argv[])
{

int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;
std::function<bool( int )>
is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );

auto n = std::count_if( std::begin( a ), std::end( a ), is_divisible_by );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( std::begin( a ), std::end( a ), std::not1( is_divisible_by ) );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


В качестве дополнительного материала по теме можно почитать статью по ссылке

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 1 [только новые]





ссылка на сообщение  Отправлено: 28.07.12 19:45. Заголовок: Из прочитанного може..


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

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

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

#include "stdafx.h"   
#include <iostream>
#include <algorithm>
#include <functional>

int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;
std::function<bool( int )>
is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );

auto n = std::count_if( std::begin( a ), std::end( a ), is_divisible_by );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( std::begin( a ), std::end( a ), std::not1( is_divisible_by ) );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


Этот пример можно переписать без использования адаптеров предикатов std::function и std::unary_negate, скрытым за вызовом функции std::not1. Ведь все, что требуется, это всего лишь нужно выполнить при втором вызове алгоритма std::count_if логическое отрицание исходного лямбда выражения.

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

std::function<bool( int )> 
is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );


следует записать

auto is_divisible_by = [divisor]( int x ) { return ( x % divisor == 0 ); };


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

[is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); }

Теперь исходный пример можно переписать, исключив из него использование стандартных адаптеров std:;function и std::unary_negate (std::not1), ограничившись только применением лямбда-выражений. Соответственно заголовок <functional> можно также убрать из кода.

#include "stdafx.h"   
#include <iostream>
#include <algorithm>

int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const int divisor = 3;
auto is_divisible_by = [divisor]( int x ) { return ( x % divisor == 0 ); };

auto n = std::count_if( std::begin( a ), std::end( a ), is_divisible_by );

std::cout << "There are " << n << " numbers divisible by " << divisor << "\n";

n = std::count_if( std::begin( a ), std::end( a ),
[is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); } );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";

return 0;
}


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

Можно сделать пример более интересынм, если позволить в программе "на лету" менять значение переменной divisor, чтобы можно было запускать алгоритм std::count_if для различных значений делителя. Чтобы этого добиться, следует передать в лямбда-выражение объект divisor по ссылке, предварительно убрав его константность.

Ниже показан пример, который в цикле подсчитывает число элементов последовательности, которые нацело делятся или не делятся на числа от 2 до 5 включительно.

#include "stdafx.h"   
#include <iostream>
#include <algorithm>

int _tmain(int argc, _TCHAR* argv[])
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int divisor;
auto is_divisible_by = [&divisor]( int x ) { return ( x % divisor == 0 ); };

for ( divisor = 2; divisor < 6; divisor++ )
{
auto n = std::count_if( std::begin( a ), std::end( a ), is_divisible_by );

std::cout << "\nThere are " << n << " numbers divisible by " << divisor << "\n";


n = std::count_if( std::begin( a ), std::end( a ),
[is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); } );

std::cout << "and " << n << " numbers not divisible by " << divisor << "\n";
}

return 0;
}


В этом примере лямбда-выражение принимает переменную divisor по ссылке

auto is_divisible_by = [&divisor]( int x ) { return ( x % divisor == 0 ); };


Поэтому изменение этой переменной в цикле

for ( divisor = 2; divisor < 6; divisor++ )


будет также отражаться на вычислении оператора вызова функции лямбда-выражения.

Второе лямбда-выражение при желании можно упростить, Вместо
[is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); }

можно записать
[=] ( int x ) { return ( !is_divisible_by( x ) ); }

Эти два лямбда-выражения эквивалентны друг другу.

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 4
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет