一. 什么是Lambda fTi5Ej*/?)
所谓Lambda,简单的说就是快速的小函数生成。 =BeJ.8$@VC
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, 6PLdzZ{
6+SaO
!lR
g:&PjKA
Gr~J-#a3~D
class filler fs,>X!l+
{ zy8D&7Ytf
public : EV
R>R
void operator ()( bool & i) const {i = true ;} E$4Ik.k
} ; wqJ1^>TB
'.XR,\g>
p'=XW#2 >
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: R1Q~UX]d=
+ ;B K|([#
F^cu!-L
41i#w;ojI
for_each(v.begin(), v.end(), _1 = true ); OB+QVYk"
J/c5)IB|
8HDI]
那么下面,就让我们来实现一个lambda库。 ^B(:Hv}G(:
Z07SK 'U
oox;8d4}y
ezhK[/E=
二. 战前分析 LP}'upv
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 ({hW
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 Ka8Bed3
KY9@2JG
&hIr@Gi@ch
for_each(v.begin(), v.end(), _1 = 1 ); ;@< e ]Ft
/* --------------------------------------------- */ _TVKvRh
vector < int *> vp( 10 ); if+97^Oy
transform(v.begin(), v.end(), vp.begin(), & _1); Yi|Nd ;
/* --------------------------------------------- */ Ne}x(uRn
sort(vp.begin(), vp.end(), * _1 > * _2); S8;5|ya
/* --------------------------------------------- */ T{lK$j
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); ^7Z.~A y
/* --------------------------------------------- */ Y-]Ne"+vf
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); xepp."O
/* --------------------------------------------- */ ,veI'WHMB
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); Bv^5L>JZ/
.QDeS|l
E&\ 0+-Dw
Ym9~/'%]
看了之后,我们可以思考一些问题: _[y<u})
1._1, _2是什么?
{s?x
NU
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 @5cY5e*i{
2._1 = 1是在做什么? 1j!{?t?
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 ;sY n=r
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 k}e~xbh-y
#6 M3BF
Tuy5h5
三. 动工 OJ<V<=MYZ
首先实现一个能够范型的进行赋值的函数对象类: l' Uj"9r,
+LaR_n[
}i9VV+L#1
G]gc*\4
template < typename T > 9@ :QBe3]
class assignment )/BbASO$)Z
{ 6f;20dn6
T value; m@g9+7
public : ev z@c)8
assignment( const T & v) : value(v) {} *NoixV1>
template < typename T2 > yzyK$WN\[3
T2 & operator ()(T2 & rhs) const { return rhs = value; } U;FJSy
} ; g<YN#
`'b2 z=j
.-cx9&
其中operator()被声明为模版函数以支持不同类型之间的赋值。 D8)6yPwE
然后我们就可以书写_1的类来返回assignment Vv*](iM
Z
\;{e'#o
\T^ptj(0
vFi+ExBU
class holder fD2)/5j1
{ mN1n/LNi
public : c{})Z=
template < typename T > F;Bq[V)R
assignment < T > operator = ( const T & t) const SH6T\}X:
{ ??,/85lM
return assignment < T > (t); ed$w5dv
} Ev0=m;@_
} ; r!/<%\S
9+I/bl4
9QEK|x`8
由于该类是一个空类,因此我们可以在其后放心大胆的写上: ;~( yv|f6
J(Zz^$8]<?
static holder _1; nc.:Wm6Mj
Ok,现在一个最简单的lambda就完工了。你可以写 |_%q@EID
T<o8lL
for_each(v.begin(), v.end(), _1 = 1 ); HD>UTX`&mc
而不用手动写一个函数对象。 >yqFO
I"HA(
+G
f^G-ba
Er<!8;{?
四. 问题分析 gh.+}8="
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 [s~6,wz
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 x+,:k=JMT
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 TECp!`)j"
3, 我们没有设计好如何处理多个参数的functor。 |eP5iy wg
下面我们可以对这几个问题进行分析。 FR6PY
'oF ('uR
五. 问题1:一致性 *)s^+F 0
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| ]+T$D
很明显,_1的operator()仅仅应该返回传进来的参数本身。 QQ./!
f;obK~b[
struct holder 4,?WNPqo
{
O<y65#68Z
// SL?YU(a
template < typename T > @81N{tg-
T & operator ()( const T & r) const * 5(%'3
{ ) RNB;K~s9
return (T & )r; ma@!"Z8S
} JHg
y&/
} ; t/h,-x
wnHfjF
这样的话assignment也必须相应改动: ?vmoRX
;e6-*
template < typename Left, typename Right > YZ6"
s-
class assignment ,z`* 1b8
{ /?u]Fj
Left l; -{NP3zy
Right r; <l<6W-I
public : ^n*:zmD
assignment( const Left & l, const Right & r) : l(l), r(r) {} c uHF^l
template < typename T2 > $aHHXd}@t2
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } 1Hs'YzvY
} ; TVAa/_y2`
Fmzkbt~oe
同时,holder的operator=也需要改动: t@q==VHF
{pC$jd>T
template < typename T > O6Y1*XTmH6
assignment < holder, T > operator = ( const T & t) const 5jHr?C
{ - #-Bo
return assignment < holder, T > ( * this , t); 0N_u6*@
} -!IeP]n#P
=4gPoS
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 Uz%2{HB@{
你可能也注意到,常数和functor地位也不平等。 yacN=]SW5
$ J!PSF8PL
return l(rhs) = r; piXL6V @c
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 #?'@?0<6
那么我们仿造holder的做法实现一个常数类: ;Swy5z0=ro
5.
+_'bF|
template < typename Tp > +-qa7
class constant_t ^;wz+u4^l
{ 1wBmDEhS
const Tp t;
7MQxW<0
public : b;5
M$
constant_t( const Tp & t) : t(t) {} !1Nh`FN
template < typename T > +NVXFjPC
const Tp & operator ()( const T & r) const Cm9#FA
{ 2IXtIE
return t; aev(CY,z
} ]U,m
1
} ; }H|'W[Q.
=ba1::18
该functor的operator()无视参数,直接返回内部所存储的常数。 |nBZ :$D
下面就可以修改holder的operator=了 DC0ON`
l YpoS
template < typename T >
Ru4M7%
assignment < holder, constant_t < T > > operator = ( const T & t) const u@t~*E5BpM
{ >v)V2,P
-
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); <Df2
} \=Od1 i
8L5O5F'
同时也要修改assignment的operator() gObafIA
{+V ]@sz
template < typename T2 > 3!`_Q%
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } ~U5Tn3'~
现在代码看起来就很一致了。 nK#%Od{GF
(,b\"Q
六. 问题2:链式操作 p!K^Q3kO
现在让我们来看看如何处理链式操作。 hx ^ l
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 0bOT&Z^
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 6VLo4bq 5
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 *'@sm*
现在我们在assignment内部声明一个nested-struct pUa\YO1J
yatZAl(B
template < typename T > ll*Ez"
struct result_1 (S2E'L L{
{ z>)lp$
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; `nY.&YT
} ; 1'|gxYT
{u4AOM=)
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: Y$s4 *)%
1C0'
Gf)3
template < typename T > V!NRBXg
struct ref wLNkXC
{ OxUc,%e9P
typedef T & reference; Pk=0pHH8q
} ; -Ua&/Yd/}
template < typename T > Z/d {v:)
struct ref < T &> <r
m)c.
{ y{2\T
typedef T & reference; @r(3
} ; w+a5/i@
$LiBJ~vV<
有了result_1之后,就可以把operator()改写一下: .yD5>iBh
{7%(m|(
template < typename T > wCu!dxT|,
typename result_1 < T > ::result operator ()( const T & t) const rPt
{ tlB-s;
return l(t) = r(t); )TEod!]
} >E3-/)Ti
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 $-]I?cWlQ
同理我们可以给constant_t和holder加上这个result_1。 uPE Ab2u="
=sF4H_B
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 x=kJlGT
_1 / 3 + 5会出现的构造方式是: z m]R76
_1 / 3调用holder的operator/ 返回一个divide的对象 X"7x_yOZ
+5 调用divide的对象返回一个add对象。 N#XC%66qy!
最后的布局是: b1QHZY\g{
Add E<7$!P=z`
/ \ 9Ais)Wy%p
Divide 5 !M(SEIc4A
/ \ !Y&]Y
G
_1 3 +O^} t
似乎一切都解决了?不。 u?F.%j-
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 Rtlc&Q.b
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 VP<LY/'f
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: D
!{e
_9q byhS7
template < typename Right > cp0yr:~
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const A4Q{(z-?
Right & rt) const "=LeHY=9
{ W }v
,6Oe
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); c'mg=jH
} #g'j0N
下面对该代码的一些细节方面作一些解释 dI>cPqQ
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 |~&cTDd
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 db&!t!#,
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 \S&OAe/b
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 %(]B1Zg6,
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? ?bg
/%o
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: zKp R:F
F{rC{5@fj
template < class Action > *9aI\#}
class picker : public Action uGHM ]"!)
{ v=Q!ioE7
public : 2p4iir
picker( const Action & act) : Action(act) {} Z?V vFEt%
// all the operator overloaded <PM.4B@
} ; z, FPhbFn
1/&^~'
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 ~z")';I|
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: 3Tp8t6*nL
<N>7.G
template < typename Right > @!}/$[hu1
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const A.h0 H]*Ma
{ \v$zU
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); {Ppb ;
} 7U^{xDg.b
N(3Bzd)
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > oOaLD{g>
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 ^bfU>02Q6p
4wGBB{X
template < typename T > struct picker_maker d_ x
jW
{ _~*j=XR s
typedef picker < constant_t < T > > result; L\5:od[EP
} ; Jd',v
template < typename T > struct picker_maker < picker < T > > }EP}D?Mmu
{ ii>^]iT
typedef picker < T > result; /I{K_G@
} ; 8&3&^!I
f(5;Rf(
下面总的结构就有了: esq~Ehr=
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 BOP7@ D
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 RLzqpE<rJ
picker<functor>构成了实际参与操作的对象。 W\mgM2p
至此链式操作完美实现。 0)7v_|z
+5 gX6V\
fEiNHV x
七. 问题3
rixVIfVF
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 {47Uu%XT
Y3s8@0b3
template < typename T1, typename T2 > m AET`B "
??? operator ()( const T1 & t1, const T2 & t2) const mN .
{ S)W?W}*R\
return lt(t1, t2) = rt(t1, t2); ecO$L<9>
} ;PnN$g]Q
R3.w")6
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: f`_{SU"3
f9
:=6
template < typename T1, typename T2 > w'XSkI_ay
struct result_2 {d]B+'
{ :>Qu;Z1P
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; )X:Sfk
} ; og~a*my3
c5:0`~5Fn
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? 5rc3jIXc{|
这个差事就留给了holder自己。 oiC@ /
!&3"($-U3G
RlbJ4`a
template < int Order > D>o u,
class holder; B&y?Dc
template <> r!w*y3
class holder < 1 > %tC[q
{ 3gD <!WI
public : 2X*n93AQi
template < typename T > {P\Ob0)q
struct result_1 {K}Dpy
{ P}( c0/
typedef T & result; a=x&sz\x
} ; dmcY]m
template < typename T1, typename T2 > L/,gD.h^
struct result_2 VUP.
\Vry
{ VS_\bIC
typedef T1 & result; q?)5yukeF
} ; TU6YS<
template < typename T > aY;34SF
typename result_1 < T > ::result operator ()( const T & r) const "gzn%k[D9m
{ e'c3.sQ|?
return (T & )r; 'HCRi Z<
} 3Zs0W{OxU
template < typename T1, typename T2 > X+<9-]=
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 9`5.0**
{ \2#K {
return (T1 & )r1; Pn4jI(
} Z_<NUPE
} ; RlU ?F
-*hPEgcV9
template <> [+#k+*1*o
class holder < 2 > 2PUB@B'
+
{ [;4ak)!
public : I9rQX9#B
template < typename T > O8N1gf;t
struct result_1 ygX!'evY
{ ,,6lQ]wG
typedef T & result; ;-l^X%r
} ; |nr;OM
template < typename T1, typename T2 > }H
saJ=1U
struct result_2 RBg2iG$8|
{ $G9E=wn
typedef T2 & result; c,ct=m.|6A
} ; &B=z*m
template < typename T > 'J!Gip ,
typename result_1 < T > ::result operator ()( const T & r) const yB=R7E7
{ 2n2,MB
return (T & )r; 'MB+cz+v
} ZtP/|P5@
template < typename T1, typename T2 > o8IqO'
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 5p:2gsk
{ -]Mk}
z$
return (T2 & )r2; GukwN]*OY
} /R?*i@rvf
} ; G&MO(r}B
!=yO72dgLY
T nyLVIP
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 QwF.c28[
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: K|6}g7&X
首先 assignment::operator(int, int)被调用: xG Y!r"[
f,LeJTX=
return l(i, j) = r(i, j); AXi4{Q,
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) PJe\PGh
m7XN6zX
return ( int & )i; %u<r_^w5
return ( int & )j; jGJf[:M&Pm
最后执行i = j; +9')G-`qj
可见,参数被正确的选择了。 pCa~:q*85
W?.xtQEv
K:Z,4Y
A)d0Z6G`
5GPAt
八. 中期总结 Vhb~kI!x
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: b}u#MU
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 66+]D4(k
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 9)j"|5H
3。 在picker中实现一个操作符重载,返回该functor KBI1t$
t=p"nIE
:J )^gc
FT}^Fi7
%$Q!'+YW
/BF7N3
九. 简化 '=Jz}F <
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 >qGWDCKr
我们现在需要找到一个自动生成这种functor的方法。 20` XklV
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: L ]BTX]
1. 返回值。如果本身为引用,就去掉引用。 >SYOtzg%
+-*/&|^等 P>x88M
2. 返回引用。 7ruWmy;j
=,各种复合赋值等
>Yv#t.!
3. 返回固定类型。 Qt^6w}&
各种逻辑/比较操作符(返回bool) eU-A_5
4. 原样返回。 /8hjs{(;
operator, b+Vlq7Bc
5. 返回解引用的类型。 !4t%\N6Ib
operator*(单目) oW(8bd)
6. 返回地址。 [`KQ\4u
operator&(单目) tEibxE
7. 下表访问返回类型。 \S~<C[P
operator[] n
iB<