一. 什么是Lambda WhPwD6l>
所谓Lambda,简单的说就是快速的小函数生成。 =W+ h.?
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, /u
hA\m(
uu08q<B5b)
TL^af-
nR%ASUx:Y
class filler 06hzCWm#
{ S
b0p?
public : ,'=Tf=wq
void operator ()( bool & i) const {i = true ;} CM$q{;y
} ; sK1YmB :~a
oWCy%76@
QGv$ ~A[h
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决:
D,cGW,2Nv
Kob i!
Af*e:}}
rByC6HV"
for_each(v.begin(), v.end(), _1 = true ); 6yDc4AX
pwj ?
w5j6RQml
那么下面,就让我们来实现一个lambda库。 #&Xr2?E@
Y&vn`#
RM^3Snd=V
H{XbKLU
二. 战前分析 E0F8FR'
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 P''5A6#5
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 2oY.MQD7iW
4J #F;#iA
PwF
1Pr`r
for_each(v.begin(), v.end(), _1 = 1 ); <d2?A}<
/* --------------------------------------------- */ (~C_zG
vector < int *> vp( 10 ); W6N3u7mrb
transform(v.begin(), v.end(), vp.begin(), & _1); '.Ww*N
/* --------------------------------------------- */ +w'"N
sort(vp.begin(), vp.end(), * _1 > * _2); !_zp'V]?
/* --------------------------------------------- */ U)v['5%
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); ~|W0+ &):
/* --------------------------------------------- */ $!~R'N c
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); !Q-h#']~L
/* --------------------------------------------- */
VL^.7U
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); kzMul<>sl
h6Femis
/(/Z~J[
U<T.o0s=
看了之后,我们可以思考一些问题: )Dg;W6
1._1, _2是什么? .Vohd@s9l
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 0?DD!H)&w
2._1 = 1是在做什么? 5AX
AIP n)
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 |I; tBqN{u
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 />wM#)o2
"6[a%f#Q
)<J|kC\r6c
三. 动工 j`fQN
首先实现一个能够范型的进行赋值的函数对象类: ll]MBq
KKrLF?rc
:5Y
yI.T
wR7Ja
cKv
template < typename T > C*+gQeK
class assignment }}R?pU_
{ )@vhqVv?
T value; &sFEe<
public : =[N=mC
assignment( const T & v) : value(v) {} x,CTB
template < typename T2 > *u?QO4>
T2 & operator ()(T2 & rhs) const { return rhs = value; } 2#<)-Cak
} ; R?%J
h=:*cqp4
AXnuXa(j
其中operator()被声明为模版函数以支持不同类型之间的赋值。 FU{$oCh/5
然后我们就可以书写_1的类来返回assignment *wH.]$
I:~KF/q
goE \C
{B!LhvYAH
class holder H@+1I?l
{ K;:_UJ>t
public : 2)iwAu
template < typename T > :i{Svb*_'
assignment < T > operator = ( const T & t) const -<g&U*/E
{ oFO)28Btv
return assignment < T > (t); r JvtE}x1
} OouIV3
} ;
11'^JmKA
JAQ y
S.<aCN<@
由于该类是一个空类,因此我们可以在其后放心大胆的写上: a#huK~$~
>yZe1CP
static holder _1; a Uy!(Y
Ok,现在一个最简单的lambda就完工了。你可以写 w5C$39e\G
m;_gNh8 Ee
for_each(v.begin(), v.end(), _1 = 1 ); >)Udb//
而不用手动写一个函数对象。 6Kvo Ho
lx'^vK% F
} @)r\t4m
Li'>pQ+
四. 问题分析 ~pZ<VH;h
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 _/Sqw
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 xj ?#]GR
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 ^"\3dfzKM
3, 我们没有设计好如何处理多个参数的functor。 0[# zn
下面我们可以对这几个问题进行分析。 _#dBcEH[
J]!&E~Y
五. 问题1:一致性 VW$a(G_h
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| Gu#Vc.e
很明显,_1的operator()仅仅应该返回传进来的参数本身。 9wTN*y
jkQ%b.a
struct holder y[D8r Fw
{ z[cs/x
// c\Z.V*o
template < typename T > Y94^mt-
T & operator ()( const T & r) const s~z~9#G(6
{ }&*wJ]j`L
return (T & )r; *(,zPn,
} 5[[mS
} ; ]ZMFK>"^%
~E8L,h~
这样的话assignment也必须相应改动: #JAy
eP?=tUB!S
template < typename Left, typename Right > {4y#+[
class assignment ?W3l
{ #VvU8"u
Left l; } SNZl`>
Right r; xg^Z. q)d
public : O)aWTI
assignment( const Left & l, const Right & r) : l(l), r(r) {} Ah?,9r=U
template < typename T2 > ^t$xR_
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } @^2?97i
c
} ; O x),jc[/
{vhP'!a6W
同时,holder的operator=也需要改动: > u!#
4
U.GRN)fL4
template < typename T > yrF"`/zv6|
assignment < holder, T > operator = ( const T & t) const SSAf<44e
{ hr/H vB
return assignment < holder, T > ( * this , t); Y'{F^VxA/
} W"v"mjYud
^.pd'
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 +_T`tmQ
你可能也注意到,常数和functor地位也不平等。 lz [s
W{is 2s
return l(rhs) = r; }eK.\_t=
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 8Y,imj\(v
那么我们仿造holder的做法实现一个常数类: xU!eT'Y
0! W$Cz[
template < typename Tp > mm:g9j
class constant_t ;ztt*py
{ W^k|*Y|
const Tp t; *}P=7TuS
public : 3F gTM(
constant_t( const Tp & t) : t(t) {} CX}==0od
template < typename T > $<s;YhM:u)
const Tp & operator ()( const T & r) const bzWWW^kNL
{ %B~@wcI)W
return t; Ncr*F^J4
} YAsE,M+
} ; =j~vL`d2]
TF%MO\!
该functor的operator()无视参数,直接返回内部所存储的常数。 ;{Nc9d
下面就可以修改holder的operator=了 |[W7&@hF
5hvg]w95;
template < typename T > >+FaPym
assignment < holder, constant_t < T > > operator = ( const T & t) const sqEOXO
{ =L]GQ=d
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); 61~7 L^882
} m#,AD,s
\|YIuzlO4
同时也要修改assignment的operator() n)uck5
'Z8=y[l
template < typename T2 > #8/pYQ;
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } V^%P}RFMc
现在代码看起来就很一致了。 7t3ps
DLH|y%"
六. 问题2:链式操作 vACJE
现在让我们来看看如何处理链式操作。 V%Ww;Ca]I
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 :[J'B4>9
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 mv{bX|.
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 G -V~6
现在我们在assignment内部声明一个nested-struct [:(hqi!
T&nIH[}v
template < typename T > ".7\>8A#a
struct result_1 D$U`u[qjtS
{ Pk{%2\%&2
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; d#CAP9n;'
} ; ^N&@7s
X]4j&QB
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: WD >z
dvu8V_U
template < typename T > 4q )+nh~s
struct ref t`")Re_j
{ cd(YH! 3
typedef T & reference; Q#5~"C
} ; ;J,`v5z0:
template < typename T > 7V2xg h!W
struct ref < T &> awl3|k/
{ }0}=-g&
typedef T & reference; b!JrdJO,DP
} ; 'Bwv-J
x
K ;#C
有了result_1之后,就可以把operator()改写一下: 3_ ZlZ_Tq
[tk6Kx8a
template < typename T > .$ X|96~$
typename result_1 < T > ::result operator ()( const T & t) const WRp0.
{ }u]7 x:lh
return l(t) = r(t); KP&$Sl
} =`ECM7
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 |@BX*r
同理我们可以给constant_t和holder加上这个result_1。 rcz9\@M
vMzBp#MT
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 i :|e#$x
_1 / 3 + 5会出现的构造方式是: UuCRQN H
_1 / 3调用holder的operator/ 返回一个divide的对象 2QgD<
+5 调用divide的对象返回一个add对象。 ^Rb*mI
最后的布局是: >0JCu^9
Add ;R]~9Aan
/ \ Al+}4{Q+?
Divide 5 z#B(1uI
/ \ d*_rJE}B
_1 3 l?B=5*0
似乎一切都解决了?不。 joBS{]
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 E1s~ +
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 vP%}XEF
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: <-DQ(0xg
no(or5UJ
template < typename Right > @~bP| a
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const LT#EYnG
Right & rt) const }=d}q *
{ cHC4Y&&uZ
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); 8RT<?I^5
} Gdz*
下面对该代码的一些细节方面作一些解释 p$}/~5b}4
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 zvn3i5z
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 l:~/%=
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 P~;1adi3
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 "hnvND4=
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? /\MkH\zg
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: 8?1MnjhX10
6^)eW+
template < class Action > 1<Vke$
class picker : public Action q1Ad"rm
{ 2(f-0or(
public : z@?WhD
picker( const Action & act) : Action(act) {} *).!
// all the operator overloaded yN/g;bQ
} ; ]wwN mmE
Vqr]Ui
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 ar_@"+tZ
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: jLn|zK
DWS#q|j`"
template < typename Right > YjiMUi\V
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const 2U3e!V
{ eV"s5X[$
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); (}rBnD
} Sd/7#
vxS4YR b
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > *D67&/g.
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 A8g_BLj!e
qJE_4/<^!
template < typename T > struct picker_maker `Hqgahb{P
{ 1p8pH$j'
typedef picker < constant_t < T > > result; S`Z[MNY
} ; NA$%Up
template < typename T > struct picker_maker < picker < T > > 6xFchdMG{m
{ Dutc#?bT
typedef picker < T > result; PZVH=dagq
} ; B`YD>oCN
CwD=nT5`
下面总的结构就有了: -2j[;kgt}
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 s4j]kH
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 ?6UjD5NkX
picker<functor>构成了实际参与操作的对象。 9&{z?*
至此链式操作完美实现。 Vha,rIi
)q`.tsR>
-EP(/CS!
七. 问题3 0\Tp/Ph
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 xo4lM
v\E6N2.S
template < typename T1, typename T2 > Zs8]A0$
??? operator ()( const T1 & t1, const T2 & t2) const i-9W8A
{ jX0^1d@
return lt(t1, t2) = rt(t1, t2); +BDW1%
} $)$_}^.k
I+(
b!(H
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: E;,__
-d-xsP}
s
template < typename T1, typename T2 > Q.fUpa v
struct result_2 raZkH8
{ _5S||TuNS
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; [930=rF*
} ; N) PkE>%X
9z`72(
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? .<Ays?
这个差事就留给了holder自己。 ?vFtv}@\
eaDR-g"
mDk6@Gd@U
template < int Order > {pdPp|YDZ-
class holder; U "r)C;5
template <> ;NQ}c"9
class holder < 1 > ky&wv+7
{ o_BRsJy
public : #=)!\
template < typename T > dc0&*/`:
struct result_1 V5p^]To!
{ K{, '%|
typedef T & result; j3H_g^
} ; z]KJ4
template < typename T1, typename T2 > s>W :vV@
struct result_2 * U}-Y*
{ eSHsE3}h
typedef T1 & result; {|<yZ,,p
} ; xel|,|*Yq
template < typename T > 5V~vND*
s
typename result_1 < T > ::result operator ()( const T & r) const 'h^Ya?g
{ *3]2vq
return (T & )r; Kzz/]
} e*}:tH
template < typename T1, typename T2 > ysPm4am$
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const l *{Bz5hc
{ HCCq9us
return (T1 & )r1; S}cR+d1}h
} ~2nt33"
} ; SurreD<x
?:&2iW7z
template <> @^DVA}*b)
class holder < 2 > (5CgC<
{ =>kg]
public : KYwUkuw)
template < typename T > +XSe;xk;rD
struct result_1 aXzb]">
{
?!<Q8=
typedef T & result; 7yXJ\(6R_
} ; lMG+,?<uK&
template < typename T1, typename T2 > 1GIBqs~-
struct result_2 X&h?1lMJ /
{ n).*=YLN
typedef T2 & result; KUq7O a!
} ; )wXE\$
template < typename T > ti$60Up
typename result_1 < T > ::result operator ()( const T & r) const ;nJ2i?"
{ .C&kWM&j
return (T & )r; <lNNT6[/r
} $|7=$~y
template < typename T1, typename T2 > X|/RV4x@Cq
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const Ptcq/f
{ f mJK+
return (T2 & )r2; cr|]\
} CU*TY1%
} ; t)uxW
7
kr@!j@j$
=v'Aub
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 N8k=c3|
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: V#|/\-@
首先 assignment::operator(int, int)被调用: G Y.iCub
&