一. 什么是Lambda K8R}2K-Y
所谓Lambda,简单的说就是快速的小函数生成。 rD?G7l<~>_
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, f)b+>!
eF06B'uL
p_g#iH!*
5j{jbo=!
class filler oZ!1^o3V
{ WxrGoo^
public : d$?sS9"8(
void operator ()( bool & i) const {i = true ;} 5L!cS+QNU
} ; !,0%ZG}]7
K8?]&.!
"gQ-{ W
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: :p|wo"=@Ge
c(j|xQ\pE
[J-uvxD
YR? ujN
for_each(v.begin(), v.end(), _1 = true ); >%?kp[
qrw"z
iW
!Y95e'f.x
那么下面,就让我们来实现一个lambda库。 v"I#.{LiH=
x&4gy%b
xaw)iC[gI{
U%?
二. 战前分析 d J|/.J$d
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 zcrM3`Zh
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 Jjr&+Q^3Tu
WW&agr
v&]k8Hc-
for_each(v.begin(), v.end(), _1 = 1 ); oWP3Y.
/* --------------------------------------------- */ t)__J\xF
vector < int *> vp( 10 ); \kS:u}Ip!
transform(v.begin(), v.end(), vp.begin(), & _1); +~{Honj[
/* --------------------------------------------- */ [(kC/W)!
sort(vp.begin(), vp.end(), * _1 > * _2); E8LZ%
N#
/* --------------------------------------------- */ t"Tv(W?_
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); B_3:.1>"BM
/* --------------------------------------------- */ lB<
kf1[
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); O+w82!<:
/* --------------------------------------------- */ Q8GI;`Rb
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); 62D UF
->S# `"@$
~^ <1k-
YA:!ULzR*
看了之后,我们可以思考一些问题: vP.^j7wB
1._1, _2是什么? 6Qw5_V^0o
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 {Yc#XP
2._1 = 1是在做什么? WV?3DzeR
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 ygo4.
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 /y-eVu6
;%`oS.69
]Dd}^khv
三. 动工 $sS;#r0
首先实现一个能够范型的进行赋值的函数对象类: !V~,aoKTj
69iY)Ob/
(
C~ u.
?qJt4Om
template < typename T > 7]F@g}8
class assignment ~zO>Q4-k
{ Ej#pM.
T value; HOSt0IHzty
public : ]*v[6 +
assignment( const T & v) : value(v) {} 4m"6$
template < typename T2 > 1@<PcQBp
T2 & operator ()(T2 & rhs) const { return rhs = value; } ;_iDiLC;
} ; I ]HP
HE{JiAf
EN-;@P9;C
其中operator()被声明为模版函数以支持不同类型之间的赋值。 4T??8J-J
然后我们就可以书写_1的类来返回assignment U.A:'9K,
u.rFZu?E\
ANuO(^
_)XZ;Q
class holder wi-F@})f#
{ 7wz9x8 \t
public : svRYdInBNu
template < typename T > >)*0lfxTZ
assignment < T > operator = ( const T & t) const
\<u
{ T?k!%5,Kj
return assignment < T > (t); `_+%
} ^|UD&6 dx
} ; 8s9ZY4_
9$s~ `z)
h1Nd1h@-
由于该类是一个空类,因此我们可以在其后放心大胆的写上: ZbfpMZ g
7fXta|eP0
static holder _1; vX}#wDNP
Ok,现在一个最简单的lambda就完工了。你可以写 Id^)WEK4
r?2J
for_each(v.begin(), v.end(), _1 = 1 ); HAmAmEc,
而不用手动写一个函数对象。 t_kRYdW 9
BF/l#)$yK
i)q8p
{NUI8AL46A
四. 问题分析 ~s2la~gu
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 h|%a}])G)
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 U(:Di]>{
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 @iBaJ"*,
3, 我们没有设计好如何处理多个参数的functor。 jK\AVjn
下面我们可以对这几个问题进行分析。 #pnB+h&tE
S+bpWA
五. 问题1:一致性 61Wh %8-
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| "0aJE1)p:
很明显,_1的operator()仅仅应该返回传进来的参数本身。 ']U<R=5T$
*h
M5pw
struct holder Eg(.L,dj
{ M
\UB
r4
// 2= zw!
template < typename T > I9L7,~s
T & operator ()( const T & r) const Xbu P_U'
{ gMs B1|
return (T & )r; oVQbc\P3
} .`jYrW-k
} ; ]cM,m2^2
'fPDODE
这样的话assignment也必须相应改动: "t%Jj89a\
]Jo}F@\g
template < typename Left, typename Right > (bAw>
class assignment K(#O@Wmjq
{ @?*;
-]#)
Left l; \)i,`bz
Right r; 3z% W5[E)
public : >%LY0(hY3
assignment( const Left & l, const Right & r) : l(l), r(r) {} (_=R<:
template < typename T2 > 5c$\DZ(
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } 6&o?#l;|
} ; -z">ov-)
Id=V\'$o
同时,holder的operator=也需要改动: :,V&P_
|t~*!0>3
template < typename T > 40G'3HOp
assignment < holder, T > operator = ( const T & t) const .Nk5W%7]=
{ 3)y=}jw
return assignment < holder, T > ( * this , t); XTRF IY
} Ax*xa6_2
JCci*F#r
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 ]f>0P3O5&
你可能也注意到,常数和functor地位也不平等。 J,J6bfR/
QCO,f
return l(rhs) = r; Q/0oe())
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 C;~LY&=
那么我们仿造holder的做法实现一个常数类: [I}z\3Z
%
e,MgR \F}
template < typename Tp > kH`?^^_yJ
class constant_t /=g/{&3[a>
{ 3H|drj:KV
const Tp t; 7CH.BY
public : @`ii3&W4
constant_t( const Tp & t) : t(t) {} Ns]$+|
template < typename T > jVh:Bw
const Tp & operator ()( const T & r) const N`~f77G
{ F"1tPWn
return t; x_CY`Y
} nuVux5:
} ; 8Ltl32JSB[
=~5N/!
该functor的operator()无视参数,直接返回内部所存储的常数。 ;y-:)7J
下面就可以修改holder的operator=了 eL.WP`Lz
P-<1vfThH
template < typename T > J*38GX+
assignment < holder, constant_t < T > > operator = ( const T & t) const 7!wc'~;
{ 3Yo)K
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); } =Xlac_U
} 97~>gFU77#
>TiEYMW
同时也要修改assignment的operator() sWB@'P:x
ZH*h1?\X
template < typename T2 > 9hssIZO
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } RR'sW@
现在代码看起来就很一致了。 [4aw*M1z}.
G"tlJ7$myQ
六. 问题2:链式操作 6nREuT'k
现在让我们来看看如何处理链式操作。 HA7%8R*.2i
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 \w"~DuA
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 Ke=+D'=
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 }"SqB{5e(
现在我们在assignment内部声明一个nested-struct c{ +bY.J
GgnR*DVP$
template < typename T > y?P`vHf
struct result_1 !|j|rYi-
{ 74N3wi5B
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; {jH'W)nR
} ; y/kB`Z(Yj
dsj}GgG?Z
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: =FI[/"476
k{=dV
template < typename T > }}ic{931
struct ref bo(w$&
VW
{ #
5U1F[
typedef T & reference; m(d|TwG{
} ; sHMO9{[7H
template < typename T > O|)b$H_
struct ref < T &> %4Qs|CM)m
{ ,hT.Ok={36
typedef T & reference; RjTGm=1w
} ; 9thG4T8
Dte5g),R
有了result_1之后,就可以把operator()改写一下: |$e'yx6j
&6
<a<S
template < typename T > >T c\~l
typename result_1 < T > ::result operator ()( const T & t) const `'sD (e
{ __FEdO
return l(t) = r(t); Wz"H.hf
} x#N_h0[i
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 mo] l_'
同理我们可以给constant_t和holder加上这个result_1。 Z<^!N)
ZTz07Jt
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 QIlZZ
_1 / 3 + 5会出现的构造方式是: 5E"^>z
_1 / 3调用holder的operator/ 返回一个divide的对象 DcdEt=\)h
+5 调用divide的对象返回一个add对象。 j7Ts&;`[*
最后的布局是: t89Tt @cf
Add '
|B3@9<
/ \ ed}#S~4q
Divide 5 VN`fZ5*d~
/ \ pr7lm5
_1 3 n*A1x8tn
似乎一切都解决了?不。 O!{YwE8x9
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 7`&ISRU4
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 |*UB/8C^/!
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: qy)~OBY
d[J_iD{ &
template < typename Right > QDV+(
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const fFqYRK
Right & rt) const DyiJ4m}kh
{ L YF|
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); &JqaIJh
} 1ONkmVtL
下面对该代码的一些细节方面作一些解释 1^X)vck
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 M3O !jN~
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 F]?] |nZZ
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 \|HNFx T`
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 <?5|(Q"@:
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? =3w;<1 ?'
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: 7#%Pry
#0[^jJ3J
template < class Action > ?SElJ?Z
class picker : public Action 3u$1W@T(
{ ?X6}+
public : )3:0TFS}}k
picker( const Action & act) : Action(act) {} =!^
gQ0~4
// all the operator overloaded bNVeL$'
} ; U].]K
v#/Gxk9eX
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 z_fjmqa?
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: {#k[-\|;
~~h#2SX
template < typename Right > II}M|qHaK
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const -R:_o1"
{ ?V^7`3F
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); 3yKmuu!
} ucx02^uA
E6 -*2U)k+
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > yW=+6@A4
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 9DNp
ebQgk
Y=
template < typename T > struct picker_maker X$ZVY2
{ V&s|I oTR
typedef picker < constant_t < T > > result; ?e<2'\5v
} ; h7UNmwj
template < typename T > struct picker_maker < picker < T > > 6~x'~T
{ ggx_h
typedef picker < T > result; kY~4AH
} ; *b.
>
QE\
[EI2
下面总的结构就有了: gYc]z5`
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 |2u=3#Jp
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 njaMI8|Pa
picker<functor>构成了实际参与操作的对象。 o6k#neB>=.
至此链式操作完美实现。 c
Rq2 re
_y^r==
vyIH<@@p7
七. 问题3 -$Hu$Y}>
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 wwB3m&
=Nxkr0])!
template < typename T1, typename T2 > 5FoZ$I
??? operator ()( const T1 & t1, const T2 & t2) const Z,.Hz\y1D
{ LZRg%3.E
return lt(t1, t2) = rt(t1, t2); c0gVW~I1
} 0
Uropam
V}#X'~Ob
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: P9
<U+\z
LKu\M h|
template < typename T1, typename T2 > T$xBH
struct result_2 h^yqrDyJ
{ <h7cQ
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; 6:7[>|okQ
} ; _5jT}I<k
8Y?M:^f~
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? MY^{[#Q
这个差事就留给了holder自己。 }'$PYAf6
<OMwi9
[ >O!~
template < int Order > ^a4z*#IOr
class holder; Rm} ym9
template <> "?I#!t%'
class holder < 1 > ~|V^IJZ22
{ -Uwxmy +
public : 4+RR`I8$Ge
template < typename T > i+*!"/De
struct result_1 1UP=(8j/
{ |1U_5w
typedef T & result; 7>JTQ CJ
} ; J7`mEL>?
template < typename T1, typename T2 > =*2,^j
struct result_2 i}) s4%a
{ g'(bk@<BP
typedef T1 & result; fjh|V9H
} ; cMw<3u\
template < typename T > uzy5rA==
typename result_1 < T > ::result operator ()( const T & r) const 1qRquY
{ *NmY]
return (T & )r; `\kihNkJn3
} y6XOq>
template < typename T1, typename T2 > ~]?:v,UIm(
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const qO#3{kW
{ \Z[1m[{
return (T1 & )r1; _%w680b'
} /Z:j:l
} ; x'GB#svi
v@_1V
template <> Bm$|XS3cD
class holder < 2 > .H" ?&Mf
{ hsC T:1i
public : T
ozx0??)
template < typename T > //R"ZE@d\
struct result_1 Y{YbKKM
{ )PX VR
T
typedef T & result; (8duV
} ; \T7Mt|f:5
template < typename T1, typename T2 > 6_CP?X+T
struct result_2 ?Nos;_/
{ 5'AP:3Gf"
typedef T2 & result; oz)[-
} ; cS ~OxAS
template < typename T > Q Be6\oq
typename result_1 < T > ::result operator ()( const T & r) const '!HTE`Aj
{ |cvU2JI@
return (T & )r; |5&+VI
} n(:<pz
template < typename T1, typename T2 > >Bt82ibN
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const EL 5+pt
{ r/Y J, 2!
return (T2 & )r2; }A)\bffH
} pv_o4qEN
} ; AGlBvRX7e
m'o dVZ7
RRL{a6(?
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 broLC5hbQU
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: #}`sfaT
首先 assignment::operator(int, int)被调用: E&M(QX5
Iy<>-e"|
return l(i, j) = r(i, j); jK|n^5\
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) ~ao:9ynY
YpZB-9Krf
return ( int & )i; vy<W4
return ( int & )j; 6u[fCGi%
最后执行i = j; J9^NHU
可见,参数被正确的选择了。 E~!$&9\
7'0Vb!(
:eN&wQ5q
BWt`l,nF
VkQ@c;C
八. 中期总结 je] DR~
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: vFPY|Vzh
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 2t= =<x
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 C6!F6Stn]g
3。 在picker中实现一个操作符重载,返回该functor s68(jYC7[
r!:yUPv
_CwTe=K}
fY<#KM6X
NxP(&M(
j G8;p41
九. 简化 #M-!/E
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 >eJ<-3L;
我们现在需要找到一个自动生成这种functor的方法。 \"lz,bT
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: LrU8!r`a
1. 返回值。如果本身为引用,就去掉引用。 6VW*8~~Xy
+-*/&|^等 N>mW64_H)
2. 返回引用。 ug3\K83aj/
=,各种复合赋值等 f{BF%;
3. 返回固定类型。 v~$V
各种逻辑/比较操作符(返回bool) 1@]&iZ]
4. 原样返回。 UU=]lWib
operator, ;[ <(4v$
5. 返回解引用的类型。 wgl <JO
operator*(单目) d |17G
6. 返回地址。 WzIUHNn'I
operator&(单目) IJ^~,+
7. 下表访问返回类型。 'a#lBzu\b
operator[] 5`h$^l/
8. 如果左操作数是一个stream,返回引用,否则返回值 lM-9 J?j
operator<<和operator>> $n<a`PdH
{ _9O4 +
&
OK,这样我们将返回值类型总结为以上8种,就可以将各种result_x从functor中剥离出来了。 =?5)M_6)
例如针对第一条,我们实现一个policy类: FnvpnU",
GJ9>i)+h;
template < typename Left > PTe L3L
struct value_return *X0>Ru[
{ | {9<%Ok4P
template < typename T > abo=v<mR
struct result_1 #p}GWS)
{ K[[~G1Z
typedef typename const_value < typename Left::template result_1 < T > ::result_type > ::value_type result_type; ee {ToK
} ; +B*]RL[th
kwjO5OC8
template < typename T1, typename T2 > ;(C<gt,r}
struct result_2 omE- c
{ =AIts[!qd
typedef typename const_value < typename Left::template result_2 < T1, T2 > ::result_type > ::value_type result_type; v[dUUR f
} ; xf,[F8 2y
} ; 5m8u :6kQu
bRAD_
/,\V}`Lx"
其中const_value是一个将一个类型转为其非引用形式的trait -^_2{i
/7}pReUj
下面我们来剥离functor中的operator() 5B=uvp|Y
首先operator里面的代码全是下面的形式:
"*d6E}wG
\^)i!@v
return l(t) op r(t) gd;!1GNi]
return l(t1, t2) op r(t1, t2) ] Q5:JV
return op l(t) aTcz5g0"
return op l(t1, t2) 3FBL CD3
return l(t) op !se1W5ke#
return l(t1, t2) op ucN'
zq
return l(t)[r(t)] '=dQ$fs
return l(t1, t2)[r(t1, t2)] h;V4|jM
$|K:
9
很自然的,我们会想到用函数替代这种操作符行为以获得更加一致的形式: Qs1p
单目: return f(l(t), r(t)); JK$3qUDnI
return f(l(t1, t2), r(t1, t2)); u)oAQ<w
双目: return f(l(t)); ~ZKJ:&f