一. 什么是Lambda f;,*P,K
所谓Lambda,简单的说就是快速的小函数生成。 KV6D0~
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, /"~UGn]R
Q:y'G9b
=9p3^:S
4_'B oU4
class filler m&(qr5>b
{ v|]"uPxH?
public : i?eVi
void operator ()( bool & i) const {i = true ;} >$r o\/
} ; Qr6PkHU
M&9urOa`
Au(oKs<
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: wPcEvGBN=
cb{"1z
\,v+ejhw
2<w vO 9
for_each(v.begin(), v.end(), _1 = true ); %AWc`D
@" umY-1f
,69547#o
那么下面,就让我们来实现一个lambda库。 8=0I4\
:LdPqFXj
c"1Z,M;G
&=:3/;c
二. 战前分析 ZYt <O
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 gMPp'^g]_
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 G)Y,*.,
uAoZ&8D6
uNw9g<g:V[
for_each(v.begin(), v.end(), _1 = 1 ); HRu;*3+%>F
/* --------------------------------------------- */ D$NpyF.87
vector < int *> vp( 10 ); ;, \!&o6
transform(v.begin(), v.end(), vp.begin(), & _1); `(I$_RSE")
/* --------------------------------------------- */ =1
S%E
sort(vp.begin(), vp.end(), * _1 > * _2); Wa&!1'
@
/* --------------------------------------------- */ 88?O4)c
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); )24M?R@r
/* --------------------------------------------- */ ! gfd!R
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); dq'f
>Sz}
/* --------------------------------------------- */ ;mwnAO
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); ?*7Mn`
-g|ji.
@^ m0>H
fd>&RbUp
看了之后,我们可以思考一些问题: asCcBp
1._1, _2是什么? yg~@}_C2_
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 n;>=QG
-v
2._1 = 1是在做什么? [/n@BK
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 $P%cdJ T0
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 }owl7G3
*BF[thB:a
L*vKIP<EMM
三. 动工 )Z['=+s%
首先实现一个能够范型的进行赋值的函数对象类: _G25$%/LU
Un
T\6u
r=54@`O!
O.xtY@'"
template < typename T > u-mD"
class assignment ?k;htJcGv
{ &CN(PZv
T value; $p$p C/:%
public : iJmzVR+
assignment( const T & v) : value(v) {} x.] tGS
template < typename T2 > 8gt&*;'}*D
T2 & operator ()(T2 & rhs) const { return rhs = value; } ~mi4V
} ; #V#!@@c;?
wQ@:0GJH
Z{yH:{Vk
其中operator()被声明为模版函数以支持不同类型之间的赋值。 2\gIjXX"
然后我们就可以书写_1的类来返回assignment ?N!kYTR%}
;_E|I=%'E
8VO];+N
P*VZ$bUe5@
class holder zZ<*
{
~vM99hW
public : Np r u
template < typename T > <c!gg7@pm
assignment < T > operator = ( const T & t) const v7`{6Pf_$
{ 4i+%~X@p
return assignment < T > (t); J1~E*t^
} f:J-X~T_f
} ; ^M;#x$Y?
#h4FLF_w
BNI)y@E^X
由于该类是一个空类,因此我们可以在其后放心大胆的写上: `r~3Pf).4
TOS'|xQ
static holder _1; dh&>E
Ok,现在一个最简单的lambda就完工了。你可以写 1KBGML-K3
S9r+Nsn
for_each(v.begin(), v.end(), _1 = 1 ); v_WQ<G?
而不用手动写一个函数对象。 NuD|%Ebs
MxKTKBxQ
`<M>"~W
k6RVP:V
四. 问题分析
P +OS
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 ^w<aS
w
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 L/]
(pXEp
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 X ,^([$
3, 我们没有设计好如何处理多个参数的functor。 yTZo4c"
下面我们可以对这几个问题进行分析。 cF8 X
}^p<Y5{b
五. 问题1:一致性 oM
Z94,3
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| W\;|mEEu
很明显,_1的operator()仅仅应该返回传进来的参数本身。 ACZK]~Y'N*
#(i
pF
struct holder ~a&VsC#
{ FU>KiBV#
// -)}Z
$;1a
template < typename T > C"_ Roir?
T & operator ()( const T & r) const h0g?=hJq
{ ~dp f1fP
return (T & )r; Qx8(w"k*
} Z*UVbyC
} ; .kPNWNrw
n\JI7A}
这样的话assignment也必须相应改动: 2l^_OrE!
,-8-Y>[
template < typename Left, typename Right > Q9xb7)G
class assignment `M 'tuQ
M
{ ~ A=Gra
Left l; @7C.0>W_A
Right r; =y)K er
public : x|G
:;{"+6
assignment( const Left & l, const Right & r) : l(l), r(r) {} 1;V_E2?V
template < typename T2 > ~!8j,Bqs+z
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } QKlsBq
} ; b.@4yW
m_@XoS
yxI
同时,holder的operator=也需要改动: *pv<ZF0>
q^Oj/ws
template < typename T > dIYf}7 P
assignment < holder, T > operator = ( const T & t) const ov;^ev,(
{ +jF2{"
return assignment < holder, T > ( * this , t); c"Vp5lo0
} Ro"'f7(v.
xdM'v{N#m
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 LbRQjwc]W
你可能也注意到,常数和functor地位也不平等。 HG?+b
i$PO#}
return l(rhs) = r; #ye`vD
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 Xo/H+[;X
那么我们仿造holder的做法实现一个常数类: cy;i1#1rO
O#=%t
template < typename Tp > ,I x>.^|
class constant_t /w(g:e
{ s-PS]l@
const Tp t; W0~G`A(:;
public : %<(d%&~
constant_t( const Tp & t) : t(t) {} |l+5E
template < typename T > 8B?U\cfa^
const Tp & operator ()( const T & r) const ~~-VScG&
{ ftR& 5!Wm
return t; 83t/\x,Q
} cGgfCF^`
} ; ?Y,^Moc:
'xxM0Kn`
该functor的operator()无视参数,直接返回内部所存储的常数。 Z_m<x!
下面就可以修改holder的operator=了 YI,t{Wy
62zu;p9m
template < typename T > m}s.a.x
assignment < holder, constant_t < T > > operator = ( const T & t) const Rk3
bZvj3
{ AguE)I&m
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); /[\g8U{5B}
} 1(IZ,*i
:;]9,n
同时也要修改assignment的operator() v
x/YWZ
/3~L#jS
template < typename T2 > 2[qfF6FHA
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } vB_3lAJt@
现在代码看起来就很一致了。 ~nfOV*
x"NQatdq
六. 问题2:链式操作 86Q3d%;-yo
现在让我们来看看如何处理链式操作。 2J&~b 8 :
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 >WDHRC
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 kex V~Q
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 e7xBi!I)~
现在我们在assignment内部声明一个nested-struct oYZ
4F
7KhS{w6
template < typename T > rMbq_5}
struct result_1 0r1GGEW`s
{ $">j~! '
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; nf 8V:y4
} ; FrXP"U}Y
Z}uY%]
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: )-Hs]D:
}" vxYB!h3
template < typename T > Qa )+Tv
struct ref 2WFZ6
{ g}D)MlXRq
typedef T & reference; nco.j:
} ; hoqZb<:
template < typename T > `HXv_9
struct ref < T &> zH}3J}
{ 5buW\_G)
typedef T & reference; iiIns.V
} ; _Ik?WA_;
bAZoi0LR
有了result_1之后,就可以把operator()改写一下: kP&I}RY
^py=]7[I
template < typename T > ya8p
4N{_
typename result_1 < T > ::result operator ()( const T & t) const Mp|Jt
{ cE
'LE1DK
return l(t) = r(t); <Q9l'u]3$c
} _90D4kGU
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 kWZY+jyt P
同理我们可以给constant_t和holder加上这个result_1。 W{"sB:E
?I[8rzBWU
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 lTMY|{9
_1 / 3 + 5会出现的构造方式是: s"`~Xnf
_1 / 3调用holder的operator/ 返回一个divide的对象 m.m6.
+5 调用divide的对象返回一个add对象。 :&vX0
Ce:
最后的布局是: j}ob7O&U'w
Add 0@-4.IHl
/ \ FDLo|aP/v
Divide 5 6-_g1vq
/ \ zY_J7,0g
_1 3 *O~y6|U?
似乎一切都解决了?不。 `5Kg[nB:
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 s;OGb{H7
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 L?d?O
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: CsA (oX
<WZ{<'ajI
template < typename Right > ?Te#lp;`~
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const 8Re[]bE
Right & rt) const /GO-
{ F%|P#CaB
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); W-s 6+DY
} N<rq}^qo
下面对该代码的一些细节方面作一些解释 lfHN_fE>Mq
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 7s?#y=M
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 7! >0
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 z!3=.D
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 Qy" Jt ]O
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? &S{r;N5u
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明:
,XEIg
FprdP*/
template < class Action > ]{6/6jl
class picker : public Action u>fMO9X}2
{ wkx9@?2*
public : %@Gy<t,
picker( const Action & act) : Action(act) {} \s*UUODWK
// all the operator overloaded LVB wWlJ
} ; spfW)v/T!
D wJ^ W&*
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 mBErU6?X,A
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: vYV!8o.I
BrE#.g Jq
template < typename Right > paIjXaU1Mb
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const o(SPT?ao~
{ ih0a#PB8
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); tVAo o-%
} &<e18L7a
L8h3kT
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > uMw6b=/U
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 Q&]|W
Xv
w/*G!o-<
template < typename T > struct picker_maker toPbFU'
{ 7?whxi Qs
typedef picker < constant_t < T > > result; -4Hb]#*2
} ; ,6{z
template < typename T > struct picker_maker < picker < T > > MWv@]P_0p!
{ a
-Pz<*
typedef picker < T > result; -13}]Gls7Q
} ; 9-T<gYl
>XgJo7u
下面总的结构就有了: e
n~m)r3&
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 Sxq@W8W
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 ck{S
picker<functor>构成了实际参与操作的对象。 T5u71C_wmt
至此链式操作完美实现。 1- s(v)cxh
^5E9p@d"J
N4+Cg t(
七. 问题3 (SRY(q
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 ~6i'V?>
(s;W>,~q
template < typename T1, typename T2 > @bA5uY!
??? operator ()( const T1 & t1, const T2 & t2) const 3UUdJh<~
{ \:J=tAC
return lt(t1, t2) = rt(t1, t2); c},pu[nL
} IADHe\.
3Tu]-.
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: ;|vP|Xi
HQP.7.w7 5
template < typename T1, typename T2 > S9l,P-X`
struct result_2 wvq4 P
{ +Xs E
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; YYn8!FIe
} ; 1jd{AqHl
VH]}{i"`
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? q|<B9Jk
这个差事就留给了holder自己。 }8 z:L<
'w=|uE {^
vQ*[tp#qU
template < int Order > I #1~CbR
class holder; y-3'qq'E
template <> B$2b=\
class holder < 1 > <{cY2cx~3
{ 8Ij<t{Lps
public : QZ&(e2z
template < typename T > d/9YtG%q
struct result_1 9\.0v{&v
{ ~QbHp|g
typedef T & result; ,7j8+p|},
} ; G~5pMyOR
template < typename T1, typename T2 > l}/_(*
struct result_2 )oCL![^pXe
{ .hmeP
MK
typedef T1 & result; Ts
!g=F
} ; +4%~.,<_to
template < typename T > L-w3A:jk
typename result_1 < T > ::result operator ()( const T & r) const !s-A`}
s+
{ tG$O[f@U6
return (T & )r; [gBf1,bK
} 2%WeB/)9
template < typename T1, typename T2 > |,,#DSe
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const gttsxOgktH
{ h,Hr0^?
return (T1 & )r1; :o!Kz`J
} X0
|U?Ib?
} ;
/#Pm'i>B
u"qu!EY2
template <> "j_iq"J
class holder < 2 > "a[;{s{{.
{ rtS cQ
public : 67rY+u%
template < typename T > )<V!lsUx'-
struct result_1 &Gh,ROo4
{ mj'~-$5T
typedef T & result; ltuV2.$
} ; /= ;,lC
template < typename T1, typename T2 > [`GSc6j
struct result_2 PFX,X
{ c]Epg)E
typedef T2 & result; f DXK<v)
} ; #`3Q4
template < typename T > J-<P~9m~I
typename result_1 < T > ::result operator ()( const T & r) const XDCm
{ 7N 0Bj!
return (T & )r; Hes!uy
} o>M^&)Xs
template < typename T1, typename T2 > my A;Y
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const 9 wR D=a
{ z|3v~,
return (T2 & )r2; @]n8*n
} GG>53}7{
} ; ^)9/Wz _x
h/tCve3Z
G06;x
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 F\N0<o
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: 7#C$}1XJ1
首先 assignment::operator(int, int)被调用: \L(jNN0_R
bWA_a]G
return l(i, j) = r(i, j); T@ESMPeU:X
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) %EU_OS(u.{
AVjRhe
return ( int & )i; ZOfv\(iJ;
return ( int & )j; M@es8\&S.
最后执行i = j; X >7Pqn'
可见,参数被正确的选择了。 N-2#-poDe
'df@4} 9
@\F7nhSfa
E}4{{{r
9mHCms
八. 中期总结 /UunWZ u%
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: &C
MBTY#u
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 qWW\d', .
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 K{_~W yRF
3。 在picker中实现一个操作符重载,返回该functor liYsUmjZ=
+>C26Q
Y[L,rc/j
|5(un#
o+hp#e
!X7z y9
九. 简化 O83J[YuzjN
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 K7C
<}y
我们现在需要找到一个自动生成这种functor的方法。 k+{~#@
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: 0z \KI?kd
1. 返回值。如果本身为引用,就去掉引用。
&5K3AL
+-*/&|^等 uH$hMg
2. 返回引用。 !PoyM[Z"f
=,各种复合赋值等 ^
q ba<#e
3. 返回固定类型。 iWeUsS%zpV
各种逻辑/比较操作符(返回bool) 5)f 'wVe
4. 原样返回。 LNJKf6:
operator, huv|l6
5. 返回解引用的类型。 a"P &
9c
operator*(单目) VJ-t#q"
6. 返回地址。 Po=:-Of:
operator&(单目) ,9G'1%z,
7. 下表访问返回类型。 xytWE:=
operator[] H9jlp.F
8. 如果左操作数是一个stream,返回引用,否则返回值 {G=> WAXo
operator<<和operator>> 'KmM%tN
7|=SZ+g
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 !Dc?9W!b
例如针对第一条,我们实现一个policy类: vULDKJNHX
xKL(:ePS
template < typename Left > ]u|FcwWc3
struct value_return I*U7YqDC9
{ !N+{X\+
template < typename T > #(qvhoi7lM
struct result_1 JUw|nUnl?
{ 0*]0#2Z
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; prO&"t
>
} ; )Mq4p'*A[
LT{g^g
template < typename T1, typename T2 > X_-/j.
struct result_2 IrRy1][Qr
{ "T /$K
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; y+B iaD!U
} ; 9*j"@Rm
} ; )X#$G?|Hn
uq6>K/~D
'`}D+IQ(j
其中const_value是一个将一个类型转为其非引用形式的trait sifjmNP
r9}(FL/)b
下面我们来剥离functor中的operator() (~\HizSl
首先operator里面的代码全是下面的形式:
fATnza
9ox5,7ZQ
return l(t) op r(t) S9:ij1
return l(t1, t2) op r(t1, t2) y46sL~HRv
return op l(t) "?aE3$/
return op l(t1, t2) W{JR%Sq$
return l(t) op |LIcq0Z
return l(t1, t2) op um PN=0u6
return l(t)[r(t)] nUq@`G
return l(t1, t2)[r(t1, t2)] 1 h(n}u
;(E]mbV'=
很自然的,我们会想到用函数替代这种操作符行为以获得更加一致的形式: 1|
WDbk
单目: return f(l(t), r(t)); D {E,XOi
return f(l(t1, t2), r(t1, t2)); 0RdW.rZJ
双目: return f(l(t)); hT=E~|O
return f(l(t1, t2)); O:V.;q2]U
下面就是f的实现,以operator/为例 &K