一. 什么是Lambda rp4{lHw>C/
所谓Lambda,简单的说就是快速的小函数生成。 /#z"c]#
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, ^E_chx-e}
gCF9XKW
[ahwJ F#r
K_n
GZ/`[
class filler 9 I:3
{ 3mHP=)
public : lvRTy|%[
void operator ()( bool & i) const {i = true ;} j]U~ZAn,K
} ; wv`ar>qVL
@
M4m!;rM
vw$b]MO!
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: nly}ly Q/
9f/l"
Z&4L///
w5yX~8UzJ
for_each(v.begin(), v.end(), _1 = true ); 0|]d^bo
LqXVi80
3<l}gB'S[
那么下面,就让我们来实现一个lambda库。 K,6{c^qf
v0TbQ
>oN Wf
}]M'f:%b
二. 战前分析 \=P(?!v
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 V(XZ7<& {
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 ^G 'n
z
*8+HQ[[#
"bB0$>0,
for_each(v.begin(), v.end(), _1 = 1 ); %QQ 2u$
/* --------------------------------------------- */ >4q6
vector < int *> vp( 10 ); `EfFyhG$
transform(v.begin(), v.end(), vp.begin(), & _1); u9(42jj[$U
/* --------------------------------------------- */ $=X>5B
sort(vp.begin(), vp.end(), * _1 > * _2); 0>46ZzxUZ
/* --------------------------------------------- */ `e`DSl D>
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); , hrv
/* --------------------------------------------- */ "Ec9.#U/
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); c[V.j+Iy#^
/* --------------------------------------------- */ ]rSg,Q>E
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); YNl".c
(.i wD&
sIbPMu`&U
O)DAYBv^
看了之后,我们可以思考一些问题: _;%l~q/
1._1, _2是什么? x}O,xquY
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 R+t]]n6#
2._1 = 1是在做什么? `mI5Z*]-
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 8GRB6-.h
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 \3]O?'
$BT[fJ'k
GIT"J}b}
三. 动工 HO_(it \
首先实现一个能够范型的进行赋值的函数对象类: ?Q$a@)x#
Q/]o'_[vW
sxS%1hp3
a#G3 dY>
template < typename T > 6xAxLZz<
class assignment jse!EtB:
{ (`_fP.Ogb
T value; u.G aMl4 (
public : FhPCFmmUT
assignment( const T & v) : value(v) {} p-lFzNPc0
template < typename T2 > ]d~{8h!G
T2 & operator ()(T2 & rhs) const { return rhs = value; } DUH DFG
} ; wW8[t8%43
,j9? 9Z7R
._t1eb`m{
其中operator()被声明为模版函数以支持不同类型之间的赋值。 {-MjsBR
然后我们就可以书写_1的类来返回assignment fFoZ!H
`KE]RTq
I<XYLe[_S
I-1NZgv
class holder SjY|aW+wAL
{ )m[<lJbw
public : QoZZXCU
template < typename T > s&'FaqE
assignment < T > operator = ( const T & t) const | lZJt
{ Fa\jVFIQ
return assignment < T > (t); ?Z4%u8Krvz
} Vy| 4k2
} ; Rry]6(
-rjQ^ze
AlG5n'
由于该类是一个空类,因此我们可以在其后放心大胆的写上: i~AReJxt7
Gg]Jp:GF
static holder _1; %rgW}Z5
Ok,现在一个最简单的lambda就完工了。你可以写 =F Y2O`%a
pq\N2d
for_each(v.begin(), v.end(), _1 = 1 ); ASrRMH[
而不用手动写一个函数对象。 qJf\,7mi
h{H*k#>
-'L~Y~'.
,Vo[mB
四. 问题分析 H3`.Y$z
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 ~'0ZW<X.
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 )n1[#x^I
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 F |R7hqf
3, 我们没有设计好如何处理多个参数的functor。 <2]D3,.g.
下面我们可以对这几个问题进行分析。 _ WPt
zL
$uJc/
五. 问题1:一致性 $duT'G, -
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| aJtpaW@
很明显,_1的operator()仅仅应该返回传进来的参数本身。 jN'h/\
L,
#|W
struct holder '*&dP"
{ {o 5^nd
// I} 5e{jBB
template < typename T > ](8F]J ,
T & operator ()( const T & r) const 1|!)*!hu
{ %l#X6jkt
return (T & )r; P,a9B2
} Q4/BpKL
} ; ;Zj(**#H
_Gaem"k|
这样的话assignment也必须相应改动: arRU` 6?
>;bym)
template < typename Left, typename Right > =$L+J O
class assignment cDzb}W*UM
{ }<@-=
Left l; 1-N+qNSD`
Right r; ~K;hXf
public : A>e-eD xi
assignment( const Left & l, const Right & r) : l(l), r(r) {} |5:2?S2R
template < typename T2 > o1?-+P/
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } ;ND[+i2MN
} ; NP.i,H
C984Ee
同时,holder的operator=也需要改动: /988K-5k
'6e4rn{
template < typename T > )G?\{n-
assignment < holder, T > operator = ( const T & t) const 98O]tL+k/u
{ GCiG50Z=
return assignment < holder, T > ( * this , t); u*W! !(P/
} zJl;|E".
*]h"J]
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 2<p@G#(
你可能也注意到,常数和functor地位也不平等。 k9<UDg_ Y
E
i>GhvRM
return l(rhs) = r; ^);M}~
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 %n8CK->
那么我们仿造holder的做法实现一个常数类: 6OAEAIh
B:0oT
template < typename Tp > g6P^ JW}.
class constant_t {^(uoB C/
{ j (Q#NFT7
const Tp t; OI"g-+~
public : H_t0$x(\
constant_t( const Tp & t) : t(t) {} vr{|ubG]d
template < typename T > $w <R".4
const Tp & operator ()( const T & r) const QRrAyRf[
{ %8%|6^,
return t; s^IC]sW\%
} r\F2X J^
} ; $F9w0kz:,*
]h'
38W
该functor的operator()无视参数,直接返回内部所存储的常数。 .-mIU.Nwi
下面就可以修改holder的operator=了 DO~[VK%|
j[FB*L1!D
template < typename T > b]Kb ~y|
assignment < holder, constant_t < T > > operator = ( const T & t) const 2#3`[+g<n
{ <H-kR\HF
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); C4`&_yoP4-
} ai1;v@1
G3+e5/0
同时也要修改assignment的operator() FE{c{G<
S;gy:n!t
template < typename T2 > QKx(S=4jQ
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } o#1Ta7Ro
现在代码看起来就很一致了。 &"gX
7cK8
bc~$"
六. 问题2:链式操作 9&Un|cr
现在让我们来看看如何处理链式操作。 aXQAm$/
>
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 '0)`.
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 3)LS#=
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 #a~BigZ[G
现在我们在assignment内部声明一个nested-struct }cGILH%
z;2& d<h
template < typename T > ?V+\E2
struct result_1 ;S$
{ L;?F^RK{U
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; cJ@fJ|
} ; T,uF^%$@AQ
m9sck:g#L1
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: 9a`~ K L
6SE^+@jR
template < typename T > &08dW9H
struct ref Lb<IEy77\
{ x|Pz24yP9
typedef T & reference; IemhHf ^l
} ; 4|I;z
template < typename T > ((#BU=0iK
struct ref < T &> D_$N2>I-
{ DbB<8$
typedef T & reference; \b"|p%CL8
} ; hEZo{0:b"
9I
[:#,zdf
有了result_1之后,就可以把operator()改写一下: 50Gu~No6
!\d~9H%`B
template < typename T > ^>!&]@
typename result_1 < T > ::result operator ()( const T & t) const *S}CiwW>/
{ )m8Gbkj<
return l(t) = r(t); ar,v/l>d4N
} SFtcO
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 (G} }h
同理我们可以给constant_t和holder加上这个result_1。 gg^iYTpt
.E+O,@?<
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 /ar0K9`c
_1 / 3 + 5会出现的构造方式是: C@t,oDU#
_1 / 3调用holder的operator/ 返回一个divide的对象 xr@;w8X`^
+5 调用divide的对象返回一个add对象。 V_m!<sr (
最后的布局是: 60nP'xfR
Add Opg_-Bf
/ \ iHc(e(CB<
Divide 5 e&:%Rr]x
/ \ L'`Au/%S}
_1 3 LJb=9tp~
似乎一切都解决了?不。 d*04[5`
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 $|&<cenMT
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 O/ItN5B
;
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: "s]
XRQ1Uh6
template < typename Right > [_3&
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const Zos.WS#
Right & rt) const M=95E$6
{ O`%F{&;29
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); -bdWG]w"
} m;rr7{7X
下面对该代码的一些细节方面作一些解释 8tv4_Lbx
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 D4y!l~_,%M
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 +HWFoK
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 FNOsw\Bo
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 5bXpj86mY
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? P2`F"
Qsq
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: (;05=DsO
WoB'B|%
template < class Action > H<q|je}e
class picker : public Action I9aiAD0s
{ 0m.`$nlV-
public : <*^|Aj|#
picker( const Action & act) : Action(act) {} kb"Fw:0
// all the operator overloaded q27q/q8
} ; `EvO^L
LD
NdHG6
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 eAI|zk6
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: N TDmOS\,
_yH">x<
template < typename Right > 3kUb cm
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const 'WmjQsf
{ NKB["+S<
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); lqh:c
} B=^M& {
n{~&^Nby*I
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > {jR3D!hK
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 jr.{M
d_&pxy?
>
template < typename T > struct picker_maker o+{i26%
{ '~f*O0_
typedef picker < constant_t < T > > result; Ei+lVLoC
} ; ht6}v<x.eA
template < typename T > struct picker_maker < picker < T > > 6(htpT%J
{ CKe72OC
typedef picker < T > result; gp 11/.
} ; Q7F4OS5b
HGh)d` 8
下面总的结构就有了: nSQ]qH&4d
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 Q"eqql<h#
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 >c
Tt2v
picker<functor>构成了实际参与操作的对象。 3$K[(>s
至此链式操作完美实现。 [okV[7
Kx,X{$Pe
sm G?y~
七. 问题3 TxN+-< f
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 WL'!M&h
dQ_'8
)
template < typename T1, typename T2 > NM),2% <
??? operator ()( const T1 & t1, const T2 & t2) const hSAI G
{ :@E^oNKa0
return lt(t1, t2) = rt(t1, t2); <?L5bhq
} EW4a@
IUh9skW5
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: 'x?|tKzd
8dt=@pwx&
template < typename T1, typename T2 > mRyf+O[
struct result_2 "d~<{(:N^
{ jVGAgR=[G
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; %yKcp5_
} ; vmOye/?k
0;=]MEk?
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? vlDA/( &
这个差事就留给了holder自己。 E#tfCM6
vZS/?pU~~
;"EDFH#W
template < int Order > Xm(#O1Vm(l
class holder; %t1Z!xv_
template <> >,k2|m
class holder < 1 > /FW$)w2{j
{ vmfFR
public : '|v<^EH
template < typename T > zT/woiyB`
struct result_1 =c#mR" 1
{ |t3}>+"?z
typedef T & result; r]QeP{
} ; F/j ; q
template < typename T1, typename T2 > qQo*:3/];
struct result_2 yU7XX+cB7
{ ND=JpVkvZ?
typedef T1 & result; F &5iA\
} ; j1+I_
template < typename T > XS^du{ai
typename result_1 < T > ::result operator ()( const T & r) const V8o,
e
{ {IBbN05 ;
return (T & )r; 5RO6YxQ
} ).u>%4=6
template < typename T1, typename T2 > /Hm/%os
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const /J!hKK^k
{ &pz`gna
return (T1 & )r1; e,#5I(E
} ^Df qc-]
} ; K~^o06 Y
LSXsq}
template <> 5OOXCtIKf
class holder < 2 > ,?%Y*?v
{ )ytP$,r![S
public : :AuK Q`c
template < typename T > "OkZ
[E)
struct result_1 ix?Z:pIS0
{ rXTdhw?+
typedef T & result; "av/a
} ; e9S*^2;
template < typename T1, typename T2 > \fUVWXv
struct result_2 B"*PBJuOA
{ r,vSDHb`j
typedef T2 & result; I7'v;*
} ; KlBT9"6"
template < typename T > l#+@!2z
typename result_1 < T > ::result operator ()( const T & r) const |r+hj<K
{ i \lr
KA
return (T & )r; 7VkjnG^!:
} 6BQq|:U
template < typename T1, typename T2 > YCzH@94QeV
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const Sv>CVp*
{ PIQd=%?'
return (T2 & )r2; qla=LS\-A+
} b1=! "Y@
} ; E J6|y'
SwrzW'%A
B*QLKO:)i
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 bsI?=lO
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: YVz,P_\(m
首先 assignment::operator(int, int)被调用: SST@
^tjM1uaZ5(
return l(i, j) = r(i, j); (0?FZ.9%
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) 2U+Fat@
dOgc%(kz
return ( int & )i; mwz!7Q
return ( int & )j; H6$pA^
最后执行i = j; yB;K|MXy?
可见,参数被正确的选择了。 =3;!
5P
`VglE?M
~_-+Q=3
{K/xI
i5*/ZA_
八. 中期总结 !g~u'r'1
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: #Wv8+&n
1。 实现一个functor,该functor的operator()要能执行该操作符的语义 uBM%E OE
2。 在该functor中实现result_1至result_n,其中n是支持参数的最大值。 4QNwu7TeR
3。 在picker中实现一个操作符重载,返回该functor QNj6ETB-d
nnd-d+$
$V_w4!:Q
$B%3#-
*;T HD>
i(q a'*
九. 简化 OG7U+d6
很明显,要支持一个操作符所要做的工作太多了,而且在每个functor中申明result_1至result_n,可见如果n发生变化,维护的开销极大。 v}^uN+a5
我们现在需要找到一个自动生成这种functor的方法。 v?DA>
首先,我们注意到result_x的形式很统一。对于各种操作符,其返回值无非下列几种: 5'(#Sf
1. 返回值。如果本身为引用,就去掉引用。 ET6}V"UD
+-*/&|^等 3|/zlKZz
2. 返回引用。 }~<9*M-P
=,各种复合赋值等 /9-kG
3. 返回固定类型。 DPl &e-`
各种逻辑/比较操作符(返回bool) }.<]A
4. 原样返回。 lOIf4
operator, -li;w
tCS
5. 返回解引用的类型。 >+ Im:fD
operator*(单目) f+QDjJ?z
6. 返回地址。 7zXX&