一. 什么是Lambda d{UyiZm\
所谓Lambda,简单的说就是快速的小函数生成。 F0O/SI(cA
在C++中,STL的很多算法都要求使用者提供一个函数对象。例如for_each函数,会要求用户提供一个表明“行为”的函数对象。以vector<bool>为例,如果想使用for_each对其中的各元素全部赋值为true,一般需要这么一个函数对象, a|*{BlY
ov{
uIG,2u,
ZE ())W"
class filler wgK:^DP
{ ;_.%S *W\
public : !z
!R)6
void operator ()( bool & i) const {i = true ;} Sc!{
o!9\
} ; :<
;'.[h*u~<
0u]!C"VX
这样实现不但麻烦,而且不直观。而如果使用lambda,则允许用户使用一种直观和见解的方式来处理这个问题。以boost.lambda为例,刚才的问题可以这么解决: j0p'_|)(
6iiH+Nc
-/>SdR$D7
=kp-[7
for_each(v.begin(), v.end(), _1 = true ); O<0G\sU
z9k3@\7
Z\{"/( Hi
那么下面,就让我们来实现一个lambda库。 Ut;,Z
`wJR^O!e
6]=R#d 7U
+Mb;;hb
二. 战前分析 uY,(3x
首先要说明的是,我并没有读过boost.lambda或其他任何lambda库的代码,因此如代码有雷同,纯属巧合。 TNA?fm
开始实现以前,首先要分析出大致的实现手法。先让我们来看几段使用Lambda的代码 6gLk?^.
t,mD{ENm&
y{.s
4NT
for_each(v.begin(), v.end(), _1 = 1 ); %<|w:z$vp
/* --------------------------------------------- */ -.8 nEO3
vector < int *> vp( 10 ); mCa[?
transform(v.begin(), v.end(), vp.begin(), & _1); }{J5)\s9
/* --------------------------------------------- */ K5O#BBX=
sort(vp.begin(), vp.end(), * _1 > * _2); zFy0SzF
/* --------------------------------------------- */ KaJCfu yp
int b = * find_if(v.begin, v.end(), _1 >= 3 && _1 < 5 ); vI<n~FHt
/* --------------------------------------------- */ 9oly=&lJ
for_each(vp.begin(), vp.end(), cout << * _1 << ' \n ' ); <q
V<dK&W
/* --------------------------------------------- */ 28KS*5S
for_each(vp.begin(), vp.end(), cout << constant( ' \n ' ) << * _1); a=<l}`*
`u%`Nj
c~B[<.Qj
<1HbjRw
看了之后,我们可以思考一些问题: j4v.8;
1._1, _2是什么? *C~O[:6D
显然_1和_2都满足C++对于标识符的要求,可见_1和_2都是对象。 9o|=n'o
2._1 = 1是在做什么? 9sQ4
$
既然_1是一个对象,那么_1的类必然重载了operator=(int)。那么operator=返回什么呢?该函数所返回的对象被传入for_each的第3个参数,可见其返回了一个函数对象。现在整个流程就很清楚了。_1 = 1调用了operator=,其返回了一个函数对象,该函数对象能够将参数1赋值为1。 kKU,|>3h
Ok,回答了这两个问题之后,我们的思路就很清晰了。如果要实现operator=,那么至少要实现2个类,一个用于产生_1的对象,另一个用于代表operator=返回的函数对象。 \/3Xb
O@@=ZyYwc
GXV<fc"1
三. 动工 WD=#. $z$
首先实现一个能够范型的进行赋值的函数对象类: N`FgjnQ`
"XWrd[Df
CNCWxu
}B{bM<dF
template < typename T > K&zp2V
class assignment uyt]\zVT
{ qNI2+<u)j
T value; ('q u#.'
public : y$=$Yc&Ub
assignment( const T & v) : value(v) {} uqaP\
template < typename T2 > yF&"'L
T2 & operator ()(T2 & rhs) const { return rhs = value; } \,<5U
F0
} ; zJnF#G
0v%ZKvSID
fVlTsc|e
其中operator()被声明为模版函数以支持不同类型之间的赋值。 o ]UG*2
然后我们就可以书写_1的类来返回assignment $F|3VQ~
[whX),3>
N? r{Y$x
c2aX_ "
class holder ZXP9{Hh
{ 3g!tk9InG
public :
UADD 7d
template < typename T > oe<9CK:?>
assignment < T > operator = ( const T & t) const "*E#4e[
{ Rf)lFi
return assignment < T > (t); & 5!.!Z3
} :"Vfn:Q
} ; Uq0GbLjv"
qJ).;S{AAt
|{ E\ 2U
由于该类是一个空类,因此我们可以在其后放心大胆的写上: T%
ys+ AY^/
static holder _1; E1(2wJ-3"
Ok,现在一个最简单的lambda就完工了。你可以写 KkVFY+/)
ZJCD)?]=3
for_each(v.begin(), v.end(), _1 = 1 ); ZP>KHiA
而不用手动写一个函数对象。 >7yOu!l
>syQDB
HmWU;9Vn+
86bl'FdKS
四. 问题分析 s8,N9o[.~P
虽然基本上一个Lambda已经初步实现出来了,但是仔细想想,问题也是很多的。 L*TPLS[lh
1, 我们现在是把_1和functor看成两个不同的存在,会导致代码的重复。 xz1jRI$
2, 目前这个Lambda还无法实现如_1 = 2 = 3这样的链式操作。 ][ri
A
3, 我们没有设计好如何处理多个参数的functor。 zKycd*X
下面我们可以对这几个问题进行分析。 's.%rre%
UZ8
vZ
五. 问题1:一致性 r;gtfX*
首先来看看1,合并_1和functor的最佳方法就是把_1本身也变成functor。那么_1的operator()会做什么事情呢?| pBW|d\8
很明显,_1的operator()仅仅应该返回传进来的参数本身。 .VFa,&5;3
t{\,vI
struct holder {ZiZ$itf
{ 9C?;'
// )<w`E{q
template < typename T > 6\MH2&L<
T & operator ()( const T & r) const g<,kV(_7
{ [yzDa:%
return (T & )r; T~shJ0%
} JZQT}
} ; Gw3H1:yo
PP\nR
@
这样的话assignment也必须相应改动: *\9JIi 2
H5@N<v5u
template < typename Left, typename Right > RQzcsO
class assignment rQ0V3x1"Qx
{ o)_;cCr)q
Left l; ?LP&VU1
Right r; 7_,)"J2^
public : wB(A['k
assignment( const Left & l, const Right & r) : l(l), r(r) {} N1dp%b9W(
template < typename T2 > 4a'GWzUtS
T2 & operator ()(T2 & rhs) const { return l(rhs) = r; } {fi:]|<1h
} ; ES~ykE
Ey5E1$w%&
同时,holder的operator=也需要改动: Z:Hk'|q}I
A"wor\(
template < typename T > iHKWz)0
assignment < holder, T > operator = ( const T & t) const ^j"*-)R
{ m2!y;)F0
return assignment < holder, T > ( * this , t); iqCZIahf
} dA;f`Bi;Q
%_*q'6K
好,这样holder也成为了一个functor,这为我们以后添加功能节省了很多代码。 B^W0Ik`m
你可能也注意到,常数和functor地位也不平等。 yqdhLX|Mk
|Gc2w]\3
return l(rhs) = r; RS'%;B-)
在这一句中,r没有调用operator()而l调用了。这样以后就要不时的区分常数和functor,是不良的设计。 p=T,JAI t
那么我们仿造holder的做法实现一个常数类: Ol8ma`}Nq3
j5lSu~
template < typename Tp > m791w8Vr
class constant_t 9UD~$_<\
{ 2Z3c` /k
const Tp t; _7?LINF9
public : /UGH7srx
constant_t( const Tp & t) : t(t) {} ~(2G7x)
template < typename T > &"v h=Z-
const Tp & operator ()( const T & r) const 9v_B$F$_T
{ 0E9LZOw4T
return t; Mz}yf5{f
} XWQp-H.
} ; joa|5v'
>L6V!
该functor的operator()无视参数,直接返回内部所存储的常数。 #q`-"2"|
下面就可以修改holder的operator=了 1:I47/
$0[T=9q <+
template < typename T > MjIp~?*
assignment < holder, constant_t < T > > operator = ( const T & t) const tOn_S@/r
{ n !ty\E
return assignment < holder, constant_t < T > > ( * this , constant_t < T > (t)); 1-.UkdZ}
} X|Gsf=
1S
e<_p\LiOS
同时也要修改assignment的operator() vh8{*9+
Eeemy*U
template < typename T2 > mz\d>0F U.
T2 & operator ()(T2 & rhs) const { return l(rhs) = r(rhs); } _KSYt32N
现在代码看起来就很一致了。 N :E7rtT,M
&r\pQ};
六. 问题2:链式操作 VH3j
现在让我们来看看如何处理链式操作。 fL[(;KcAa
其实问题1已经为我们处理掉了大量的问题。如果_1,functor,常量彼此之间不统一为functor,那么链式操作的时候就要时刻小心一个对象是_1还是functor还是常量,会大大增加编码的难度。 n
GE3O#fv
事实上,首先要解决的是,如何知道一个functor的operator()的返回值的类型。遗憾的是,我并没有找到非常自动的办法,因此我们得让functor自己来告诉我们返回值的类型。 ht8%A 1|
比较麻烦的是,operator()的返回值一般和其参数的类型相关,而operator()通常是一个模版函数,因此其返回值类型并不能用一个简单的typedef来指定,而必须实现一个trait。 8 Zy`Z
现在我们在assignment内部声明一个nested-struct b<UZDy N~
K*Tj;
template < typename T > `>^2MHF3LT
struct result_1 X9^a:7(
{ W (N@`^
typedef typename ref < typename Left::result_1 < T > ::result > ::reference result; ZJz6{cY
} ; (;^VdiJ
)M5:aSRz
那么如果参数为T,其返回值类型就为result_1<T>::result。上面代码的ref<T>为一个类型转换类,作用是返回T的引用。不直接加上&符号的原因是如果T本身就是Q的引用Q&,那么Q&&是非法的。因此ref的实现即为: q5il9*)d(
V!=1 !"}OG
template < typename T > $j(2M?.>#
struct ref g%1FTl
{ #S+GI!
typedef T & reference; cES3<`[K
} ; " $5J7
template < typename T > 0m?v@K' l
struct ref < T &> Vw7NLTE}`
{ C!N&uNp@s
typedef T & reference; f]F]wg\_f
} ; m
S[Vl6
_aOisN{
有了result_1之后,就可以把operator()改写一下: `.PZx%=
ax7]>Z=%d"
template < typename T > 7T
\}nX1
typename result_1 < T > ::result operator ()( const T & t) const CrHH Ob
{ a}l^+
return l(t) = r(t); !@E=\Sm8EV
} RH+3x7l
可能大家已经注意到我定义assignment的operator()的返回类型的时候,是直接将其定义为Left的operator()返回类型的引用形式,如果实际上处理的对象的operator=并不是按照常理来声明的,那么这段代码可能就编译不过。这的确是一个很麻烦的事情。实际上,在gcc下,使用typeof关键字可以很容易的得到该类型的operator=的返回类型,就可以让这段代码变得更有通用性。然而为了实现可移植性,我不得不放弃这个诱人的想法。 7o?6Pv%HJC
同理我们可以给constant_t和holder加上这个result_1。 p;av63i
`PI,tmv!
有了这个result_1,链式操作就简单多了。现在唯一要做的事情就是让所有的functor都重载各种操作符以产生新的functor。假设我们有add和divide两个类,那么 WZ}c)r*R
_1 / 3 + 5会出现的构造方式是: "7_6iB&@<
_1 / 3调用holder的operator/ 返回一个divide的对象
yE3g0@*
+5 调用divide的对象返回一个add对象。 M~Tq'>Fn
最后的布局是: <'H^}gQow
Add |n-NK&Y(o
/ \ lUXxpv1m
Divide 5 U[9`:aV;
/ \ BwO^F^Pr?k
_1 3 f`@$saFD
似乎一切都解决了?不。 ^`
N+mlh
你可以想象一下一个完整的Lambda库,它必然能够重载C++几乎所有的操作符。假设其重载了10个操作符,那么至少会有10个代表这些操作符的functor类。大体上来讲,每一种操作符所对应的functor都应当能够由链式操作产生别的任意一种操作符所对应的functor。(例如:*_1 = 2既是由operator*的functor产生operator=的functor)。可想而知这样一共能产生10*10=100种产生方式。这是对编码的一个大挑战。 BR5r K
如何简化这个问题呢?我们不妨假定,任意一种操作符的functor,都能够产生任意一种操作符的functor,这样,每一种操作符的functor都拥有一样的产生方案。如果某种转换确实是不合法的(例如:A/B=C无论如何也不可能合法),那么在试图产生新functor的时候会出现编译错误。幸好C++的模版是如果不使用就不编译的,因此这种编译错误不会干扰到正常的使用,这正是我们所要的。 nU$;W
OK,我们的方法呼之欲出了。既然所有的functor都具有一样的产生方案,那么不如大家都不要实现,等到最后统一的在所有的functor里面加上这么一系列的产生代码吧。例如,如果要添加从某functor XXX到operator=的functor的产生代码: j*"V!d
z38&