一. 什么是Lambda yf[~Yl>Ogw
所谓Lambda,简单的说就是快速的小函数生成。 ;$smH=I
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, {OXFN;2
,q}MLTSi
H@q?v+2
\6R,Nq
class filler w8MG(Lq1"
{ t.7?
public : \/: {)T~
void operator ()( bool & i) const {i = true ;} k< y>)
} ; \.-}adKg
.NYbi@bk(<
-I&m:A$4*
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: )%`^xR
k@/sn(x
fh](K'P#^
,.kha8v
for_each(v.begin(), v.end(), _1 = true ); / c AUl
8=NM|i
_F$aUtb%O
那么下面,就让我们来实现一个lambda库。 /ro=?QYb
Bj1?x
yXHUJgjl/
0:9.;x9_
二. 战前分析 I@yCTluV$
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 %-c*C $
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 ,N!o
9s6U}a'c
B56L1^7
for_each(v.begin(), v.end(), _1 = 1 ); (O.d>
/* --------------------------------------------- */ >`A9[`$n
vector < int *> vp( 10 ); ;#vKi0V7
transform(v.begin(), v.end(), vp.begin(), & _1); e[&L9U6GW-
/* --------------------------------------------- */ FaDjLo2'o
sort(vp.begin(), vp.end(), * _1 > * _2); 5N/%v&1
/* --------------------------------------------- */ L.S;J[a;
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); `$W_R[
/* --------------------------------------------- */ VJickXA
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); ki?S~'a
/* --------------------------------------------- */ l'/R&`-n
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); *>n;SuT_
\=:~ki=@B
HY&aV2|A1
-jb0o/:
看了之后,我们可以思考一些问题: +
HK8jCa
1._1, _2是什么? 7"20hAd
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 %oZ6l*
2._1 = 1是在做什么? pe] A5\4c
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 Ji>o!
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 w5A y)lz
E\as@pqo\p
G Uon/G8
三. 动工 bN]+_ mF
首先实现一个能够范型的进行赋值的函数对象类: |wiqGzAr{
i rU 6D
vms|x wb
xv(9IEjt0
template < typename T > BK)$'AqO
class assignment Sjvdirr
{ . 1KhBgy^K
T value; >qS9PX
public : 1FlX'[vh
assignment( const T & v) : value(v) {} ++6`sMJ
template < typename T2 > }1Gv)l7
T2 & operator ()(T2 & rhs) const { return rhs = value; } kYG/@7f/
} ; wO'TBP
@k,z:~[C=
>O*IQ[r-
其中operator()被声明为模版函数以支持不同类型之间的赋值。 iV'k}rXC
然后我们就可以书写_1的类来返回assignment 6-z%633DL
D8Ykg >B;&
B@&4i?yJ
fZ0M%f
class holder $c0h.t
{ NidIVbT.A
public : [x+FcXb
template < typename T > QEz?w}b*
assignment < T > operator = ( const T & t) const 7
n8"/0kc:
{
coW:DFX
return assignment < T > (t); oB}BU`-l
} yXSFjcoB
} ; l`oZ)?ur
X:HacYqtC
,}3
'I [
由于该类是一个空类,因此我们可以在其后放心大胆的写上: j[`j9mM8
63\/ *
NNB
static holder _1; `uOT+B%R
Ok,现在一个最简单的lambda就完工了。你可以写 d,+Hd2o^X
y0sR6TY)f
for_each(v.begin(), v.end(), _1 = 1 ); #M9~L[nFS
而不用手动写一个函数对象。 "W6uV!
B3We|oe !
OI|[roMK
U#lCj0iUt,
四. 问题分析 t^+ik1.
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 |iak z|])
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 ]<ldWL
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 l4F%VR4KT
3, 我们没有设计好如何处理多个参数的functor。 %|auAq&w
下面我们可以对这几个问题进行分析。 r)y=lAyF>
7''??X
五. 问题1:一致性 ((H^2KJn
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| '))0Lh
l
很明显,_1的operator()仅仅应该返回传进来的参数本身。 +ieY:H[
[%q@]\U$s
struct holder 6HT;#Znn
{ CDsSrKhx
// h;p>o75O
template < typename T > &5\iM^
T & operator ()( const T & r) const ;O,+2VzP%^
{ >" )Tf6zw&
return (T & )r; CyJEY-
} /5S30 |K
} ; gZN8!#h}B
]OM"ZG/^
这样的话assignment也必须相应改动: =$u!
59_dE
umjt]Gu[
template < typename Left, typename Right > ^]H5h ]U'
class assignment bGN:=Y'
{ gH$ Mr
Left l; Vx$ \hcG
Right r; 2<i!{;u$qL
public : X3{G:H0\p
assignment( const Left & l, const Right & r) : l(l), r(r) {} 6c}h(TkB
template < typename T2 > bp*
^z,w
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } +[M6X}
TQ
} ; FtpK)9/4
m,VOx7%n
同时,holder的operator=也需要改动: qyZ"
%Kz
M\o9I
template < typename T > C].iCxn
assignment < holder, T > operator = ( const T & t) const *QpMF/<?
{ \z>fb%YW
return assignment < holder, T > ( * this , t); /$i.0$L
} 3-[q4R
8NxM4$nQX
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 :y+2*lV
你可能也注意到,常数和functor地位也不平等。 34`'M+3
uW=k K0E
return l(rhs) = r; 2a-w%
(K
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 @'w"R/,n-@
那么我们仿造holder的做法实现一个常数类: c?tBi9'Y]
,`|3KE9
template < typename Tp > "7
4-4
class constant_t sGi"rg#
{ \RNNg
const Tp t; cA2V2S)
public : 9%k2'iV7
constant_t( const Tp & t) : t(t) {} aI%g2q0f
template < typename T > NokU)O ;x
const Tp & operator ()( const T & r) const KxI&G%z
{ n3T>QgK
return t; bk[U/9Z\
} *U^6u/iH
} ; {'NZ.
%<)2/|lCd
该functor的operator()无视参数,直接返回内部所存储的常数。 DjCqh-&L
下面就可以修改holder的operator=了 Qk0R a_
t=(!\:[D
template < typename T > 9`T)@Uj2n
assignment < holder, constant_t < T > > operator = ( const T & t) const ?274uAO'
{ #9B)Xx!g
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); BTlk
E tm
} Rvkedb
cW~}:;D4
同时也要修改assignment的operator() 6|K5!2
szb_*)k
template < typename T2 > fWCo;4<5?
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } ^Xuvy{TkPH
现在代码看起来就很一致了。 w~.f
~t@cO.c
六. 问题2:链式操作 :<ka3<0%
现在让我们来看看如何处理链式操作。 A|CmlAW~^
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 5 z~1Dw
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 N@;?CKU
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 !!qK=V|>
现在我们在assignment内部声明一个nested-struct b}OY4~ Y4
heltgRt
template < typename T > CWf /H)~
struct result_1 efSM`!%j
{ :Gv1?M
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; x[4`fM.m*
} ; qBU-~"2t
n?oW < &
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: Zvhsyz|
)r';lGh2#
template < typename T > PvR6
z0
struct ref T\:4qETQF]
{ _G_Cj{w
typedef T & reference; |$+3a
} ; Q0$8j-1I
template < typename T > E^Y#&skXp3
struct ref < T &> Bm.afsM;
{ [l:x'_y
typedef T & reference; |D'4uN8\
} ; -Btk 3
uvgdY
有了result_1之后,就可以把operator()改写一下: Pl(Q,e7O]
z_g~
template < typename T > 909?_v
typename result_1 < T > ::result operator ()( const T & t) const Gk967pC
{ 4p e'06:
return l(t) = r(t); K7$x<5 +)
} m 2-Sx
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 agkA}O
同理我们可以给constant_t和holder加上这个result_1。 &6DMk-
<CRP^_c
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 P<oehw'>
_1 / 3 + 5会出现的构造方式是: kSC}aN'
_1 / 3调用holder的operator/ 返回一个divide的对象 |
H!28h
+5 调用divide的对象返回一个add对象。 YX%[ipgB
最后的布局是: A+HF@Uw}^
Add rMXN[,|v
/ \ xrlmKSPa
Divide 5 Ok{*fa.PK
/ \ V=)_yIS
_1 3 ~0?mBy!-O
似乎一切都解决了?不。 4B=2>k
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 h
a|C&G
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 [N1hWcfvd
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: uB |Ss
_4TH4~cY
template < typename Right > v. %R}Pa
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const AoY-\E
Right & rt) const r`%+M7
{ iM2W]
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); 4!$s}V=6
} t'9*R7=
下面对该代码的一些细节方面作一些解释 El<]b7
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 F1 iGMf-8
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 'iy*^A `Y
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 0ph{
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 M@h|bN
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? OQ8 bI=?[x
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: FSU ttg"
GRMiQa
template < class Action > Jm|+-F@I
class picker : public Action ?!wgH9?8
{ x? ?pBhJH
public : Jwj%_<
picker( const Action & act) : Action(act) {} D*Ik7Pe
// all the operator overloaded >*@y8u*
} ; ^BUYjq%(`
n$U#:aQE
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 :q
ti
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: ub7zA!%
A;5n:Sd
template < typename Right > :1 (p.q=
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const @)-sTgn
{ Bt1p'g(V|
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); "oWwc
zzO
} J~B<7O<?!1
?gJOgsHJP
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > I6j$X 6u
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 p(PMZVV`
S5KEXnjm
template < typename T > struct picker_maker H_EB1"C;\
{ %ThyOl@O
typedef picker < constant_t < T > > result; *\(r+>*x*
} ; wUiys/OVM
template < typename T > struct picker_maker < picker < T > > !iH-#B-
{ N;Dni#tQ`
typedef picker < T > result; iv?gZg
} ; n8uv#DsdK
I&MY{f
下面总的结构就有了: u\LiSGePN
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 fLDg~;3
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 )'/|)
picker<functor>构成了实际参与操作的对象。 6lkl7zm
至此链式操作完美实现。 .fN"@l
&j?#3Qt'_
zrR`ecC(b
七. 问题3 w^L ta
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 gzBy?r> r
|u0(t,T
template < typename T1, typename T2 > AtU v71D:
??? operator ()( const T1 & t1, const T2 & t2) const 0VckocF
{ fGw^:,B
return lt(t1, t2) = rt(t1, t2); =`*O1a
} ZiYm:$CJ
"Vw m
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: t<T[h2Wd
U7!.,kR-
template < typename T1, typename T2 > !O.[PH(,*
struct result_2 -RO7
'm0
{ r|PFw6
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; /&CmO>^e
} ; /"
${$b{
1x@qkL6
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? gzjR6uz
这个差事就留给了holder自己。 rgSOS-ox
K TsgJ\W
7SlsnhpW
template < int Order > +Vo}F
class holder; "z0zpHXek
template <> OkCQ?]
class holder < 1 > 4l!@=qwn
{ ndjx|s)E
public : QCH}-q)
template < typename T > {K4+6p
struct result_1 :C}2=
{ 2<`.#zIds
typedef T & result; fV v.@HL{
} ;
vj51
g@
template < typename T1, typename T2 > yu6`66h)
struct result_2 -+7uy.@cS
{ ?lbH02P{v
typedef T1 & result; vKq^D(&cl
} ; |o2sbLp
template < typename T > 7_.11$E=H
typename result_1 < T > ::result operator ()( const T & r) const Aub]IO~
{ -b9;5eS!
return (T & )r; $we]91(::
} {/X4(;~0
template < typename T1, typename T2 > 4q'B<7{Q
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 2$14q$eb
{ c&X{dJWD
return (T1 & )r1; o\88t){/kB
} *[r!
} ; tG8jFou
Q\GDrdA
template <> K,6b3kk
class holder < 2 > N0K){
{ wO:Sg=,
public :
U3izvM
template < typename T > I=7Y]w=
struct result_1 QV h4
{ !eAo
typedef T & result; (x"BR
} ; *\wp?s>-t
template < typename T1, typename T2 > d{3@h+zL
struct result_2 oT{@_U{*J
{ QJ
F=UB
typedef T2 & result; 1=|7mehL%
} ; {^m(,K_
template < typename T > ?_oF :*~\
typename result_1 < T > ::result operator ()( const T & r) const [F_/2+e
{ ?E9D Xg
return (T & )r; &O)&k
} ?9HhG?_x
template < typename T1, typename T2 > RP2_l$
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const WpS1a440
{ &n[~!%(
return (T2 & )r2; rUlS'L;$"
} Cv>o.Bp|
} ; iweD
@b
'S<%Xm
L>!8YUz7p$
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 TDg@Tg0
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: :qR=>n=
首先 assignment::operator(int, int)被调用: 'lo
o7TN,([W
return l(i, j) = r(i, j); RQkyCAGx
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) $55U+)C<
X; 5Jb
return ( int & )i; k-E{d04-2
return ( int & )j; F,GN[f-
最后执行i = j; 4D$;KokZ
可见,参数被正确的选择了。 g|Y] wd
O<jPGU
F(
Ak
'JZJFE7Z
6AvHavA^Y
八. 中期总结 R#n%cXc|
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: R*zO
dxY
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 q8Nn%o=5V
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 v!42DA)
3。 在picker中实现一个操作符重载,返回该functor ?
b[n|^wS
.6m "'m0;
]WUC:6x
T*I?9d{k
*9 Q^5;y
j'HkBW:L
九. 简化 2 $ !D* <
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 wNNB;n`l
我们现在需要找到一个自动生成这种functor的方法。 2b=)6H1
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: B51kV0
1. 返回值。如果本身为引用,就去掉引用。 LhzMAW<L4
+-*/&|^等 RA],lNs
2. 返回引用。 >r)X:K+I
=,各种复合赋值等 QC0!p"
3. 返回固定类型。 Fl{WAg
各种逻辑/比较操作符(返回bool) '4OcZ/oI
4. 原样返回。 #fs|BV
!
operator, {%.Lk'#9
5. 返回解引用的类型。 IN7<@OS7
operator*(单目) xU
S]P)R
6. 返回地址。 (X +s-4%
operator&(单目) m,>
7. 下表访问返回类型。 p<`+sf}A:
operator[] s$DrR
8. 如果左操作数是一个stream,返回引用,否则返回值 L{ho*^b
operator<<和operator>> ?$z.K>S5
!r+IXuqV,!
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 S2C]?6cTq
例如针对第一条,我们实现一个policy类: p T[gdhc
"PH6e bm
template < typename Left > -6=<#9R
struct value_return )9=(|Lp
{ `@`1pOb
template < typename T > RGD]8mw
struct result_1 64j|}wJ$
{ hzY[
G:
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; | A:@&|
} ; _7kM]">j
6<Hu8$G|
template < typename T1, typename T2 > rS*$rQCr=
struct result_2 6+dn*_[Z6
{ "Vd_CO
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; DF1<JdO+
} ; LS.r%:$mb
} ; K(T\9J.
m@rSz
Ep ~wWQh
其中const_value是一个将一个类型转为其非引用形式的trait ~2uh'e3
U5/qf8)yO
下面我们来剥离functor中的operator() >qn/<??
首先operator里面的代码全是下面的形式: 7ODaX.t->
?4z8)E9Ju
return l(t) op r(t) %G?K@5?j?
return l(t1, t2) op r(t1, t2) kII7z;<^`
return op l(t) RbQ <