一. 什么是Lambda ZCMB]bL-e
所谓Lambda,简单的说就是快速的小函数生成。 L&'0d$Tg8
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, kI3-G~2
HJ5m5':a
T}[W')[s
As (C8C<
class filler h& (@gU`A
{ 2`vCQV
public : rA9x T`
void operator ()( bool & i) const {i = true ;} C<fNIc~.
} ; 8'B\%.+"8e
jl2nRo
)
ZOmv
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: S_:(I^
@6$r|:]G-
ooIMN =
>UJ&noUD#:
for_each(v.begin(), v.end(), _1 = true ); ),\>'{~5&
`z)!!y
NI(`o8fN
那么下面,就让我们来实现一个lambda库。 "`"j2{9|e!
0mj=\ j
i:kWO7aP
H]=3^ g64
二. 战前分析 0m`7|80#P
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 7"xd'\c@
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 4'54
n/?5[O-D]
5.[{PJ]bq
for_each(v.begin(), v.end(), _1 = 1 ); 9$Mi/eLG2N
/* --------------------------------------------- */ cJ8F#t
vector < int *> vp( 10 ); 2c%}p0<;|?
transform(v.begin(), v.end(), vp.begin(), & _1); !icpfxOpjQ
/* --------------------------------------------- */ kFM'?L&
sort(vp.begin(), vp.end(), * _1 > * _2); \-s) D#Y;r
/* --------------------------------------------- */ 4&ea*w
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); sD{b0mZT
/* --------------------------------------------- */ }h_Op7.5D
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); sjTsaM;<
/* --------------------------------------------- */ i8B%|[nm
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); <YeF?$S}
_;B!6cRLps
7Xad2wXn
kw-/h+lG
看了之后,我们可以思考一些问题: 2hJ{+E.m
1._1, _2是什么? U*&ZQw
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 !W%HAlUAG[
2._1 = 1是在做什么? m]-8?B1`Y
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 (C-z8R
Z6
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 WQ5sC[&
&YT7>z,
Bd
NuhV`0
三. 动工 '-i
tn
首先实现一个能够范型的进行赋值的函数对象类: =|U2 }U;
p fBO5Ys
_kY5
6
P/I{q s
template < typename T > ^CK)q2K>[
class assignment J.<%E[
z
{ Ar<OP'C
T value; 6ZG)`u".("
public : owMH
assignment( const T & v) : value(v) {} T![K
i
template < typename T2 > Oq[E\8Wn
T2 & operator ()(T2 & rhs) const { return rhs = value; } L|q<Bpz
} ; #h3+T*5} 6
`90v~OF
Eq8OAuN
其中operator()被声明为模版函数以支持不同类型之间的赋值。 ?J~JQe42
然后我们就可以书写_1的类来返回assignment /5x`TT
T),:8/
huF L [
,g,jY]o
class holder @zJI0_Bp
{ BL8\p_U
public : 5./
(fgx>
template < typename T > -ufmpq.
assignment < T > operator = ( const T & t) const 7&At_l_
{ sN
C?o[9l!
return assignment < T > (t); ^X&9"x)4
} *2AQ'%U~
} ; i52R,hz
R{[Q+y'E
zJnVO$A'
由于该类是一个空类,因此我们可以在其后放心大胆的写上: Wl#^Eu\g1W
_#gsR"FZ$
static holder _1; .u*].As=
Ok,现在一个最简单的lambda就完工了。你可以写 mN eW|3a
[*vN`AfE
for_each(v.begin(), v.end(), _1 = 1 ); +E [b Lz^
而不用手动写一个函数对象。 tbPPI)lu
=a!6EkX
*
A$F;fCV*
*h4m<\^U
四. 问题分析 'i(p@m<'
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 _B1uE2j9
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 J:lwq@u
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 {@#L'i|
3, 我们没有设计好如何处理多个参数的functor。 0l6iv[qu5w
下面我们可以对这几个问题进行分析。 /K!,^Xn
}}1/Ede{5
五. 问题1:一致性 =|!~0O
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| ~1'468
很明显,_1的operator()仅仅应该返回传进来的参数本身。 U959=e
cx,A.Lc
struct holder K D-_~uIF
{ PbPP1G')
// ]= NYvv>H
template < typename T > Dq?HUb^X
T & operator ()( const T & r) const +zdkdS,2<
{ .O#lab`:2
return (T & )r; YgiGI
<U
} 2A%T!9J3
} ; NACY;XQ%
5dp#\J@
这样的话assignment也必须相应改动: "J5Pwvs-
Rdg0WT*;j
template < typename Left, typename Right > M0zD)@
class assignment W`'|&7~
{ #(IMRdUf
Left l;
)M N
yOj
Right r; tKeO+6 l
public : Qg>GW
assignment( const Left & l, const Right & r) : l(l), r(r) {} erP>P
template < typename T2 > Hm*vKFhz
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } 9(F?|bfk
} ; LQ@|M.$A
^R7z LHU;
同时,holder的operator=也需要改动: (YJAT
>1U@NK)HfY
template < typename T > B^(rUR
assignment < holder, T > operator = ( const T & t) const 4_%FSW8-
{ e-cb?.WU?
return assignment < holder, T > ( * this , t); c'+r[rSn1
} 3t8H?B12ow
&E &iaw!
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 JGDUCb~
你可能也注意到,常数和functor地位也不平等。 DsW`V~T
$ XsQ e
return l(rhs) = r; *z"1MU
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 ~}0hN]*G
那么我们仿造holder的做法实现一个常数类: f5GR#3-h(
,N7l/6
template < typename Tp > ptcLJ]+)
class constant_t n{Qh8"
{ ;9 &1JX
const Tp t; q3-;}+
public : T :S{3
constant_t( const Tp & t) : t(t) {} }
o"_#\6
template < typename T > xFm{oJ!]&
const Tp & operator ()( const T & r) const SxW}Z_8x
{ aho<w+l@
return t; khN:+V|
} KaQq[a
} ; `?o1cf A
):fu
该functor的operator()无视参数,直接返回内部所存储的常数。 R`C_CsXir
下面就可以修改holder的operator=了 %M)oHX1p
7YXXkdgbd
template < typename T > T3t~=b>&L
assignment < holder, constant_t < T > > operator = ( const T & t) const d! QD vO
{ h
GA0F9.U
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); h>^jq{yu
} mf]( 3ZL
So\| Ye
同时也要修改assignment的operator() X|damI%
Q"6hD?6.
template < typename T2 > e7bT%h9i
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } &^3~=$
现在代码看起来就很一致了。 ?`
eYWZ">
K!D_PxV
六. 问题2:链式操作 `/wq3+ ?
现在让我们来看看如何处理链式操作。 G\:psx/
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 M*~v'L_sI
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 H8<7#
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 :&1=8^B Y
现在我们在assignment内部声明一个nested-struct rGn5QV
%hQMC'c
template < typename T > ;x3 ]4^
struct result_1 J<($L}T*$
{ ]~
#+b>
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; `^&15?Wk
} ; Bsu=^z
bDZKQ&
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: D=82$$
'e<HP Ni)
template < typename T > [zh4W*K_cq
struct ref o3i,B),K
{ 6h:?u4
typedef T & reference; PK2Rj%
} ; @O<@f8-
template < typename T > #lyM+.T
struct ref < T &> K[#v(<)
{ v/aPiFlw
typedef T & reference; KT
lP:pB;
} ; *_{l
5v!DYx
有了result_1之后,就可以把operator()改写一下: ]w_
"%}Gy>;
template < typename T > TJyH/C
typename result_1 < T > ::result operator ()( const T & t) const Gdf1+mi
{ XAQ\OX#
return l(t) = r(t); %TW%|"v
} ^z *):e
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 r(,= uLc
同理我们可以给constant_t和holder加上这个result_1。 da9*9yN
(pT(&/\8
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 co$Hi9JE
_1 / 3 + 5会出现的构造方式是: yBPt%EF
_1 / 3调用holder的operator/ 返回一个divide的对象 }rKJeOo^x?
+5 调用divide的对象返回一个add对象。 ,#P,B;r~
最后的布局是: 0\EpH[m}-
Add k%Ma4_Z
/ \ <m Ju v
Divide 5 z<yNG/M1>U
/ \ e>?_)B4
_1 3 7Ykj#"BZ
似乎一切都解决了?不。 DnG/ n
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 &O+sK4P
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 f!M[awj%
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: h V|v6 _
O?nPxa<
template < typename Right > F_Z&-+,*3t
assignment < XXX, typename picker_maker < Right > ::result > operator = ( const z)58\rtz
Right & rt) const QD.zU/F~>
{ {[M0y*^64$
return assignment < XXX, typename picker_maker < Right > ::result > ( * this , rt); .0nn0)"
} p4m^ ~e
下面对该代码的一些细节方面作一些解释 d]O_E4X*
XXX指的是原来的functor的类型,picker_maker<T>是一个类型变换的trait,如果T是一个常量,那么他会返回constant_t<T>,否则返回T本身。 Sk6b`W7$
因此如果该函数声明在assignment的内部,那么就实现了连等,如果声明在的dereference(解引用)的内部,就允许(*A = B)的行为发生。 toS(UM n
最后,如何把这些函数塞到各个functor的声明里边呢?当然可以用宏,但是。。。大家都知道这样不好。 tr6jh=
除了宏之外还可以用的方式就是继承。我们可以写一个类叫做picker,该类实现了所有的如上的产生函数。然后让所有的functor继承自它。 4
[R8(U[g
且慢,也许立刻就有人跳出来说:这样的话那个XXX怎么写呢?这样不是会导致循环依赖么?这样不是会有downcast么? /v}P)&
正解,让picker做基类确实不是一个好主意。反过来,让picker继承functor却是一个不错的方法。下面是picker的声明: E;6Y? vJ
G$?|S@I,
template < class Action > g
,/a6M
class picker : public Action Hv8SYQ|
{ iGG6Myp-
public : zY7*[!c2
picker( const Action & act) : Action(act) {} ioB|*D<U2
// all the operator overloaded 82j'MgGP
} ; , vY)n6
1% $d D2
Picker<T>继承自T,唯一的作用就是给T添加上了各种操作符的重载函数。 f,Sth7y
现在所有参与行动的functor都要套上一层picker, _1被声明为 picker<holder>, 并且holder中所重载的操作符除了operator()之外全部被移到了picker内。而picker中的操作符重载的返回的functor也必须套上一个picker: vOos*&
mgi,b2
template < typename Right > Jt##rVN
picker < assignment < Action, typename picker_maker < Right > ::result > > operator = ( const Right & rt) const 38[)[{G)Hv
{ O0@w(L-
return assignment < Action, typename picker_maker < Right > ::result > ( * this , rt); `^v4zWDK
} gKmX^A5<
|BwRlE2CFO
Piker_maker返回的也是picker<T>,或者picker<constant_t<T> > k4S} #!
使用picker还带来一个额外的好处。之前提到picker_maker要区分functor和常量,有了picker,区分的方法就非常简单了:凡是属于picker<T>的都是functor,否则就是常量。 Sa%zre@
k/df(cs
template < typename T > struct picker_maker {F'Az1^I=
{ 3LKB;
typedef picker < constant_t < T > > result; }X=87ud
} ; +p13xc?#j
template < typename T > struct picker_maker < picker < T > > :ar?0
{ d!`lsh@tF
typedef picker < T > result; sC% b~
} ; "kX`FaAhY
{I`B[,*
下面总的结构就有了: BR;QY1
functor专心模拟操作符的行为,并实现一个result_1来告诉别人自己的返回类型。 OQ6sv/
picker专心负责操作符之间的产生关系,由它来联系操作符合functor。 :bwM]k*$
picker<functor>构成了实际参与操作的对象。 U);OR
至此链式操作完美实现。 >[a FOA
$Z/klSEf
HeCcF+
七. 问题3 `8,w[o oC2
如何使用多参数的函数对象呢?考虑_1=_2,这个functor必须接受2个参数,因此所产生的assignment对象的operator()必须能接收2个参数。 SC'BmR"ox
CoJ55TAW
template < typename T1, typename T2 > (B&h;U$HAH
??? operator ()( const T1 & t1, const T2 & t2) const NUMi])HkN
{ .Y! :x=e
return lt(t1, t2) = rt(t1, t2); Qu`n&
} JX{KYU
1 o|T
很明显,这个函数的返回类型会依赖于T1,T2,因此result_1已经无法适用,我们就只好再写一个result_2: 9UP:J0 `
kBbl+1{H
template < typename T1, typename T2 > _ENuwBYW-
struct result_2 ^|aNG`|O
{ ,<sm,!^<r
typedef typename ref < typename Left::result_2 < T1, T2 > ::result > ::reference result; 9RxO7K
} ; J^fm~P>.
6yI}1g
显然,各个functor似乎根本不理会各个参数那个是_1, 那个是_2, 那么最后是怎么选择的呢? >\ZR*CS
这个差事就留给了holder自己。 0qv$:w)g+v
.jU Z
j5\$[-';
template < int Order > %,|ztH/ Q
class holder; ~s#e,Kav"
template <> $M':&i5`,
class holder < 1 > t}Ss=0dJO
{ O%-h&C3
public : ^uW%v2
template < typename T > [Uli>/%JB
struct result_1 /BpxKh2p
{ x l0DN{PG
typedef T & result; &x0C4Kh
} ; ,- '4L9
template < typename T1, typename T2 > DZe}y^F
struct result_2 w(BH247`
{ )p8I@E
typedef T1 & result; o9Sn*p-.
} ; HM&1yubh#
template < typename T > <tbZj=*O/o
typename result_1 < T > ::result operator ()( const T & r) const xMI+5b8
{ knT.l"
return (T & )r; Q>8pP \ho
} sS!w}o2X
template < typename T1, typename T2 > j$x)pB3]
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const zoP%u,XL
{ VXm[-
return (T1 & )r1; F98i*K`"
} H9`
f0(H
} ; G#[*|+f8
pm USF #u
template <> 0xpx(T[
class holder < 2 > KWhZ +i`
{ *Msr15
public : Y
?'tUV
template < typename T > :gI.l1
struct result_1 c8A`<-\MfB
{ }+RB=#~o
typedef T & result; X=~V6m
} ; lIf(6nm@
template < typename T1, typename T2 > 7*s8ttX
struct result_2 +.Bmkim
{ R1ktj
typedef T2 & result; V U~Dk);Bv
} ; & ,L9O U
template < typename T > ~`eHHgX
typename result_1 < T > ::result operator ()( const T & r) const S>Z|)I
{ Owf.f;QR
return (T & )r; P<;7j?
} #[ -\lU|
template < typename T1, typename T2 > 4MW ]EQ-
typename result_2 < T1, T2 > ::result operator ()( const T1 & r1, const T2 & r2) const |(% u}V?
{ eThy+
return (T2 & )r2; KhaYr)&~
} HIf{Z* mb
} ; 0ys~2Y!eH
m)&znLA
RL}KAGK
新的holder变成了holder<int>, holder<n>的n个参数的operator()会返回第n个参数的值。而_1,_2也相应变为picker<holder<1> >, picker<holder<2> >。 .T.5TMiOSq
现在让我们来看看(_1 = _2)(i. j)是怎么调用的: {G*QY%j^
首先 assignment::operator(int, int)被调用: Bw<rp-
H+ZSPHs
return l(i, j) = r(i, j); BC/_:n8O
先后调用holder<1>::operator()(int, int)和holder<2>::operator()(int, int) {3edTu
KN[d!}W:
return ( int & )i; {'bip`U.
return ( int & )j; R+=a`0_S
最后执行i = j; 85 ]SC$
可见,参数被正确的选择了。 `M@Ak2gcR+
|)U|:F/{@
3|kgTB-
8cVzFFQP
fA^Em)cs2
八. 中期总结 <GIwRVCU
目前的结果是这样的,为了支持一个操作符,我们需要作如下几件事: jqcz\n d
1。 实现一个functor,该functor的operator()要能执行该操作符的语义
CjL<