一. 什么是Lambda sDXQ{*6a
所谓Lambda,简单的说就是快速的小函数生成。 B{NGrC`5)
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, k'K 1zUBj
}Q_ }c9?
;uqi
- S%8
class filler K}Lu1:~
{ Sp@{5
public : S~{}jvc
void operator ()( bool & i) const {i = true ;} /?:q9Wy
} ; sB<y(}u
2bTM0-
CjU?3Ag
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: oTf^-29d
6"V86b0)h}
z_87;y;=
Uy$?B"Z
for_each(v.begin(), v.end(), _1 = true ); 0lpUn74F
s5oU
(&qjY
I
那么下面,就让我们来实现一个lambda库。 G\
/L.T
trL8oZ6
Pol
c.
"XKd#ncP
二. 战前分析 7G23D
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 TL([hR _
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 3@mW/l>X
d0-T\\U
9TV1[+JWe
for_each(v.begin(), v.end(), _1 = 1 ); d'b q#r
/* --------------------------------------------- */ %~qY\>
vector < int *> vp( 10 ); JPkI+0
transform(v.begin(), v.end(), vp.begin(), & _1); kSO:xS0 _N
/* --------------------------------------------- */ ?^
`EI}g
sort(vp.begin(), vp.end(), * _1 > * _2); Med0O~T%
/* --------------------------------------------- */ a`zw5
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); 4"Pf0PD:
/* --------------------------------------------- */ # |,c3$
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); NV9H"fI
/* --------------------------------------------- */ o*s3"Ib
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); .q9i10C
F vHd`
H)i%\7F5
>FReGiK$T
看了之后,我们可以思考一些问题: q%MLj./?[
1._1, _2是什么? $(;0;!t.
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 ,%,.c^-
2._1 = 1是在做什么? 9C\@10 D
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 Xldz&&@
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 yUu+68Z6
IoWK 8x
x%,!px3s
三. 动工 "y=AVO
首先实现一个能够范型的进行赋值的函数对象类: [HQ Bx`3TS
D,,
x<JG|
s%t =*+L\
*gN)a%9
template < typename T > t`vIcCXqyl
class assignment \m1jV>q
{ ??=7pFm
T value; oOHr~<
public : IsP!ZcV;
assignment( const T & v) : value(v) {} ph=U<D4
template < typename T2 > bd3q207>
T2 & operator ()(T2 & rhs) const { return rhs = value; } S&;D
} ; |=ljN7]!
nWv6I&
M7SVD[7~HM
其中operator()被声明为模版函数以支持不同类型之间的赋值。 VseeU;q
然后我们就可以书写_1的类来返回assignment s@5r}6?M
IP l]$j>N
u
YJL^I8M'
[7gwJiK
class holder +xRSd *
{ gq an]b_
public : v6+<F;G3y>
template < typename T > wM&WR2
assignment < T > operator = ( const T & t) const ?K^~(D8(
{ g(F? qP_K
return assignment < T > (t); >O}J*4A>+#
} B;xGTl@8
} ; %Dm:|><V$b
/S&8%fb
K!_''Fg
由于该类是一个空类,因此我们可以在其后放心大胆的写上: "\1QJ
W1p5F\ wt
static holder _1; t+Hx&_pMj
Ok,现在一个最简单的lambda就完工了。你可以写 %%f(R7n
dSIZsapH
for_each(v.begin(), v.end(), _1 = 1 ); ^ l9NF
而不用手动写一个函数对象。 '.d]n(/lZd
%&b70]S(
QLe<).S1B2
n ^_B0Rkv
四. 问题分析 Z^yhSbE{5
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 .?p\=C@C+
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 rty&\u@}
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 Z;nUS,?om
3, 我们没有设计好如何处理多个参数的functor。 41jlfKiOm
下面我们可以对这几个问题进行分析。 2K$#U|Qi
dNgjM
Q
五. 问题1:一致性 L\("
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| :Y2J7p[+
很明显,_1的operator()仅仅应该返回传进来的参数本身。 sn.&|)?Fi
"N*i!h
struct holder ad[oor/7|
{ V-TWC@Y"
// ]~-vU{
template < typename T > ,Frdi>7 ~
T & operator ()( const T & r) const )m[dfeqd +
{ "=\@
a=
return (T & )r; R3Ka^l8R|
} F otHITw[
} ; Jl(G4h V'\
D^e7%FX
这样的话assignment也必须相应改动: :T# "bY
;#Pc^Yzc1
template < typename Left, typename Right > $yg=tWk
class assignment &[|P/gj#>
{ 5 ]v]^Y'?
Left l; ;m cu(J
Right r; h`b[c.%
public : *]RCfHo\=
assignment( const Left & l, const Right & r) : l(l), r(r) {} a#4 'X*
template < typename T2 > SebJ}P1x
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } N_),'2
} ; Ig M_l=
Y]>Qu f.!
同时,holder的operator=也需要改动: O)Mf/P'
"/}cV5=Z
template < typename T > J{bNx8.&
assignment < holder, T > operator = ( const T & t) const ;IYH5sG{
{ KK4"H]!.
return assignment < holder, T > ( * this , t); .WT^L2l%
} kw.IVz<
mFXkrvOf,
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 K7N.gT*4
你可能也注意到,常数和functor地位也不平等。 a5xmIp@6
q^k]e{PD
return l(rhs) = r; @ME
.
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 N_Y*Z`Xb
那么我们仿造holder的做法实现一个常数类: /l@h[}g+d-
Y94/tjt
template < typename Tp > Yab=p
9V;;
class constant_t ~ GW8|tw
{ eq#x~O4
const Tp t; -L%2*`-L$
public : j1{\nP/
constant_t( const Tp & t) : t(t) {} uepL"%.@7|
template < typename T > ]h6mJ{k
const Tp & operator ()( const T & r) const q=40l
{ 1-bQ
( -
return t; Jf{
M[ z
} @*rED6zH
} ; --9Z
Nu%:7
该functor的operator()无视参数,直接返回内部所存储的常数。 9x40
下面就可以修改holder的operator=了 c@1q8,
Hz6yy*
template < typename T > f8'$Mn,
assignment < holder, constant_t < T > > operator = ( const T & t) const O#5ll2?
{ , JUP
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); p*
} U
DC>iHt
mC}!;`$8p
同时也要修改assignment的operator() >7^+ag~&
"Nn+Zw43
template < typename T2 > )QvuoaJQ
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } ^3:DeZf!u
现在代码看起来就很一致了。 |rbl sL2?Z
;y{VdT
六. 问题2:链式操作 :9Vd=M6,
现在让我们来看看如何处理链式操作。 -=A W. Zo
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 ;dh8|ujh
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 \O7Vo<B&D
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 "<J%@
现在我们在assignment内部声明一个nested-struct K9J"Q4pEC
j{;RuNt
template < typename T > k-LT'>CWl
struct result_1 M"t=0[0DM:
{ yU@~UCmja
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; ^QKL}xiV:
} ; &MlBpI
0y3<Ho,+$
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: !tNJLOYf
Fc"&lk4e
template < typename T > %$l^C!qcY
struct ref -Jtx9P
{ qWzzUM1=
typedef T & reference; l^IPN'O@
} ; f @cs<x
template < typename T > #!FLX*,
struct ref < T &> n6a*|rE
{ s;0eD5b>x
typedef T & reference; g#ZuRL
} ; G{cTQH|
r_kw "9
有了result_1之后,就可以把operator()改写一下: ab=s+[r1
;Q]j"1c
template < typename T > %YaUc{.%
typename result_1 < T > ::result operator ()( const T & t) const ?"aj&,q+
{ iZy`5
return l(t) = r(t); /Lc=
K<
} 2z\4?HJy
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 7Pc0|Z/
同理我们可以给constant_t和holder加上这个result_1。 N&0MA
Vd{h|=J
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 IFX|"3[$
_1 / 3 + 5会出现的构造方式是: ] _/d
_1 / 3调用holder的operator/ 返回一个divide的对象 m7XJe[O
+5 调用divide的对象返回一个add对象。 Qjj:r~l
最后的布局是: Qn7l-:`?
Add |m%M$^sZ}
/ \ &E{5k{Y
Divide 5 Ur626}
/ \ 4R U1tWQ%
_1 3 x Qh?
似乎一切都解决了?不。 a9E!2o+,
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 t|X |67W
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 sJlX]\RLQ
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: rI:KZ}GZ
k"P2J}4eO
template < typename Right > F$K-Q;r]<
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const Z w5\{Z0
Right & rt) const Or9@ X=C
{ ~EU[?
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); f$E66yG
} OU(z};Is6Z
下面对该代码的一些细节方面作一些解释 ?CS
jn
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 fJCh
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 k"SmbFn%N0
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 wYf=(w\c
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 ]
%*970
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? H&L=WF+x
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: UZdE^Q[
9xg_M=72
template < class Action > 2`* %NJ
class picker : public Action x~GV#c
{ s9A'{F
public : er5}=cFZ
picker( const Action & act) : Action(act) {} =&fBmV
// all the operator overloaded mm=Y(G[_%y
} ; ucj )t7O
%6<Pt
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 e76@-fg
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: ![5<\
R7KQ-+Zb
template < typename Right > (Df<QC`0v
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const bq4H4?j
{ 'w%N(N tq
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); GtO5,d_
} !9"R4~4
p _e-u-
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > U!a"r8u|8q
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 `OQ&u
+&\TdvNI4
template < typename T > struct picker_maker l@*/1O)v
{ J'O`3!Oy/
typedef picker < constant_t < T > > result; *:.0c
} ; i,")U)b
template < typename T > struct picker_maker < picker < T > > K23_1-mbe
{ Y%:p(f<
typedef picker < T > result; lSyp
k-c
} ; (r[<g*+3
A2&&iL=j/
下面总的结构就有了: ?<frU ,{
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 =zA=D.D2
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 7IJb$af:;
picker<functor>构成了实际参与操作的对象。 g}^/8rW
至此链式操作完美实现。 w#mnGD
sW2LNE
|V9%@
Y?
七. 问题3 ,H[AC}z2X
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 0D#!!r ;
;D8Nya>%
template < typename T1, typename T2 > wI}'wALhA
??? operator ()( const T1 & t1, const T2 & t2) const K=5_jE^e
{ 0HD1Ob^@
return lt(t1, t2) = rt(t1, t2); 5,AQ~_,'\
} _R(5?rG,
0acY@_
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: z3*G(,
L)nVNY@Mc
template < typename T1, typename T2 > (+]k{
struct result_2 GPx S.&
{ uWnS<O
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; ['km'5uZ^
} ; Rg[e~##
IPxfjBC+J
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? l!AZ$IV
这个差事就留给了holder自己。 u
F*cS&'Z
gy =`c MS@
` 4EOy:a
template < int Order > z~
u@N9M
class holder; @I"Aet'XV
template <> ,O~2
R
class holder < 1 > 3X!~*_iC
{ $Qy(ed
public : pO+1?c43
template < typename T > 2FVKgyV
struct result_1 3+|6])Hi1
{ uBE,z>/,;
typedef T & result; pV("NJj!
} ; J$I1*~I4v
template < typename T1, typename T2 > `u>BtAx8
struct result_2 ,;d9uG2
{ mTP.W#N
typedef T1 & result; Ba+OoS
} ; BWPYHWW}E
template < typename T > R-Fi`#PG2
typename result_1 < T > ::result operator ()( const T & r) const *>'R
R<
{ ABHZ)OM
return (T & )r; CQ( @7
} \7j)^
template < typename T1, typename T2 > fBLd5
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const qBNiuV;*
{ `X^e}EGWu
return (T1 & )r1; GC\/B0!
} >(*jbL]p
} ; Fp]8f&l8
-.*\J|S@g
template <> tJu<#hX
class holder < 2 > sMS`-,37u
{ "G,*Z0V5
public : %@&)t?/=
template < typename T > &V:dcJ^Q
struct result_1 ,){0y%c#y
{ $Tur"_`I;
typedef T & result; .E}});l
} ; aXJe"IT.u
template < typename T1, typename T2 > Y@4vQm+
struct result_2 XP` kf]9
{ v4zd
x)
typedef T2 & result; 8Cqs@<r4Od
} ; >ATW/9r
template < typename T > kxmS
typename result_1 < T > ::result operator ()( const T & r) const |K_B{v.
{ f!J^vDl
return (T & )r; 6'%]6"&M4
} e"CLhaT
template < typename T1, typename T2 > +-nQ,
fOV
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const aOD"z7}U
{ Ax^'unfQ:
return (T2 & )r2; Ji!-G4.n"
} 1%@~J\qF
} ; tQ~B!j]
0\#Q;Z2
% *G)*n
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 lewDR"0Kx
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: 'AAY!{>
首先 assignment::operator(int, int)被调用: f5a](&
Xp~]kRm9
return l(i, j) = r(i, j); 9vbh5xX
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) 7xc<vl#:q7
Xdq,
=;
return ( int & )i; *YtNt5u
return ( int & )j; B~NC
最后执行i = j; :z\f.+MI
可见,参数被正确的选择了。 CN=&Je%I
~ tLR
_'7/99]4g}
Ax0,7,8y
h0
Sf=[>z
八. 中期总结 *mQit/k.
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: g=C<E2'i*
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 |u{QI3#'
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 +mA=%?l
3。 在picker中实现一个操作符重载,返回该functor 4B]61|A
6\3k0z
[KH?5C
DOerSh_0W
zFtGc
upDQNG>d
九. 简化 u,m-6@il
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 1955(:I
我们现在需要找到一个自动生成这种functor的方法。 1,j9(m2
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: QP B"EW
1. 返回值。如果本身为引用,就去掉引用。 ^PQV3\N
+-*/&|^等 _")h
%)f
2. 返回引用。 hQm4R]a
=,各种复合赋值等 m=MT`-:
3. 返回固定类型。 BB.TrQM.#
各种逻辑/比较操作符(返回bool) a+/|O*>#
4. 原样返回。 >y9o&D