一. 什么是Lambda @v/Ae_q!
所谓Lambda,简单的说就是快速的小函数生成。 a[!:`o1U
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, 3ox|Mz<aZX
h:z$uG
daQJ{Cd,w
uAk>VPuuZ
class filler ?6MUyH]a
{ 9I1`* 0A
public : gI Gi7x
void operator ()( bool & i) const {i = true ;} KAr5>^<zw
} ; 4>HQ2S{t
vsq
|m5
+f^|Yi
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: 4*q6#=G
VjiwW%UOM
\)g}
RM25]hx
for_each(v.begin(), v.end(), _1 = true ); =G 'c %
;Q5o38(
UD2l!)rW
那么下面,就让我们来实现一个lambda库。 _*t75e$-
H5gcP11r
`[_p,,}Ir
`Z2-<:]6&a
二. 战前分析 S*ie$}ZX
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 =}+xD|T
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 WZbRR.TxO
8*]dAft
V-dub{K
for_each(v.begin(), v.end(), _1 = 1 ); Djp;\.$(
/* --------------------------------------------- */ W>u$x=<T
vector < int *> vp( 10 ); Fcn@j#[J
transform(v.begin(), v.end(), vp.begin(), & _1); &D7Mv5i0@
/* --------------------------------------------- */ =AuxMEg
sort(vp.begin(), vp.end(), * _1 > * _2); u$"Ew^C
/* --------------------------------------------- */ ^w
jM u5f
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); )b|xzj @
/* --------------------------------------------- */ m\ @Q}
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); `7 Nk;
/* --------------------------------------------- */ !,DA`Yt
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); Qz<i{r-z
%W2
o`W$
S)^eHuXPI
jyRz53
看了之后,我们可以思考一些问题: ch/DBu
1._1, _2是什么? 'L%)B-,n
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 c#fSt}J>C
2._1 = 1是在做什么? - l0X]&Ex
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 <Um 5w1
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 cw~-%%/
Ige*tOv2
dhr-tw
三. 动工 llpgi,-=
首先实现一个能够范型的进行赋值的函数对象类: r)dXcus
T'14OU2N{Y
(6)X Fp&
"(;t`,F
template < typename T > ;Z&w"oSJ
class assignment 7C@m(oK
{ *.-qbwOg
T value; .`h:1FP8
public : +L=a\8Ep
assignment( const T & v) : value(v) {} 2
3A)^j
template < typename T2 > S<++eu
T2 & operator ()(T2 & rhs) const { return rhs = value; } sFRQFX0XoY
} ; uX&Tn1Kg
7I:<i$)V
vPu{xy
其中operator()被声明为模版函数以支持不同类型之间的赋值。 4+N9Ylh
然后我们就可以书写_1的类来返回assignment ,LDdL
#4^D'r>pJ
~H626vT37
)dRBI)P
class holder <TEDs4
C
{ };~I#X
public : YD;"_yH
template < typename T > v<]$,V]
assignment < T > operator = ( const T & t) const 9E
{ |
Fk9ME
return assignment < T > (t); 8ao>]5Rs3
} ztaSIMZ
} ; ^ Mq8jw(2
P)06<n1">Z
%T~LK=m
由于该类是一个空类,因此我们可以在其后放心大胆的写上: +?C7(-U>
N6/;p]|
static holder _1; wgKM6?
Ok,现在一个最简单的lambda就完工了。你可以写 $"{I|UFC
X}]g;|~SN
for_each(v.begin(), v.end(), _1 = 1 ); FzQ6UO~'
而不用手动写一个函数对象。 [mG:PTK3
' "o2;J)7
24d{ol)
@Yzb6@g"
四. 问题分析 !u%XvxJwDb
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 I!g+K
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 Vs&Ul6@N
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 4]ETF+
3, 我们没有设计好如何处理多个参数的functor。 q<Wz9lDMNR
下面我们可以对这几个问题进行分析。 2!6-+]tC
Q|W~6
五. 问题1:一致性 RjG=RfB'V
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| /8s>JPXKH[
很明显,_1的operator()仅仅应该返回传进来的参数本身。 0/b3]{skK
qfB!)Y
struct holder G\H |\i
{ K]Z];C#)
// 2~W8tv0^b2
template < typename T > |F?/L>
T & operator ()( const T & r) const `&o>7a;
{ d2<+Pp
return (T & )r; )gKX+'
} A!aki}aT~
} ; 3rVWehCv
kntn9G
这样的话assignment也必须相应改动: "v5jYz5M
9rM6kLD
template < typename Left, typename Right > 7!#34ue
class assignment 9
IY1"j0O
{ |F52)<\
Left l; C3e0d~C
Right r; #w]@yL]|is
public : ;Qdw$NuW
assignment( const Left & l, const Right & r) : l(l), r(r) {} Te&5IB-
template < typename T2 > :pg]0X;
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } *d,Z?S/
} ; FKkL%:?
{{e+t8J??
同时,holder的operator=也需要改动: \PgMMc4'
U
jB5Xks
template < typename T > U:O&FE
assignment < holder, T > operator = ( const T & t) const "A3V(~%!
{ G}gmkp]z
return assignment < holder, T > ( * this , t); H!uq5`j0K
} kZH IzU
Nmu=p~f}3`
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 ,~qjL|9
你可能也注意到,常数和functor地位也不平等。 tJZ3P@ L
g7<u eF
return l(rhs) = r; #(Ezt% ^
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 2/#%^,Kb2
那么我们仿造holder的做法实现一个常数类: g.eMGwonTJ
C!S(!Z,
template < typename Tp > Tyt1a>!qA
class constant_t JAP4Vwj%j
{ {x/)S*:Z
const Tp t; =9cN{&qf
public : .
I#dR*
constant_t( const Tp & t) : t(t) {} !6DH6<HC
template < typename T > !ZTBiC5R
const Tp & operator ()( const T & r) const 3q:>NB<
{ Bq#B+JwX
return t; RI-)Qx&!f
} ?UV!^w@L:0
} ; f|-%.,
*S{fyYyM
该functor的operator()无视参数,直接返回内部所存储的常数。 WeRX ~
下面就可以修改holder的operator=了 gC\^"m
h(3ko
An
template < typename T > D;WQNlTU
assignment < holder, constant_t < T > > operator = ( const T & t) const Q
a8;MxK`
{ Dro2R_j{
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); KPMId`kf
} 1JSKK.LuJV
8+OcM
;0
同时也要修改assignment的operator() c:sk1I,d~^
>Yt+LdG!-
template < typename T2 > @6:J$B~)u
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } $z* Y:vFP
现在代码看起来就很一致了。 a) 5;Od
Vo:Gp
六. 问题2:链式操作 =hDFpb,mr
现在让我们来看看如何处理链式操作。 |sklY0?l(
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 sj\kp
ni
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 )-_To&S*
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 $kCLS7 *
现在我们在assignment内部声明一个nested-struct [nG@
3n
%SlF7$
template < typename T > B_#U|10et
struct result_1 c6f[^Q%#j
{ "`8~qZ7k
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; ju {\7X5
} ; }KCb5_MDF
3lD1G~
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: |\_d^U&`
fPu,@
L
template < typename T > ^TCgSi7k`L
struct ref qJPEq%'Q
{ w.6 Gp;O
typedef T & reference; z]O,Vqpl?
} ; QpC,komLJ
template < typename T > .cA'6J"Bm\
struct ref < T &> ;E]^7T
{ GtSvb6UNn
typedef T & reference; >xJh!w<pB
} ; =%+o4\N,
etkKVr;Kv
有了result_1之后,就可以把operator()改写一下: +1Ua`3dWN_
-P'KpX:]hd
template < typename T > i#W0
typename result_1 < T > ::result operator ()( const T & t) const l&LrcM
{ hAv.rjhw_
return l(t) = r(t); _k2*2db
} nFY6K%[
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 VQ((c:+!
同理我们可以给constant_t和holder加上这个result_1。 /WWD;keP5
:Mq-4U.e
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 q=(.N>%
_1 / 3 + 5会出现的构造方式是: 5<?s86GHh'
_1 / 3调用holder的operator/ 返回一个divide的对象 kz+OUA@~
+5 调用divide的对象返回一个add对象。 ;&v~tD7
最后的布局是: ri?>@i-9=
Add 3'D<'S}[
/ \ $^;b
1bnO
Divide 5 /,m!SRJ
/ \ 3A>Bnb
_1 3 <qpDAz4k
似乎一切都解决了?不。 ap[{`u
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 j9G1
_
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 a2tRmil
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: :`w'}h7m
mFdj+ &2\
template < typename Right > eH9Ofhsry
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const /<WK2G
Right & rt) const ="*:H)
{ i1E~ F
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); f R?Xq@c
}
x."/+/
下面对该代码的一些细节方面作一些解释 bO2s'!x
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 ohPCYt
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 q V+gQ
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 D3BT>zTGK
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 d5O_~xf&
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? rbw5.NU
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: JL1z8Nu
eub2[,
template < class Action > bm:"&U*tu'
class picker : public Action jx7b$x]
{ [^4)3cj7}
public : '**dD2
n
picker( const Action & act) : Action(act) {} .3QX*]{
// all the operator overloaded ,-GkP>8f(
} ; Ja@zeD)f"
wQV[ZfU^h
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 6bXR?0$*M.
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: WzwH;!
QSxR@hC
template < typename Right > 3w-0IP]<
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const $V0G[!4
{ Bl"BmUn
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); tin5.N)"z
} ra4$/@3n
2sryhS'(H
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > iE;D_m.>`O
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。
!8V
v.Y?<=E+<d
template < typename T > struct picker_maker ~;#OQ[
{ RMfKM!
vE
typedef picker < constant_t < T > > result; )=vQrMyB
} ; 'q_^28rK
template < typename T > struct picker_maker < picker < T > > bI_T\Eft
{ R
rtr\a
typedef picker < T > result; yD-L:)@"
} ; C=&rPUX{
UHh7x%$n
下面总的结构就有了: c\\'x\J7
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 BS_ 3|
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 AJ0
;wx
picker<functor>构成了实际参与操作的对象。 |pA
至此链式操作完美实现。 g$N/pg2>cT
[10y 13
nbECEQ:|B
七. 问题3 dpPu&m+
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 1YrIcovi-
ZVin+ z
template < typename T1, typename T2 > +6$ |No
??? operator ()( const T1 & t1, const T2 & t2) const 'fGB#uBt
{ $gv3Up"U
return lt(t1, t2) = rt(t1, t2); jrl'?`O
} y|7sh
~.*G%TW &V
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: @3Lh/&
Duu)8ru
template < typename T1, typename T2 > +=:*[JEK,U
struct result_2 ;;zQV D )X
{ ,_N+t:*#0
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; pmIOV~K
} ; {|E'
wIbxnn
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? \@}G'7{
这个差事就留给了holder自己。 fy6<KEea
NZTG)<
k"z ~>
template < int Order > s)L\D$;+O
class holder; t{ R\\j
template <> <U]!1
class holder < 1 > qq,#bRe
{ 5!b+^UR;z
public : bl8EzO
template < typename T > FkH HTO
struct result_1 dx&!RK+
{ P"%QFt,
typedef T & result; 8nj^x?bn
} ; `Q@w*ta)
template < typename T1, typename T2 > .T63:
struct result_2 Vx<`6uv
{ XB.xIApmy
typedef T1 & result; Nf!g1D"U
} ; {PTB]D'
template < typename T > L2,.af6+
typename result_1 < T > ::result operator ()( const T & r) const Ki,SFww8r
{ >]!8f?,
return (T & )r; cUH.^_a
} WCdl 25L#
template < typename T1, typename T2 > o
_G,Ph!7
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const aWCZ1F
{ M&v;#CV
return (T1 & )r1; j TyR+#Wn
} ?^Q8#Y^M
} ; %2;Nj;
J$
+I$,Y~&`>
template <> ){I0
class holder < 2 > (^@rr[.o7
{ d:X@zUR*)
public : X"k:+
template < typename T > u{'|/g&
struct result_1 ].Sz2vI
{ X7g@.Oy`
typedef T & result; AL;z's(F?
} ; \`:nmFO(9
template < typename T1, typename T2 > n6xJ
struct result_2 HVHd@#pDZ
{ RDSkFK( D
typedef T2 & result; {O=PVW2S
} ; q?*
z<)#
template < typename T > z8@[]6cW
typename result_1 < T > ::result operator ()( const T & r) const K7-z.WTUR
{ 8)o%0#;0B
return (T & )r; J85S'cwZZ
} 0Xw$l3@N^
template < typename T1, typename T2 > T2ZB(B D
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const Dx5X6 t9=
{ +e87/\5
return (T2 & )r2; 4aGVIQ
} ;xl0J*r
} ; \V_Tc`
hjgB[
&U>
W<@9ndvH
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 Nrn_Gy>|D
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: ;Zy[2M
首先 assignment::operator(int, int)被调用: q21l{R{Y
QMhvyzkS
return l(i, j) = r(i, j); 5<>"d :9
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) t+ vz=`
A`:a
T{j
return ( int & )i; W5Uw=!LdEY
return ( int & )j; =o5|W'>`
最后执行i = j; `PUGg[Zx^
可见,参数被正确的选择了。 UasU/Q <
W>j@E|m$
t}YT+S
&e6!/y&
^?8/9o
八. 中期总结 ;EB^1*AEw
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: `oU|U!|
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 dLfB){>S
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 KK}ox%j
3。 在picker中实现一个操作符重载,返回该functor kK|D&Xy`
B2,c_[UZ.
q|g>;_
8CUlE-R5
3oOr*N3R
-.OZ
九. 简化 3c=>;g
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 6]sP"
我们现在需要找到一个自动生成这种functor的方法。 `k6ZAOQtX
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: .Im=-#EN
1. 返回值。如果本身为引用,就去掉引用。 "U-dw%b}b
+-*/&|^等 }0IeKpu5
2. 返回引用。 B#G:aBCM
=,各种复合赋值等 mt]^d;E
3. 返回固定类型。 |[)n.N65=
各种逻辑/比较操作符(返回bool) Y:R*AOx
4. 原样返回。 ni85Ne$
operator, IG Ax+3V
5. 返回解引用的类型。 }a%1$>sj
operator*(单目) GO)5R,
6. 返回地址。 $Jo4n>/
operator&(单目) ph$vP;}
7. 下表访问返回类型。 bO` SBq$
operator[] hXh nJ
8. 如果左操作数是一个stream,返回引用,否则返回值 ALQ-aXJ
operator<<和operator>> {2)).g
P~M[i9 V
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 1,(WS
F
例如针对第一条,我们实现一个policy类: ,M9e *
bq2f?uD-}
template < typename Left > FeZ*c~q
struct value_return Za,myuI+
{ \ZA@r|=$
template < typename T > L54]l^ls>
struct result_1 2){O&8 A
{ PJYUD5
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; wF9L<<&B
} ; O6ph_$nt.
9:*[Q"v
template < typename T1, typename T2 > 6>]w1
H
struct result_2 ;0U*N &
f
{ HbRvU}C1
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; >6R3KJe
} ; r
)HZaq
} ; pm=m~
.8->n aj|
J&iSS9c
其中const_value是一个将一个类型转为其非引用形式的trait #aQQd8
uM\5GK
下面我们来剥离functor中的operator() f^ja2.*%?
首先operator里面的代码全是下面的形式: a^8PB|G
L~%7=]m
return l(t) op r(t) %!r.)Wx|2
return l(t1, t2) op r(t1, t2) pC]XbokES
return op l(t) Re2&qxE
return op l(t1, t2) Qvty;2$o@
return l(t) op T 5F)
return l(t1, t2) op %fnG v\uI
return l(t)[r(t)] !6l*Jc3
return l(t1, t2)[r(t1, t2)] (g*j+i
):[}NDmC
很自然的,我们会想到用函数替代这种操作符行为以获得更加一致的形式: p|(SR~;6
单目: return f(l(t), r(t)); v;`>pCal
return f(l(t1, t2), r(t1, t2)); VEp cCK
双目: return f(l(t)); tY>Zy1hlI
return f(l(t1, t2)); v[2&0&!K#
下面就是f的实现,以operator/为例 qX*xQA|ak,
wTD}c1J(
struct meta_divide RRXp9{x`
{ 51u\am'T
template < typename T1, typename T2 > yM `u]p1
static ret execute( const T1 & t1, const T2 & t2) rvlvk"
{ 9;'#,b*(
return t1 / t2; IJ~j(.W
} |RXQ_|
} ; _ !E&