牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

使用STL仿函数和判断式来降低复杂性并改善可读性

from:http://www.builder.com.cn/2003/1030/100158.shtml

使用STL仿函数和判断式来降低复杂性并改善可读性
作者: 周靖

标准模板库(STL)包含C++程序员不可或缺的许多东西。它还有力证明了C++的概念化编程能力。STL的概念包括容器(container)、范围(range)、算法(algorithm)以及仿函数(functor)。本文着重讲解仿函数,它本质上是一个类,但通过重载operator(),所以行为与函数相似。这个概念在STL之前便已存在,STL只是从另一个角度来看待它。继续阅读本文,你就能体会到个中三味。

 

算法、范围和函数

STL以泛型方式来处理函数。假如一个参数的行为应该与函数相仿,STL算法就不关心它是一个实际的C++函数,还是一个仿函数。出于本文的目的,假定某个类有一个重载的operator(),而且重载的operator()要求获取一个参数,我们就将这个类称为“一元仿函数”(unary functor);相反,如果重载的operator()要求获取两个参数,就将这个类称为“二元仿函数”(binary functor)。

STL算法适用于范围。你可使用函数,并将它们应用于一个范围中的每个元素(参见清单A)。这样一来,就可以处理三种类型的函数:

 

  • 获取零个参数的函数,也称为“生成器”(generators),它们能生成范围。例如,假定一个函数能生成斐波那契数字,那么对该函数的每一个调用都能生成斐波那契数列中的下一个数字。
  • 获取一个参数的函数(一元函数)。
  • 获取两个参数的函数(二元函数)。

这其实已覆盖了大多数情况。极少数情况下,你要求函数获取3个或者3个以上的参数。在这种情况下,可考虑采取其他方式。例如,可将多个参数打包到一个结构中,再按引用传递它。

仿函数:用途和适用的场合

之所以要开发仿函数(functors),是因为函数不能容纳任何有意义的状态。例如,使用函数,你不能为某个元素加一个任意值,再将其应用于一个范围。但是,使用仿函数可轻易做到这一点,如清单B所示。

这演示了仿函数的一个主要优点——它们可以有背景(context)或状态。下面是使用仿函数时要记住的要点:

 

  • 仿函数以传值方式传给一个算法。
  • 每次只能应用一个仿函数,方法是为范围中的每个元素应用operator()。
  • 使用仿函数,可对范围中的每个函数做某事(比如为每个元素都乘以5),可基于整个范围来计算某个有意义的结果(比如求所有元素的平均值),或者同时进行这两种操作。
  • 对于一个给定的范围,仿函数不知道它要应用于多少个元素。

假定你要创建一个函数,要求它在给定一个范围的情况下,能为每个元素都返回当前已处理的所有元素的平均值。换言之:

  • 处理x1时,返回x1
  • 处理x2时,返回(x1 + x2) / 2
  • 处理x3时,返回(x1 + x2 + x3) / 3

清单C展示了怎样实现这个任务。

 

只要亲自编写和使用一下仿函数,就会体会到它具体如何降低复杂性。你不必关心整个范围,只需将注意力集中在一个元素上。这同时还有助于改善代码的可读性。清单D给出了示范性的generate_fibonacci代码。

 

 

前面讲述的都是一元仿函数。二元仿函数同等重要。二元仿函数同时应用于两个范围,或者应用于某个范围中的两个元素。二元仿函数的operator()要求获取两个参数,而不是一个。假定你有两个范围,分别有相同数量的元素,而你希望构建一个新的范围,比如:

  • 第一个元素:x1 * y1
  • 第二个元素:- x2 * y2
  • 第三个元素:x3 * y3
  • 第四个元素:- x4 * y4,等等。

清单E给出了一个示范性的实现。

 

为什么需要判断式


“判断式”(predicates)是仿函数的特例。事实上,你要写的许多仿函数都是判断式。假如一个仿函数返回的值能转换成bool类型(可为true或false),这个仿函数就是判断式。一元判断式(获取一个参数)能实现“筛选”,如清单F所示。

二元判断式能实现“比较相等性”和“排序”(比较两个值,判断一个是否小于另一个)。清单G展示了怎样比较两个范围的“近似”相等性。

不要低估判断式的重要性。下一次写代码时,注意一下你会在筛选、比较相等性以及排序上花费多少时间。使用判断式,不仅能节省大量时间,还能使编码工作更加轻松惬意。除此之外,代码还会变得更容易理解。

使用绑定仿函数

仿函数和判断式的真正优势反映在它们与binder组合使用的时候。binder允许为二元仿函数或判断式绑定一个值,从而将那个值固定下来。你可以绑定第一个或者第二个参数。随即,二元仿函数会变成一元仿函数。比如:

  • f = std::bind1st( functor, v); 'f( x)'等价于'functor( v, x)'
  • f = std::bind2nd( functor, v); 'f( x)'等价于'functor( x, v)'

你可以绑定一个二元仿函数,获得一个一元仿函数,再把它应用于一个范围。例如,假定我们要在一个范围中找出小于10的所有元素清单H展示了具体怎样做。

 

清单I所示,如果综合运用binder、仿函数和算法,就能获得多个方面的好处,包括:

  • 可以只打印小于一个给定值的元素。
  • 可以对范围进行分区,一个分区包含小于或等于一个值的元素,另一个分区则包含不小于那个值的元素。
  • 可以使范围中的所有元素都乘以一个值。
  • 可以移除大于一个给定值的所有元素。
  • 可以替换大于或等于一个值的所有元素。

STL配套提供了大量预定义的仿函数和判断式,包括std::lessstd::greaterstd::plusstd::minus,它们都在<functional>标头中。


 
更多信息

建议阅读由SGI提供的STL文档
其他不错的参考资料包括:
Andrei Alexandrescu,,Modern C++ Design
Scott Meyers,Effective STL

 



可配接函数

在泛型编程中使用仿函数时,有时想要知道仿函数的参数类型以及/或者仿函数的返回类型。例如,假定我们要实现bind2nd,,如清单J所示。

 

 

由于bind1stbind2nd是如此重要,所以人们研究出了同时支持两者的一个方案,这就是“可配接函数”(adaptable functions)。可配接函数具有嵌套的typedef,它允许客户端知道函数的参数和函数的返回类型。对于一元可配接仿函数来说,我们有argument_typereturn_type。对于二元可配接仿函数来说,我们有first_argument_typesecond_argument_typereturn_type。为了获得这些typedef,简单的办法就是从std::unary_function或者std::binary_function派生出它们。本文的所有程序清单都采用了这个办法。

注意,bind1stbind2nd并非惟一要用到可配接函数的函数。另一些函数也需要;在你写自己的仿函数时,也可能要用到它们。正是因为这个原因,所以我们建议你尽可能使你的仿函数成为“可配接”的。

仿函数的一些局限
虽然仿函数和判断式非常出色,但在写一元和二元仿函数时,仍然必须非常小心。除非与std::for_each算法配合使用,否则它们所容纳的背景(context)应该是保持不变的(如果有任何成员变量,它们应该在构造函数中实例化,并在之后保持不变)。所以,根据C++标准,清单C的例子是有问题的,虽然它在目前所有平台上都能正常地工作(每次应用operator()时,average结构的数据成员都会改变)。

一切才刚刚开始
本文只是接触了泛型编程的一些皮毛。要想真正理解仿函数和判断式,你必须亲自编写并使用它们。只有这样,才能找出越来越多适合使用它们的情况,并真正体会到它们如何与算法良好地配合。



责任编辑:李宁

posted on 2007-09-03 16:01 杨粼波 阅读(342) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理