一. 什么是Lambda JK/gq}c
所谓Lambda,简单的说就是快速的小函数生成。 ppP0W`p
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, yrF"`/zv6|
SSAf<44e
^H(,^cVN
^vY[d]R _\
class filler +%~/~1
{ 61 @;3yV
public : pBxyq"z
void operator ()( bool & i) const {i = true ;} W5^<4Ya!
} ; ${F4x "x
+F4SU(T
q` 0wG3
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: 4Zn" K}q
.N>Th/K8
,J4rKGG
W\pO`FL
for_each(v.begin(), v.end(), _1 = true ); m<e_Z~ ^G
~PtIq.BY
@2;/-,4O
那么下面,就让我们来实现一个lambda库。 fP KFU
bzWWW^kNL
%B~@wcI)W
~-tKMc).X
二. 战前分析 lDX\"Fq
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 _/5#A+ ?
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 SjL&\),
?/1Eu47
K(3_1*e
for_each(v.begin(), v.end(), _1 = 1 ); )j+G4
/* --------------------------------------------- */ 8W2oGL6
vector < int *> vp( 10 ); /wX5>^
transform(v.begin(), v.end(), vp.begin(), & _1); Rn_FYP
/* --------------------------------------------- */ BW x=Q
sort(vp.begin(), vp.end(), * _1 > * _2); 6%B)
/* --------------------------------------------- */ ):-Ub4A\
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); *A([1l&]i
/* --------------------------------------------- */ wj2z?0}o
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); (Zoopkxw
/* --------------------------------------------- */ P;U(2;9 N
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); )Y &RMYy
I /z`)
GO]5~4k
5Ly Wg2
看了之后,我们可以思考一些问题: v+vM:At4
1._1, _2是什么? ku5vaP(
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 sKwUY{u\M
2._1 = 1是在做什么? [:(hqi!
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 T&nIH[}v
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 ".7\>8A#a
8)ykXx/f@
mlO\wn-F
三. 动工 ?`/DFI'_G
首先实现一个能够范型的进行赋值的函数对象类: WyU\,"
%PlA9@:IZ
[T(`+
#f
O8k+R@
template < typename T > FaLc*CU
class assignment s4[PwD
{ A&S n^mw
T value; yi;pn Z
public : *6aIDFNl
assignment( const T & v) : value(v) {} \P;2s<6i\
template < typename T2 > jdX*
T2 & operator ()(T2 & rhs) const { return rhs = value; } )wNcz~
Y
} ; aP[oLk$'Z
K"jS,a?s 6
Z</57w#-7
其中operator()被声明为模版函数以支持不同类型之间的赋值。 wE3fKG.
然后我们就可以书写_1的类来返回assignment LUzn7FZk
2GxkOch
*t300`x
0=k
class holder 1\Z/}FT
{ E1D0un
public : /8wfI_P>M"
template < typename T > X$*]$Ge>
assignment < T > operator = ( const T & t) const K/0Wp %
{ L./{^)
return assignment < T > (t); ML.|\:r*
} ]P>c{
} ; 0{(5J,/BF
oTg
'N
k] A(nr
由于该类是一个空类,因此我们可以在其后放心大胆的写上: l\WN
a"D'QqtH
static holder _1; T|-llhJ8
Ok,现在一个最简单的lambda就完工了。你可以写 >BZ,g!N,J}
}`y%*--
for_each(v.begin(), v.end(), _1 = 1 ); xEg@Y"NQ
而不用手动写一个函数对象。 k\X yR4r
8RT<?I^5
Gdz*
p$}/~5b}4
四. 问题分析 zvn3i5z
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 l:~/%=
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 jAdZS\?w
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 9t!Agxm
3, 我们没有设计好如何处理多个参数的functor。 !j/54,
下面我们可以对这几个问题进行分析。 -TS5g1
LKBh{X0%(
五. 问题1:一致性 mNOxe
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| uann'ho?q
很明显,_1的operator()仅仅应该返回传进来的参数本身。 4BZ7R,m#.
[r1dgwh8
struct holder c8Nl$|B
{ Nw '$r
// Q^8/"aV\
template < typename T > 8@/MrEOW#
T & operator ()( const T & r) const FXul
u6"SX
{ Fl!D2jnN
return (T & )r; &88c@Ksn
} 2U3e!V
} ; eV"s5X[$
(}rBnD
这样的话assignment也必须相应改动: Sd/7#
vxS4YR b
template < typename Left, typename Right > 2({|LQqk
class assignment P#}vi$dZ
{ [#(',~lN7
Left l; rv c%[HfW;
Right r; 1DlXsup&?#
public : =7[}:haB{
assignment( const Left & l, const Right & r) : l(l), r(r) {} 2BiFP||
template < typename T2 > S`Z[MNY
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } NA$%Up
} ; ipE|)Ns
rX0 ?m:&m
同时,holder的operator=也需要改动: R'pfA
B|!
M+I9k;N6&
template < typename T > ,/&|:PkS
assignment < holder, T > operator = ( const T & t) const JNo[<SZb
{ ^<_rE- k
return assignment < holder, T > ( * this , t); CjEzsjqe<I
} ' g d=\gV
UOyM=#ipY
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 J%lrXm(l{
你可能也注意到,常数和functor地位也不平等。 ^r,0aNzAs
97/ 4J
return l(rhs) = r; EQQ@nW{;
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 xd\ml
37~
那么我们仿造holder的做法实现一个常数类: L)qUBp@MW
J50n
E~
template < typename Tp > {<1uV']x
class constant_t E;,__
{ z4(`>z2a
const Tp t; S$gLL kD1
public : -hq^';,
constant_t( const Tp & t) : t(t) {} 7yjun|Lt}X
template < typename T > Sk-Q 4D^
const Tp & operator ()( const T & r) const 3Kc9*]D
{ y\,,hs
return t; ~NB|BwAh
} CM7NdK?I
} ; \58bz<u"
U "r)C;5
该functor的operator()无视参数,直接返回内部所存储的常数。 i(;.Y
下面就可以修改holder的operator=了 6uTC2ka[&R
%`~+^{Wp
template < typename T > rGrR;
assignment < holder, constant_t < T > > operator = ( const T & t) const G9Noch9
g
{ 4 Dy1M}7
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); @R<z=n"
} W.%p{wB|
8llXpe
同时也要修改assignment的operator() NwdrJw9
>I-rsw2
template < typename T2 > &3J^z7kU
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } {jv+ JL"5
现在代码看起来就很一致了。 ohs`[U=%~
B`||4*
六. 问题2:链式操作 ox_DEg7l
现在让我们来看看如何处理链式操作。 R"l6|9tmP
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 B_D0yhh
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 zeq")A
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 @n=&muC}
现在我们在assignment内部声明一个nested-struct vvs2:87zvJ
6=qC/1,l
template < typename T > X{(?p=]
struct result_1 MPK rr
{ YQyI{
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; `,]_r4~ ~
} ; K#'$_0.
^IyYck'y+
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: u'k+t`V&
[ LQOP3f
template < typename T > vz|(KN[
struct ref ]O{i?tyX
{ =qbN?a/?2
typedef T & reference; VFMn"bYOB
} ; 'p78^4'PL
template < typename T > )Gk?x$pY@
struct ref < T &> vexF|'!}0#
{ q[+h ~)
typedef T & reference; G
B,O
} ; NEPK
D>;_R
HK
有了result_1之后,就可以把operator()改写一下: "shX~zd5
WnOvU<Z
<
template < typename T > 'Z:wEt!
typename result_1 < T > ::result operator ()( const T & t) const KFRf5^ %
{ J"@X>n
return l(t) = r(t); {$5g29
} rA^=;?7Q
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。
?6>*mdpl
同理我们可以给constant_t和holder加上这个result_1。 4q:8<*W=
J}+N\V~
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 G9V2(P
_1 / 3 + 5会出现的构造方式是: ?3qp?ea
_1 / 3调用holder的operator/ 返回一个divide的对象 UbGnU_}
+5 调用divide的对象返回一个add对象。 XR3 dG:
最后的布局是: >I<}:=
Add ]N;nq
/ \ mq:WBSsV
Divide 5 US=K}B=g
/ \ K:kb&W
_1 3 p_%,JD
似乎一切都解决了?不。 SAj#+_db
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 cNFHbMd
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 B2* 7H
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: Ke3~o"IQ
WPrBK{B`o
template < typename Right > E:k]Z
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const e igVT4
Right & rt) const ^*+M9e9Z
{ z@o6[g/*Q
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); -T i<H9OV
} xWqV~NnE
下面对该代码的一些细节方面作一些解释 :475FPy]
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 <}h<By)
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 tN_=&|{WE4
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 tIV{uVM[|D
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 =tY%`e
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? lkly2|wA
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: BlZB8KI~
~c]
q:pU2
template < class Action > jIwN,H1$-
class picker : public Action _Pa@%/
{ tw=A]
a*
public : k.2GIc:5
picker( const Action & act) : Action(act) {} 9;uH}j8sE
// all the operator overloaded ),y`Iw
} ; m#G,m
ssS"X@VZ
\
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 BOR$R}q
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: -;ra(L`
[s\8@5?E
template < typename Right > c0HPS9N\
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const tC oE4Ed
{ p&u\gSo
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); =cb!2%?}
} wq,&0P-v
7cWeB5e?O
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > [i.c;'Wy/
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 W`c$2KS?DO
N 3O!8A_
template < typename T > struct picker_maker _?y3&4N)
{ \ltS~EuWU
typedef picker < constant_t < T > > result; xLLTp7b(
} ; 'p\&Mc_Gu
template < typename T > struct picker_maker < picker < T > > Cg%Owe/E?0
{ ki }Li*)7
typedef picker < T > result; Y~Vc|zM^(
} ; |pbetA4&
_(~LXk^C
下面总的结构就有了: &cT