Форум » C/C++ » Адаптация лямбда-выражений при их использовании в алгоритмах » Ответить
Адаптация лямбда-выражений при их использовании в алгоритмах
Сыроежка: Эту тему можно рассматривать как учебный материал по лямбда-выражениям. Рассмотрим простую задачу: подсчитать количество элементов в некоторой целочисленной последовательности, которые нацело делятся на заданное число. Такого рода задачи часто встречаются в качестве заданий для самостоятельного решения студентами при прохождении тем, посвященных циклам. Оставим в стороне решение задачи с помощью циклов и рассмотрим, как эта задача реализуется с помощью стандартных алгоритмов. Очевидно, что наилучшим образом для выполнения поставленный задачи подходит стандартный алгоритм std::count_if. Необходимо лишь написать соответствующий предикат, который будет использоваться в алгоритме для проверки делимости чисел заданной последовательности. Вот как мог бы выглядеть код такого решения, написанный в рамках средсттв языка С++ до принятия стандарта С++ 2011 (использовался компилятор MS VC++ 2010). [pre2] #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; }[/pre2] Если бы также потребовалось подсчитать число элементов последовательности, которые не делятся нацело на заданное число, то было бы целесообразно воспользоваться уже написанным предикатом, примения логическое отрицание к возвращаемому значению оператор-функцией этого предиката. В стандартной библиотеке уже есть такой функциональный адаптер, который принимает предикат и выполняет логическое отрицание возвращаемого значения оператор-функцией этого предиката. Таким адаптером является шаблонный класс std::unary_negate, который легко создать с помощью вспомогательной стандартной функции std::not1. Можно было бы записать вызов алгоритма std::count_if для новой задачи следующим образом [pre2]int n = std::count_if( a, a + sizeof( a ) / sizeof( *a ), std::not1( is_divisible_by( divisor ) ) );[/pre2] Однако компилятор сообщит об ощибке, когда дойдет до анализа этой строчки. Дело в том, что использование адаптирующего предиката std::unary_negate требует наличия в исходном предикате, который он логически инвертирует, определений типов argument_type и result_type. Поэтому исходный предикат is_divisible_by потребуется переписать следующим образом, добавив требуемые объявления: [pre2]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; };[/pre2] Тогда результирующий код будет выглядеть следующим образом: [pre2] #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; }[/pre2] Еще лучше было бы сделать предикат is_divisible_by производным от стандартного класса std::unary_function, который как раз и содержит необходимые объявления типов argument_type и result_type. Ниже показан окончательный вид кода решения расширенного задания раздельного подсчета чисел нацело делящихся на заданное число и не делящихся без остатка на это же число. [pre2] #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; }[/pre2] На самом деле для решения этого простого задания можно было бы вообще не писать самостоятельно собственный предикат, а воспользоваться уже предоставляемым стандартной библиотекой С++ предикатом std::modulus, оператор-функция которого возвращает остаток от деления двух чисел. Различие в коде будет состоять в том, что в первоначальном решении "вручную" написанный предикат возвращал логическое значение true, если остаток от деления равен нулю, тогда как стандартный прредикат std::modulus возвращает сам остаток, и чтобы проверить, что он равен нулю, нужно применить к нему логическое отрицание. Вот код с применением стандартного предиката std::modulus/. [pre2] #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; }[/pre2] Условие данного задания довольно простое, а потому удалось ограничиться использованием в коде стандартных предикатов. Однако в общем случае не всегда логическое условие, используемое в алгоритме, можно выразить через стандартные предикаты, и приходится самостоятельно разрабатывать свой класс предиката, как это было сделано ранее в приведенных примерах. Возникает естественный вопрос, а что может измениться в этом коде с учетом новых возможностей, предоставляемых стандартом С++ 2011? Первое, что сразу же напрашивается, это использование лямбда-выражения вместо написания предиката. Лямбда-выражение позволяет "приблизить" логику вычисления к месту ее использования. Сначала напишем код с применением лямбда-выражения для только подсчета чисел последовательности, которые нацело делятся на заданное число. [pre2] #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; }[/pre2] В этом примере сразу же бросается в глаза использование глобальных стандартных функций, задающих диапазон обрабатываемой последовательности, std::begin() и std::end(), вместо задания диапазона "вручную", а также применение лямбда-выражения. Эта программа успешно решает поставленную исходную задачу. А что если нужно также подсчитать число элементов последовательности, не делящихся нацело на заданнное число, как это было ранее? Казалось бы достаточно применить стандартный функциональный адаптер std::unary_negate с помощью заключения лямбда-выражения в круглые скобки в качестве аргумента вспомогательной стандартной функции std::not1 по аналогии с тем, когда использовались стандартный (std::modulus)или самостоятельно написаннный (is_divisible_by) предикаты. То есть напрашивается следующий вид вызова алгоритма std::count_if [pre2]n = std::count_if( std::begin( a ), std::end( a ), std::not1( [divisor]( int x ) { return ( x % divisor == 0 ); } ) );[/pre2] Однако, увы, этот код не будет компилироваться по той же самой причине, как и не компилировался пример с использованием класса is_divisible_by, в котором не были объявлены типы argument_type и result_type. Казалось бы никакой сложности не составит объявить эти типы и в лямбда-выражении, например, [pre2]auto is_divisible_by = [divisor]( int x ) -> bool { typedef int argument_type; typedef bool result_type; return ( x % divisor == 0 ); };[/pre2] и подставить это лямбда-выражение в качестве аргумента функции std::not1. Но компилятор снова не будет компилировать код и выдаст сообщение об ошибке, что не найден тип argument_type или result_type! Проблема заключается в том, что все, что в лямбда-выражении заключено в фигурные скобки, относится к телу оператор-функции этого лямбда-выражения. Поэтому все объявления, включенные в фигурные скобки, являются локальными по отношению к этой неявной оператор-функции и за ее пределами не видны. Получается безвыходная ситуация: нельзя напрямую применять функциональные адаптеры к лямбда-выражениям. На мой взгляд это упущение стандарта С++ 2011. Можно было бы принять в стандарте, что все typedef внутри лямбда-выражения относятся к самому лямбда-выражению, то есть к этому безымяннному классу. а не к его оператор-функции. Тогда вышеприведенное объявление лямбда-выражения можно было бы использовать со стандартными функциональными адаптерами. Что же делать? Выйти из тупиковой ситуации помогут новые, появившиеся в стандарте С++ 2011 функциональные адаптеры std::function. Просто объявляется объект этого класса, конструктору которого передается лямбда-выражение. А уже сам функциональный адаптер позаботится об объявлении требуемых типов argument_type и result_type. Вот как это будет выглядеть: [pre2]std::function<bool( int )> is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );[/pre2] Теперь можно написать окончательный код программы полного решения задания. [pre2] #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; }[/pre2] В качестве дополнительного материала по теме можно почитать статью по ссылке
Ответов - 1
Сыроежка: Из прочитанного может создаться ложное впечатление, что если нужно использовать логическое отрицание для предиката, заданного лямбда-выражением, то единственный путь - это сохранить лямбда-выражение в стандартном адаптере std::function, а лишь затем к полученному объекту применить стандартный адаптер std::unary_negate с помощью вызова вспомогательной функции std::not1. На самом деле это делать не обезательно. Этот способ демонстрировал общий подход к использованию лямбда-выражений вместе со стандартными адаптерами. Он в общем случае предпочтителен, так как делает код более понятным в силу того, что используются стандартные средства, знакомые каждому С++ программисту, имевшему дело со стандартными алгоритмами. Однако в частных случаях можно вполне обойтись без применения стандартных адаптеров, чтобы получить логическое отрицание заданного лямбда-выражения. Чтобы показать, как это делается, вернемся к коду последнего примера из предыдущего сообщения. [pre2]#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; }[/pre2] Этот пример можно переписать без использования адаптеров предикатов std::function и std::unary_negate, скрытым за вызовом функции std::not1. Ведь все, что требуется, это всего лишь нужно выполнить при втором вызове алгоритма std::count_if логическое отрицание исходного лямбда выражения. Естественно, что сам объект лямбда-выражения нужно будет сохранить в какой-нибудь переменной, чтобы затем ее использовать в выражении логического отрицания. Поэтому вместо объявления в вышеприведенном примере [pre2]std::function<bool( int )> is_divisible_by( [divisor]( int x ) { return ( x % divisor == 0 ); } );[/pre2] следует записать [pre2]auto is_divisible_by = [divisor]( int x ) { return ( x % divisor == 0 ); };[/pre2] Возникает вопрос, а как применить логическое отрицание к этому лямбда-выражению, сохраненному в переменной is_divisible_by? Очень просто, с помощью нового лямбда-выражения, которое применит оператор отрицания к уже определенному лямбда-выражению. Новое лямбда-выражение будет выглядеть следующим образом: [is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); } Теперь исходный пример можно переписать, исключив из него использование стандартных адаптеров std:;function и std::unary_negate (std::not1), ограничившись только применением лямбда-выражений. Соответственно заголовок <functional> можно также убрать из кода. [pre2]#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; }[/pre2] Итак, как видно, вполне можно обойтись одними лямбда-выражениями без использования стандартных функциональных адаптеров. В этом последнем примере имеет место вложенность лямбда-выражений друг в друга. Можно сделать пример более интересынм, если позволить в программе "на лету" менять значение переменной divisor, чтобы можно было запускать алгоритм std::count_if для различных значений делителя. Чтобы этого добиться, следует передать в лямбда-выражение объект divisor по ссылке, предварительно убрав его константность. Ниже показан пример, который в цикле подсчитывает число элементов последовательности, которые нацело делятся или не делятся на числа от 2 до 5 включительно. [pre2]#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; }[/pre2] В этом примере лямбда-выражение принимает переменную divisor по ссылке [pre2]auto is_divisible_by = [&divisor]( int x ) { return ( x % divisor == 0 ); };[/pre2] Поэтому изменение этой переменной в цикле [pre2]for ( divisor = 2; divisor < 6; divisor++ )[/pre2] будет также отражаться на вычислении оператора вызова функции лямбда-выражения. Второе лямбда-выражение при желании можно упростить, Вместо [pre2][is_divisible_by] ( int x ) { return ( !is_divisible_by( x ) ); }[/pre2] можно записать [pre2][=] ( int x ) { return ( !is_divisible_by( x ) ); }[/pre2] Эти два лямбда-выражения эквивалентны друг другу.
полная версия страницы