一. 什么是Lambda wnQy
所谓Lambda,简单的说就是快速的小函数生成。 xgkCN$zQ`
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, V{q*hQd_3
DOFW"Sp E
i={4rZOD^
ZDp^k{AN9a
class filler WW6-oQs_#*
{ V*2*5hx
public : |"%OI~^%
void operator ()( bool & i) const {i = true ;} >iK LC
} ; .L%pWRxA[
,38M6yD
3$P
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: acUyz2x
"m6G;cv
mDv<d =p!
@f|~$$k=
for_each(v.begin(), v.end(), _1 = true ); $ `\qY ^.(
[9 :9<#?o^
%rrD+
那么下面,就让我们来实现一个lambda库。 OIw[sum2
bw/mF5AsW
qHyOaKMd
a[j]fv*6
二. 战前分析 H<ovIMd
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 c'VCCXe
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 F|!=]A<
9mXmghoCO
vyWx{@
for_each(v.begin(), v.end(), _1 = 1 ); jz;{,F
/* --------------------------------------------- */ FwB xag:u
vector < int *> vp( 10 ); <v_Wh@m
transform(v.begin(), v.end(), vp.begin(), & _1); CXz9bhn<4
/* --------------------------------------------- */ FcZ)^RQ4G
sort(vp.begin(), vp.end(), * _1 > * _2); reYIF*
/* --------------------------------------------- */ hMS:t(N{
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); ZR|s]'
/* --------------------------------------------- */ :?z@T[-
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); u-jc8W`Zd
/* --------------------------------------------- */ B+R|fQ
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); Z]2z*XD
nB :i G
{hf_Xro&
m*)jndXY
看了之后,我们可以思考一些问题: rbv
1._1, _2是什么? J~`!@!
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 3rN}iSF^
2._1 = 1是在做什么? L_:~{jV
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 &Y9%Y/Y
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 %1GKN|7
r+#g
]Y->EME:W
三. 动工 :TKx>~`
首先实现一个能够范型的进行赋值的函数对象类: XrMw$_0)
K+L9cv4 |*
+G!#
/u1
!J {[XT
template < typename T > vg X7B4
class assignment z$g__q-
{ k[<i+C";
T value; s{X+0_@Q
public : 4T$jY}U
assignment( const T & v) : value(v) {} 6q0)/|,@
template < typename T2 > H0lW gJmi|
T2 & operator ()(T2 & rhs) const { return rhs = value; }
OU]"uV<(
} ; >bhF{*t#;y
h?4EVOx+
TL$w~dY
其中operator()被声明为模版函数以支持不同类型之间的赋值。 `RU RC"
然后我们就可以书写_1的类来返回assignment &E!m(|6?+
?/,V{!UTtq
<pG 4g
h5aPRPU g
class holder gth_Sz5!#
{ zt|1tU:
public : tOk=m'aUK
template < typename T > Abmi=]\bx
assignment < T > operator = ( const T & t) const )`W|J%w+
{ MX!N?k#KhP
return assignment < T > (t); [?,+DY
} #\xy,C'Y
} ; 4v5qK
SjA'<ZX>TM
QiVKaBS8
由于该类是一个空类,因此我们可以在其后放心大胆的写上: u~'_Uqp
,}>b\(Lk
static holder _1; \>j@!W
Ok,现在一个最简单的lambda就完工了。你可以写 |VyN>&r~6
%|R]nB
for_each(v.begin(), v.end(), _1 = 1 ); 1`Bhis9X8
而不用手动写一个函数对象。 KNP^k$=)3c
:y{@=E=XSC
hQL@q7tUr
@l_rB~
四. 问题分析 ?e+y7K}"]
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 JH2-'
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 Pu BE=9,
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 HG5E,^1n
3, 我们没有设计好如何处理多个参数的functor。 `!ja0Sq]U
下面我们可以对这几个问题进行分析。 w; f LnEz_
JV!F<
五. 问题1:一致性 7fT_]H8
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| +^rt48${ y
很明显,_1的operator()仅仅应该返回传进来的参数本身。 j/ARTaO1]"
%(\et%[]
struct holder pVjOp~=U
{ 0Uk;&a0s
// {irl}EeyC
template < typename T > :V)=/mR
T & operator ()( const T & r) const FiXE0ZI$0q
{ Z)u_2e
return (T & )r; AuB BSk8($
} 00Ye
]j_
} ; 9r8bSV3`
a?W<<9]
这样的话assignment也必须相应改动: {G|= pM\'
H:16aaMn(
template < typename Left, typename Right > .NF3dC\
class assignment {
"f}
}}l
{ mD?={*7%
Left l; {HVsRpNEf
Right r; |F~U
public : "p>kiNu
assignment( const Left & l, const Right & r) : l(l), r(r) {} Te^_gdf
template < typename T2 > Je K0><
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } 8ux
} ; o7v9xm+
;_=dB[M
同时,holder的operator=也需要改动: m^tf=O<
%~lTQCPE
template < typename T > zmFKd5
assignment < holder, T > operator = ( const T & t) const 3JF" O+@
{ UH5A;SrTqR
return assignment < holder, T > ( * this , t); O;(n[k
} ~Hb0)M@y7
ZJjm r,1
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 Vk1 c14i>
你可能也注意到,常数和functor地位也不平等。 ZRa~miKyM
GgvMd~
return l(rhs) = r; wu}Zu
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 %=vU
Z4
那么我们仿造holder的做法实现一个常数类: iVM% ]\
)Tn(!.
template < typename Tp > Y)AHM0;g
class constant_t gm: xtN
{ "Z-YZ>2
const Tp t; axkNy}ct
public : NV2$ >D
constant_t( const Tp & t) : t(t) {} OuPfB
template < typename T > P@Pe5H"o
const Tp & operator ()( const T & r) const 'H1k
{ .;:dG
return t; Z,,q mwd
} u6*0%
Km
} ; ~(.&nysZ-
GM0pHmC
该functor的operator()无视参数,直接返回内部所存储的常数。 t RTJ Q
下面就可以修改holder的operator=了 0 \o5+
qcBamf
template < typename T > *OY
Nx4 k
assignment < holder, constant_t < T > > operator = ( const T & t) const (Ii+}Mfp
{ e{ZS"e`!
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); ^8g<>,$
} S$GWY^5}{
[](] "r
同时也要修改assignment的operator() C'joJEo
19\
V@d^
template < typename T2 > i6:O9Km
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } 7{OD/*|
现在代码看起来就很一致了。 a#/~rNRY
6lQP+! EF
六. 问题2:链式操作 RJD(c#r$
现在让我们来看看如何处理链式操作。 6eK7Jv\K
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 mP./e8
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 m*>gG{3;
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 {"*gX&;~
现在我们在assignment内部声明一个nested-struct (S63:q&g
VzuU0
template < typename T > f(c#1AJE53
struct result_1 mqQC`Aqx:
{ >ZnnGX6$(
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; N >];xb>
} ; >\s+A2P
~HUO$*U4<
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: _6\"U5*Y
nX+c
HF
template < typename T > 3?wL)6Uj8J
struct ref xGw|@d
{ GrM`\MIO
typedef T & reference; i#Z#(D
`m
} ; f"G-',O<
template < typename T > (U|WP%IM'
struct ref < T &> Ap<j;s4`
{ Ce@"+k+w
typedef T & reference; e,@5`aYHM@
} ; bxAHzOB(\
7$JE+gL/7
有了result_1之后,就可以把operator()改写一下: {$_Gjv
mFuHZ)iQG
template < typename T > i[n3ILn
typename result_1 < T > ::result operator ()( const T & t) const }^*m0`H
{ tAS[T9B
return l(t) = r(t); -N1X=4/fg
} {6>:=?7]R
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 Pt7yYl&n7^
同理我们可以给constant_t和holder加上这个result_1。 _j\8u`^n
AXPdgo6
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 PED5>90
_1 / 3 + 5会出现的构造方式是: X[1w(d U[
_1 / 3调用holder的operator/ 返回一个divide的对象 ##yH*{/&
+5 调用divide的对象返回一个add对象。 U%aDkC+M
最后的布局是: RnUud\T/
Add D'"l%p
/ \ Ak@y"!wnM
Divide 5 xc1-($Q,
/ \ u
236a\:
_1 3 3^Z@fC
似乎一切都解决了?不。 /wJocx]vQ
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 c/-PEsk_TP
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。
l\{r-F
N
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: q.d
qr<
cbv%1DT3
template < typename Right > }?,Eb~q
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const XGDJC N
Right & rt) const v2f|%i;tq
{ /k=krAz.
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); (iu IeJ^Z
} 'M%uw85
下面对该代码的一些细节方面作一些解释 Wf-P a9
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 Y]+KsiOL
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 -;&-b >b
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 }_9yemP
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 ~{{@m]P
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? 0Q:l,\lY
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: W-4R;!42
Eyg F,>.4
template < class Action > c^}DBvG,
class picker : public Action Ca#T?HL
{ 3u1\zse
public : !~ZAm3GwL
picker( const Action & act) : Action(act) {} +Al*MusS
// all the operator overloaded ic?(`6N8
} ; U/>l>J5
W%<z|
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 [yDOvQ[
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: 6:`4bo
(Iv*sd
*
template < typename Right > !w:pb7+G
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const {R5_=MG
{ kQO5sX$;
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); DWk2=cO
} <ua! ]~
.}iRe}=
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > MQlGEJ
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 >xIb|Yp)&
5ih5=qX
template < typename T > struct picker_maker B1z7r0Rm,
{ G%SoC
typedef picker < constant_t < T > > result; #[sJKW
} ; ,?VYrL
template < typename T > struct picker_maker < picker < T > > agnEYdM_
{ p+^K$w^Cs
typedef picker < T > result; hCB _g
} ; Ny]]L
3PaMq6Ca
下面总的结构就有了: /7K7o8g
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 Bh()?{q
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 G Cp90
picker<functor>构成了实际参与操作的对象。 3tCT"UvTD
至此链式操作完美实现。 v'SqH,=d
Ba9"IXKH
+D M,+{}
七. 问题3 %=i/MFGX
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 P&AaD!Qn
e
J:#vX86
template < typename T1, typename T2 >
{5JYu
??? operator ()( const T1 & t1, const T2 & t2) const qex::Qf
{ Eg$Er*)h8
return lt(t1, t2) = rt(t1, t2); 7}vx]p2
} =T#?:J#a
@Zfg]L{Lr
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: d@{#F"o
SHqz&2u
template < typename T1, typename T2 > N`7+]T
struct result_2 L:Me
{ ^[1Xl7)`
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; \d
QRQL{LL
} ; s~g]`/h$r
UDHMNubB
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? #kAk
d-QY6
这个差事就留给了holder自己。 -8&P1jrI
.zvvk
J&;' gT
template < int Order > *N%)+-
class holder; N7Kkz
/
template <> F& ['w-n%
class holder < 1 > /5Xt<7vm8
{ KqWO9d?w.
public : Q-||A
template < typename T > |O[ I=!
struct result_1 0t)5K O
{ ]v0=jm5A
typedef T & result; K(_8oB784
} ; Hx ojxZwm
template < typename T1, typename T2 > 6V-JyTcxGI
struct result_2 ;:P}s4p
{ 3+V.9TL'a
typedef T1 & result; W(PNw2
} ; AnQUdU
template < typename T > ?r^>Vk}
typename result_1 < T > ::result operator ()( const T & r) const *ub"!}$st
{ %`]fZr A]#
return (T & )r; K#]FUUnj=
} ]9hhAT44
template < typename T1, typename T2 > /rv=mlpRL
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const (^^}Ke{J
{ c5t7X-L B
return (T1 & )r1; 4J$dG l#f
} `&SBp }W}
} ; <Mf(2`T
rnXoA, c/
template <> -nnAe
F
class holder < 2 > g>_d,#F
{ i[PksT#p
public : 1"U.-I@
template < typename T > nT@FSt
struct result_1 I6[=tB
{ EKzYL#(i
typedef T & result; =_`cY^ib+
} ; 8lF:70wia
template < typename T1, typename T2 > Z xR
struct result_2 Qz([\Xx:
{ ;%O>=m'4
typedef T2 & result; r&nEM6
} ; 6o]>lQ}
template < typename T > x.>[A^
typename result_1 < T > ::result operator ()( const T & r) const 5hp)Z7
{ JiRfLB
return (T & )r; mlbSs_LT^
} tdnd~ WSR
template < typename T1, typename T2 > \7 }{\hY-
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 'BNZUuUl
{ 3 /LW6W|
return (T2 & )r2; 6?= ^8
} Tywrh9[
} ; g715+5z[
~0Mw\p%}
_&PF (/w
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。
_cQhT
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: 9f$3{ g{m
首先 assignment::operator(int, int)被调用: {EVHkQ+o
CMHg]la
return l(i, j) = r(i, j); p\r V 6+
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) @<44wMp
Z^GXKOeq
return ( int & )i; h($Jo
return ( int & )j; M.KXDD#O
最后执行i = j; !-q)9K?
可见,参数被正确的选择了。 q8Rep
9a{9|p>L
(h%xqXs
ib~EQ?u{
gBo~NLrf
八. 中期总结 ^Rmrre`uU
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: N1X;&qZDd
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 z2OXCZ*/
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 2m2$jp0
3。 在picker中实现一个操作符重载,返回该functor {)& b6}2h
p *GAs
C
q:G3y[ P
+!"7=?}
TXfG@4~kC
9,0}}3J
九. 简化 5!7vD|6
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 }xytV5a^
我们现在需要找到一个自动生成这种functor的方法。 61`tQFx,
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: "S3U]zw0_
1. 返回值。如果本身为引用,就去掉引用。 _)^`+{N<
+-*/&|^等 ;e\K8*o
2. 返回引用。 IYB;X
=,各种复合赋值等 }r:8w*47
3. 返回固定类型。 )Tad]Hd"W
各种逻辑/比较操作符(返回bool) c/`Rv{*'o
4. 原样返回。 mv1|oFVW
operator, Kg#s<# h
5. 返回解引用的类型。 :w:ql/?X
operator*(单目) aN~x3G
6. 返回地址。 anFl:=
operator&(单目) /5C>7BC
7. 下表访问返回类型。 +!<{80w
operator[] YPS,[F'B.
8. 如果左操作数是一个stream,返回引用,否则返回值 8YkCTJfBGu
operator<<和operator>> #5_pE1
mJS-x-@
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 -|_io,eL;
例如针对第一条,我们实现一个policy类: Fo&ecWhw
gBE1aw;
template < typename Left > <&=3g/Y
struct value_return J*]JH{
{ E1Rz<&L
template < typename T > MpLn)
struct result_1 .;NoKO7)
{
h]?[}&
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; ((tWgSZ3
} ; "gq_^&
L&qY709
template < typename T1, typename T2 > Oa-~}hN
struct result_2 lK #~lC
{ [300F=R
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; 9XW[NY#)#
} ; X e\,:~
} ; kF7`R4Sz
,4kipJ!,yK
QlWkK.<Z3_
其中const_value是一个将一个类型转为其非引用形式的trait T( sEk
5fud:k
下面我们来剥离functor中的operator() gPr&