一. 什么是Lambda A5zT^!`[
所谓Lambda,简单的说就是快速的小函数生成。 EOjo>w>
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, k9.2*+vvg
|jniI(
Uax- z
8|`4D 'Ln
class filler qde.;Yv9
{ ]z,W1Zs?
public : iU\WV
void operator ()( bool & i) const {i = true ;} %J?;@ G)r
} ; 1_!*R]a q
pUWj,&t
Zycu3%JI
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: SqTO~zGC
bH&Cbme90-
w3c[t~R8
DJ;G0*
for_each(v.begin(), v.end(), _1 = true ); d$/BF&n
U&|=dH]-
GM{m(Y
那么下面,就让我们来实现一个lambda库。 $cFanra
[Zk|s9
PWOV~`^;
z1?7}9~`0c
二. 战前分析 6';'pHqe
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 T+m`a#
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 pIk&NI
<1VzQH!o
}|
_uqvin
for_each(v.begin(), v.end(), _1 = 1 ); %<JjftNQ
/* --------------------------------------------- */ IDb|J%e^P
vector < int *> vp( 10 ); ,YJ\
$?
transform(v.begin(), v.end(), vp.begin(), & _1); &+=A;Y)
/* --------------------------------------------- */ EUU9JnQhBJ
sort(vp.begin(), vp.end(), * _1 > * _2); C+$dm)M/q
/* --------------------------------------------- */ iK1<4)
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); 1K&z64Q5J
/* --------------------------------------------- */ [J0L7p*6
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); Y!v `0z
/* --------------------------------------------- */ !MNUp(:
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); w%)=`'s_
6|t4\'
BCk$FM@
E%
Ce/n
看了之后,我们可以思考一些问题: Y(ly0U}
1._1, _2是什么? 2:Q9gru
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 f7}/ {}g
2._1 = 1是在做什么? Z}TuVE
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 c$Js<[1
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 ?&ThMWl
{e
A4y~k
cOthq87:
三. 动工 a1]k(AuQrC
首先实现一个能够范型的进行赋值的函数对象类: d {a^
oori t
-kxNJ Gc?
PmO utYV
template < typename T > MRiQaUg2
class assignment mF[w-<:.d
{ xxgS!J
T value; f2B?Zn
public : (Kd;l&8
assignment( const T & v) : value(v) {} &F*s.gL
template < typename T2 > dX: (%_Mn
T2 & operator ()(T2 & rhs) const { return rhs = value; } at${^,&
} ; z@^[.
:f?\ mVS+
mdR:XuRD"t
其中operator()被声明为模版函数以支持不同类型之间的赋值。 .@ZqCH
然后我们就可以书写_1的类来返回assignment ~xpU<Pd*
y.26:c(
=O1N*'e
6]rIYc[,
class holder k!b\qS~Q
{ e'mm4 2
public : #.UooFk+Y
template < typename T > (EGsw o
assignment < T > operator = ( const T & t) const o-Pa3L=
{ K?,eIZ{.S
return assignment < T > (t); ',?v7&
} V03U"eI="
} ; aErms-~
4<)%Esyb
pI|Lt
由于该类是一个空类,因此我们可以在其后放心大胆的写上: r4k=i4
uOc:^
static holder _1; )uiYu3 I
Ok,现在一个最简单的lambda就完工了。你可以写 o {Sc
\:]Clvc
for_each(v.begin(), v.end(), _1 = 1 ); VG^*?62
而不用手动写一个函数对象。 r5> FU>7'
oE[wOq+
p<*3mbgGO
-gefdx6ES
四. 问题分析 k`U")lv
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 xGCW-YR9
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 3~}G~ t
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 pw"
!iG}
3, 我们没有设计好如何处理多个参数的functor。 hC?:XVt
下面我们可以对这几个问题进行分析。 $As;Tvw.
E1usxF)
五. 问题1:一致性 :jB~rhZ~
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| Ikql
很明显,_1的operator()仅仅应该返回传进来的参数本身。 P?VGY
i-w^pv'
struct holder \:9dt8(-U
{ z$$ E7i
// >Lx,<sE
template < typename T > q 9lz
T & operator ()( const T & r) const KSnU;B6w>
{ kg?[
return (T & )r; R7}=k)U?d@
} e3,TY.,Ay
} ; %^f!= *
xDv$z.=Y
这样的话assignment也必须相应改动: 5A
oKlJrY
[74HUw>
template < typename Left, typename Right > L|.q19b*
class assignment 5wYYYo=
{ =/Pmi_
Left l; \B) a57
Right r; mIgc)"
public : iz!E1(z(
assignment( const Left & l, const Right & r) : l(l), r(r) {} B/.+&AJw
template < typename T2 > A&X(\ c M
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } EjW3_ %
} ; sS(t
}$
&NZl_7PL
同时,holder的operator=也需要改动: =(:{>tO_"
nXPl\|pXt
template < typename T > IV*@}~BJ
assignment < holder, T > operator = ( const T & t) const @q:v?AO
{ JoeU J3N
return assignment < holder, T > ( * this , t); I[,tf!
} dCv@l7hE
&HBqweI
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 i3#To}g5V
你可能也注意到,常数和functor地位也不平等。 Tlc3l}B*Z
CZ*#FY
return l(rhs) = r; Agt6G\n
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 &J(+XJM%
那么我们仿造holder的做法实现一个常数类: 6 /_] |4t
IX@g].)C
template < typename Tp > 4Gz5Ju
class constant_t ?}|l )
{ };;\&#
const Tp t; l3kYfq{";"
public : +TzZ
constant_t( const Tp & t) : t(t) {} hbl%<ItI49
template < typename T > (1pI#H"f9
const Tp & operator ()( const T & r) const /Iht,@%E
{ \1|]?ZQ\ K
return t; aK>5r^7S
} !kCMw%[
} ; b-4gHW
ZslH2#
该functor的operator()无视参数,直接返回内部所存储的常数。 k\->uSU9
下面就可以修改holder的operator=了 V6l~Aj}/
:'1UX <&B
template < typename T > lO=+V 6
assignment < holder, constant_t < T > > operator = ( const T & t) const
MO}J
{ dQP7CP
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); }?[^q
} 74f3a|vx/
0-Z
sV3I&
同时也要修改assignment的operator() )Dn~e#
Ip c2Qsa
template < typename T2 > +LBDn"5
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } ,K4*0!TXP
现在代码看起来就很一致了。 `"~s<+
81?7u!=ic+
六. 问题2:链式操作 x~1.;dBF
现在让我们来看看如何处理链式操作。 T'YHV}b}vX
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 kg@D?VqJP
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 x1H?e8
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 MtE18m"z
现在我们在assignment内部声明一个nested-struct 9gjI;*(z1
_<Hx1l~
template < typename T > R}~p1=D
struct result_1 9J>b6
{ (EZ34,k'S
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; ?naPti1GX
} ; p#-ov-znp
5vxKkk&i4l
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: !%w#h0(b
D2hEI2S
template < typename T > OPm?kr
struct ref g7*"*%v 2
{ F\pw0^K;N
typedef T & reference; >R|*FYam
} ; si`{>e~`6P
template < typename T > @q=l H
*=
struct ref < T &> WY=RJe2
{ _PTo!aJL
typedef T & reference; 1|K>V;C
} ; #$\cRLPg
;=rM Ii
有了result_1之后,就可以把operator()改写一下: E>_?9~8Mf
}qf9ra
template < typename T > t<`h(RczHI
typename result_1 < T > ::result operator ()( const T & t) const In1VW|4h
{ FN$hEc!
return l(t) = r(t); 'vgO`
} NF?FEUoxz
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 JGmW>mH
同理我们可以给constant_t和holder加上这个result_1。 M :m-i X
[,GXA)j
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 p)
x.Y
_1 / 3 + 5会出现的构造方式是: b0\'JZ
_1 / 3调用holder的operator/ 返回一个divide的对象 sy^k:y?
+5 调用divide的对象返回一个add对象。 &p?Oo^
最后的布局是: H<$.AC\zn
Add G5^gwG+
/ \ WZ.d"EE"
Divide 5 3F%Qq7v
/ \ j
s(E-d/
_1 3 Bjg 21bw^
似乎一切都解决了?不。 tykA69X\W
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 pB
@l+
n^
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 6{O#!o*g
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: jgiP2k[Xom
1[k~*QS
template < typename Right > 9JF*xXd>Q
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const id^U%4J
Right & rt) const |pIA9/~Z
{ L_+0[A
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); Dl862$_Q
} nMU#g])y)
下面对该代码的一些细节方面作一些解释 3t(8uG<rL
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 47Y|1
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 Q37VhScs
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 K#"@nVWJ.m
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 eO,
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? /)80@
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明:
]
=Js 5
//--r5Q
template < class Action > {$iJYS\
class picker : public Action (xU+Y1*g"%
{ {Y5h*BD>
public : my#qmI
picker( const Action & act) : Action(act) {} Isq3YY
// all the operator overloaded 9Ao0$|@b
} ; l<<G".?
^qpa[6D6x
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 vOYcS$,^X%
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: .js4)$W^
-;$+`<%
template < typename Right > UQ|zSalv,
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const F"a^`E&
{ PVO9KWv**
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); *$(=I6b
} $Z;HE/3
<$liWAGX\
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > 5iola}6
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 < %Qw
dEO
> qA5
template < typename T > struct picker_maker
w'=#7$N
{ V mQ7M4j*
typedef picker < constant_t < T > > result; #SY8Zv
} ; PF .sM(
template < typename T > struct picker_maker < picker < T > > ~H0~5v F
{ #e%.z+7I
typedef picker < T > result; aMTY{
} ; ]P0DPea
<.3@-z>w2,
下面总的结构就有了: tC+9W1o
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 b*Ipg8n+
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 -<#n7b
picker<functor>构成了实际参与操作的对象。 i7~oZ)w
至此链式操作完美实现。 ej,MmLu~^
NrvS/cI!t
}wR)p
七. 问题3 ZLvw]N&R
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 4x'^?0H@
1elx~5v1.=
template < typename T1, typename T2 > =nnS X-x
??? operator ()( const T1 & t1, const T2 & t2) const yh_s(>sh
{ I#l9
return lt(t1, t2) = rt(t1, t2); %9mCgHQ9
} OxF\Hm)(
ZNB*Azi
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: +2oZB]GPL
9BANCW"
template < typename T1, typename T2 > HkvCQ H
struct result_2 X_
>B7(k
{ ^OG^%
x"
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; @n(=#Q3
} ; >1ZMQgCG
cXJgdBwo
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? _0F6mg n
这个差事就留给了holder自己。 IJ,,aCj4g
MbnV5 b:X
zi>f436-
template < int Order > 62EJ# q[
class holder; [ur/`
template <> mC~W/KReA
class holder < 1 > ~Y)Au?d(a
{ 3|:uIoR{
public : \)BKuIP
template < typename T > B_cn[?M
struct result_1 B_5q}Bp<
{ D~f.)kkC4
typedef T & result; =|3L'cDC
} ; 0nie>
template < typename T1, typename T2 > D3.sR\Hxf
struct result_2 %n}.E304
{ BpP\C!:^
typedef T1 & result;
=hl-c
} ; f| N(~
template < typename T > }Tc)M_
typename result_1 < T > ::result operator ()( const T & r) const `"ie57-
{ 4kXx(FE
return (T & )r; 1Y9Ye?~jd
} {bETHPCf
template < typename T1, typename T2 > zm8m J2s
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const %aw/Y5
{ tDN-I5q
return (T1 & )r1; !y] Y'j
} ZQBo|8*
} ; uaDU+ywL
#gN{8Yk>
template <> ]Vwky]d
class holder < 2 > Zt!l3(*tt
{ dN*<dz+4r
public : +}+hTY$a
template < typename T > WZO#(eO`
struct result_1 bkOm/8k|4
{ 5 #kvb$97
typedef T & result; !d(!1fC
} ; 5h{Hf]A
template < typename T1, typename T2 > LnJ7i"Q
struct result_2 coLn};W2
{ 0>e>G (4(8
typedef T2 & result; P;_dilG
} ; jB1\L<P
template < typename T > 9q8
rf\&
typename result_1 < T > ::result operator ()( const T & r) const |x5w;=
{ W'
2)$e
return (T & )r; [\.>BK
} -x_iqrB
template < typename T1, typename T2 > >8AtT=}w
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 8dZH&G@;
{ zIAMM
return (T2 & )r2; O3BU.X1'%
} to?"{
} ; hXrvb[6
pP/o2
#ASu
SQ
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 lmc-ofEv
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: 8v6rS-iHP
首先 assignment::operator(int, int)被调用: 57MoO
AT9SD vJ
return l(i, j) = r(i, j); EEo+#
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) .A `:o
blPC"3}3Vd
return ( int & )i; Ol-'2l
return ( int & )j; h">X!I
最后执行i = j; h=U 4
可见,参数被正确的选择了。 +_}2zc4
<1LuYEDq
qnm9Lw#
3}gK`1Nq1
AN1bfF:C
八. 中期总结 z`2d(KE?
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: kt:%]ZZL
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 6?iP z?5
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 -'VT
3。 在picker中实现一个操作符重载,返回该functor :|A db\b
e.kt]l
{r}}X@|5
v}mmY>M%
c]&VUWQ
W2B=%`sC
九. 简化 *Xnq1_K}
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 ?-Z:N`YP
我们现在需要找到一个自动生成这种functor的方法。 KWH
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: Arv8P
P^'
1. 返回值。如果本身为引用,就去掉引用。 !'MD8
+-*/&|^等 nc{<v
2. 返回引用。 hWu)0t
=,各种复合赋值等 3gh^a;uC
3. 返回固定类型。 OlJj|?z$
各种逻辑/比较操作符(返回bool) ]a%Kn]HI&2
4. 原样返回。 "|%fAE
operator, E4.IS=4S
5. 返回解引用的类型。 UmuFzw^
operator*(单目) fh3
6
6. 返回地址。 $3Ia+O
operator&(单目) gc:>HX);)
7. 下表访问返回类型。 c8s/`esA
operator[] od fu7P_
8. 如果左操作数是一个stream,返回引用,否则返回值 NEH$&%OV?
operator<<和operator>> y$"L`*W
N{yZk"fq:6
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 qprOxP
r
例如针对第一条,我们实现一个policy类: 8UcT?Zp
|Wgab5D>V
template < typename Left > ?C{N0?[P-
struct value_return ZM.g+-9
{ f$'D2o, O
template < typename T > Y|~>(
struct result_1 [)u(\nfGX
{ F{+`F<r
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; b#U%aPH
} ; /km3L7L%R
*X-$*
~J0
template < typename T1, typename T2 > ;CZcY] ol
struct result_2 BYf"l8^,
{ 7EXmmB~>,
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; /{va<