一. 什么是Lambda 'F[ C 4
所谓Lambda,简单的说就是快速的小函数生成。 +e6c4Tw/
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, 0piBK=tE/
'#b7Z?83C
"<J%@
0u"/7OU
class filler VI(;8
{ 6Q6l?!|W4
public : M"t=0[0DM:
void operator ()( bool & i) const {i = true ;} yU@~UCmja
} ; ^QKL}xiV:
&MlBpI
0y3<Ho,+$
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: !tNJLOYf
<15POB
%$l^C!qcY
8uO@S*)0
for_each(v.begin(), v.end(), _1 = true ); M:~/e8Xv
/<s$Am
6!3Jr
那么下面,就让我们来实现一个lambda库。 I:qfB2tL)O
o,sw[
T"GuE[?a
p~sfd
二. 战前分析 ~',}]_'oR-
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 I'[hvp
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 z]YP
-*K!JC-
`>q|_w\e
for_each(v.begin(), v.end(), _1 = 1 ); B
az:N6u
/* --------------------------------------------- */ s\`Vr;R:|
vector < int *> vp( 10 ); ^!*?vHx:
transform(v.begin(), v.end(), vp.begin(), & _1); QxGQF|
/* --------------------------------------------- */ WLAJqmC]
sort(vp.begin(), vp.end(), * _1 > * _2); >Ufjmm${
/* --------------------------------------------- */ ikGH:{
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); yMNLsR~ rh
/* --------------------------------------------- */ J\%<.S>
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); .=>T yq
/* --------------------------------------------- */ P'Fy,fNg
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); y%H;o?<WX
PSdH9ea
r]{fjw(~
lbES9o5
看了之后,我们可以思考一些问题: I@=h|GM
1._1, _2是什么? X'&$wQ6,K
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。
,qRSB>5c
2._1 = 1是在做什么? 3"gifE
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 RTSR-<{z
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 {}3kla{
$l&&y?()
~?}/L'q!b
三. 动工 (/_Q
r2KfC
首先实现一个能够范型的进行赋值的函数对象类: P#H#@:/3
@Y>3 -,o,S
+fhyw{
|7Q8WjCQ{m
template < typename T > RZfC?
class assignment _^RN
C)ol
{ >5Zpx8W
T value; ^gFjm~2I
public : 7F-b/AdVq
assignment( const T & v) : value(v) {} g)'tr
'
template < typename T2 > K.2M=Q
T2 & operator ()(T2 & rhs) const { return rhs = value; } Siw9_c
} ; r2T?LO0N{
er5}=cFZ
=&fBmV
其中operator()被声明为模版函数以支持不同类型之间的赋值。 F_~-o,\
然后我们就可以书写_1的类来返回assignment ucj )t7O
%6<Pt
O#7ldF(
e76@-fg
class holder ![5<\
{ UBRMV
s
public : | 4I x2GD
template < typename T > 04;y%~,}U/
assignment < T > operator = ( const T & t) const S'-<p<;D\B
{ ,l<-*yMD
return assignment < T > (t); z1+rz%
} 1#qCD["8
} ; 4Uf+t?U9
e#^|NQ<'A
Z"?AaD[
由于该类是一个空类,因此我们可以在其后放心大胆的写上: fC3IxlG
s/[i>`g/9
static holder _1; ud:?~?j&w
Ok,现在一个最简单的lambda就完工了。你可以写 U30)r+&
V8Q#%#)FHe
for_each(v.begin(), v.end(), _1 = 1 ); 5?kA)!|UB
而不用手动写一个函数对象。 8{+~3@T
@sKAsn
pOI+
`Ik}Xw
四. 问题分析 73~Mq7~8
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 |->y'V
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 UKK}$B
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 &SN$D5U'
3, 我们没有设计好如何处理多个参数的functor。 (P#2Am$
下面我们可以对这几个问题进行分析。 o33{tUp'
,.FTw,<
五. 问题1:一致性 &up/`8
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| ;oFaDTX]
很明显,_1的operator()仅仅应该返回传进来的参数本身。 hqD;<:.
lO $M6l
struct holder 0]oQ08
{ SA>;]6)`(
// 5,AQ~_,'\
template < typename T > ,f?#i%EF&
T & operator ()( const T & r) const Ql*/{#$
{ N2&aU?`e
return (T & )r; Y0B*.H
Ae
} \S7OC
} ; %yw*!A1
Sw1]]-Es
这样的话assignment也必须相应改动: /1li^</|p`
G0s:Dum
template < typename Left, typename Right > =cC]8Pz?
class assignment cn\& ;55v
{ f!$J_dz
Left l; iKabo,~
Right r; b"FsT
public : ,t+ATaOF
assignment( const Left & l, const Right & r) : l(l), r(r) {} r3j8[&B"
template < typename T2 > Zc4hjg
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } "}HQ)54&
} ; H+5]3>O-$
3+|6])Hi1
同时,holder的operator=也需要改动: uBE,z>/,;
<Ab:yD`K!
template < typename T > J$I1*~I4v
assignment < holder, T > operator = ( const T & t) const `u>BtAx8
{ @J<B^_+Se
return assignment < holder, T > ( * this , t); mTP.W#N
} [d&Faa[`
Fcr@Un'
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 fd,~Yj$R?
你可能也注意到,常数和functor地位也不平等。 a+~o: 5
l wg.'<
return l(rhs) = r; $GO'L2oLwn
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 ^p7(
那么我们仿造holder的做法实现一个常数类: =hs@W)-O
PRz oLzr
template < typename Tp > \~)573'
class constant_t GO)rpk9
{ /MU<)[*Ro
const Tp t; RrZjC
public : Nz}Q"6L
constant_t( const Tp & t) : t(t) {} kx=AX*I
template < typename T > .FXQ,7mZ-
const Tp & operator ()( const T & r) const f.P( {PN
{ w%_BX3GTO
return t; |TUpv*pq
} Np-D:G
} ; Q~@8t"P
9bNIaC*M
该functor的operator()无视参数,直接返回内部所存储的常数。 cY"^3Ot%^
下面就可以修改holder的operator=了 VDPN1+1*
z>0"T2W
y
template < typename T > (;j7{(
assignment < holder, constant_t < T > > operator = ( const T & t) const @iP6N
{ K`X2N
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); ww,c)$
} |@g1|OWd|
5->PDp
同时也要修改assignment的operator() OX`n`+^D
6+u'Tcb
template < typename T2 > d$TW](Bby
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } ~JNuy"8
现在代码看起来就很一致了。 PW`Tuj
jFXU
xf
六. 问题2:链式操作 >eTlew<5
现在让我们来看看如何处理链式操作。 I>5@s;
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 \Cs<'(=
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 S }n;..{
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 J9 =gv0
现在我们在assignment内部声明一个nested-struct bvx:R ~E$
*Z:PB%d5
template < typename T > "XY?v8*c
struct result_1 +n, BD C;
{ qC4-J)8Wk
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; jwq"B$ap
} ; HxM sH5;
.;:xx~G_Q
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: :}JZKj!}M
JB(;[# '~
template < typename T > fEjW7 c
struct ref LNZ#%R~r
{ ?},ItJ#>)q
typedef T & reference; uJOW%|ZN`
} ; _5T7A><q<
template < typename T > ^8m+*t
struct ref < T &> V"p<A
{ Vd0GTpB?1
typedef T & reference; ger<JSL%
} ; 1pb;A;F,A
0uz"}v)
有了result_1之后,就可以把operator()改写一下: ffM(il/2
5G<CDgl^!
template < typename T > 4cQ5E9
typename result_1 < T > ::result operator ()( const T & t) const {Pb^Lf >
{ (OqJet2{+
return l(t) = r(t); X4$e2f
} -"e}YN/
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 &XsLp&Do2
同理我们可以给constant_t和holder加上这个result_1。 x3s^u~C)(w
Wn^^Q5U#
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 L)}V[j#
_1 / 3 + 5会出现的构造方式是: [!&k?.*;<
_1 / 3调用holder的operator/ 返回一个divide的对象 BB.TrQM.#
+5 调用divide的对象返回一个add对象。 psC7IE<v
最后的布局是: \`zG`f
Add w4'K2 7
/ \ 'D&G~$
Divide 5 Qm#i"jvV
/ \ v)yimIHzo
_1 3 WQpJd7
似乎一切都解决了?不。 :6?&FzD`
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 3-bcY4
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 W6O.E
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: ikhX5
&e
kkBU<L2
template < typename Right > 2NknC>9(\
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const @'*#]YU8
Right & rt) const CLfb`rF
{ $-]setdY
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); ^,K.)s
} 8 uxFXQ
下面对该代码的一些细节方面作一些解释 5{q/z^]
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 ]7t\%_
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 z4641q5'm
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 6B/"M-YME
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 LH#LBjOZk
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? l :Nxl
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: z8|9WZ:
O{#Cddt:r
template < class Action > #U52\3G
class picker : public Action \hW73a!
{ eH955[fVd4
public : q"D
L6 >j
picker( const Action & act) : Action(act) {} KN:dm!A
// all the operator overloaded :EwA$`/
} ; F[=lA"F^
yl<$yd0Zdu
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 }AW)R&m
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker:
}pnFJ
j{R|]SjW2H
template < typename Right > |/^aLj^u
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const 1vs>2` DLa
{ M3@fc,Ch
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); 6Y)^)dOi
} ?gwbg*
m=\eL~h
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > ev%t5NZ
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 #}7m'F
HQ`nq~%&(
template < typename T > struct picker_maker +Z&&H'xD
{ Vfm #UvA
typedef picker < constant_t < T > > result;
Jf<yTAm
} ; q>(u>z!
template < typename T > struct picker_maker < picker < T > > 7Y|>xx=v
{ $a*Q).^
typedef picker < T > result; c9TAV,/fF*
} ; bNjaCK<
fC GDL6E
下面总的结构就有了: J5p!-N`NS
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 (vsk^3R[6
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 }0*ra37z>
picker<functor>构成了实际参与操作的对象。 sq(Ar(L<
至此链式操作完美实现。 3ZL7N$N}7
tW.>D;8
d)1sP0Z_@
七. 问题3 0 ,Qj:
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 y?z _^ppj
gVA}?t;
template < typename T1, typename T2 > |vDoqlW
??? operator ()( const T1 & t1, const T2 & t2) const ws2j:B
{ J=SB/8tQ)T
return lt(t1, t2) = rt(t1, t2); a-A+.7
} cw]>a&d
5'c+313 lm
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: #X@<U <R
v#%>uLl
template < typename T1, typename T2 > {9.~]dI|L
struct result_2 <fsn2[V:B%
{ iC|6roO!jk
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; QjjJtKz
} ; Na 9l#
$
lsRg:J
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? .V 3X#t
这个差事就留给了holder自己。 zHoO?tGf
{iIg 4PzrU
#D LT-G0
template < int Order > h[je _^5
class holder; B,vHn2W
template <> yp2 'KES>
class holder < 1 > TQ\wHJ
{ fFZ`rPb
public : h/0-Mrk;e
template < typename T > BRU9LS
struct result_1 YNgR1:l
{ 9 CK\tx&
typedef T & result; {`Fx~w;i
} ; G<u.+V
template < typename T1, typename T2 > *VC4s`<
struct result_2 Hu9-<upc&
{ ]i,Mq
typedef T1 & result; 9HNh*Gc=
} ; fyg~KF}
template < typename T > 5lHN8k=mm2
typename result_1 < T > ::result operator ()( const T & r) const snTJe[^d
{ H&yFSz}6a
return (T & )r; ~b$z\|Y
} xL39>PB
template < typename T1, typename T2 > A.$VM#
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const RZ)vU'@kx
{ 1f@U:<:
return (T1 & )r1; uWR,6\_jY
} HDSA]{:sl
} ; z@%/r~?|
J!A/r<
template <> 34m' ]n
class holder < 2 > Q9eYF-+
{ m['v3m:
public : 01-\:[{
template < typename T > q(&^9"
struct result_1 _]=TFz2O
{ ndKvJH 4
typedef T & result; @u"kX2>Eq
} ; C?/r}ly<\
template < typename T1, typename T2 > C;)Xwm>e
struct result_2 8!&ds~?
{ =Y]'5cn{
typedef T2 & result; qtdxMX]iR
} ; VO @
4A6
template < typename T > zy5s$f1IA
typename result_1 < T > ::result operator ()( const T & r) const fVA=<:
{ cFI7}#,5
return (T & )r; ^`TKvcgIc
} 3D$\y~HU
template < typename T1, typename T2 > 0+n&BkS'
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 7SA-OFM
{ c_-" Qo
return (T2 & )r2; ,Y g5X
} DX&lBV
} ; zO).<xIq+
n $O.>
mV**9-"
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 -n=$[-w
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: "u Of~e"
首先 assignment::operator(int, int)被调用: J I+KS
^:cb
$9F
return l(i, j) = r(i, j); wv7p,9Z[
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) hyk|+z`B
H)j[eZP
return ( int & )i; _>jrlIfc
return ( int & )j; ;9p#xW6
最后执行i = j; =q"w2b&
可见,参数被正确的选择了。 [$1: &!(!
U!a!|s>
[U%ym{be^
je- ,S>U
@Hspg^
八. 中期总结 F=
_uNq
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: Cz=A{<^g
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 |c06ix;).
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 {FV,j.D
3。 在picker中实现一个操作符重载,返回该functor vB{;N
.-('C> @
k7yv>iN
}sTH.%
(E"&UC[
u@=+#q~/P
九. 简化 Q*09E
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 ;1*m}uNz
我们现在需要找到一个自动生成这种functor的方法。 =9;[C:p0-
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: XI@6a9Uk
1. 返回值。如果本身为引用,就去掉引用。 HQ|o%9~
+-*/&|^等 gtaV6sD
2. 返回引用。 Qm35{^p+
=,各种复合赋值等 "4Lg8qm
3. 返回固定类型。 JAGi""3HG
各种逻辑/比较操作符(返回bool) 1AV1d%F
4. 原样返回。 g{g`YvLu^
operator, gZ`32fB%
5. 返回解引用的类型。 Gsds!z$
operator*(单目) q:`77
6. 返回地址。 7gVh!rm
operator&(单目) J^ +_8
7. 下表访问返回类型。 nV!2Dfd
operator[] Xk{!' 0
8. 如果左操作数是一个stream,返回引用,否则返回值 Z-^uM`],G
operator<<和operator>> ]+}ZfHp
]~j_N^oZ1X
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 '2Q.~6
例如针对第一条,我们实现一个policy类: J<