泛型编程:再现Min和Max

2016-01-29 12:21 7 1 收藏

泛型编程:再现Min和Max,泛型编程:再现Min和Max

【 tulaoshi.com - C语言心得技巧 】

泛型编程:再现Min和Max
作者: Andrei Alexandrescu(陶章志译)

原文出处:http://www.cuj.com/documents/s=7996/cujcexp1904alexandr/

在1995年1月,Scott Meyers 在C++ Report杂志上就强调"min,max 对C++社团来说是一个很大的挑战",他对基于macro-based实现的min,max进行认真的分析,对照基于模板的min,max实现,他得到了如下结论:

“对于实现max,什么是最好的方法?”用一句Tevye的名言:“我将告诉你:我不知道”,基于以上分析,我有信心告诉大家宏实现的方法,也许是最好的,不过,我个人很讨厌:宏。因此,大家如果有什么更好的实现方法,请赶快告诉我。

根据我个人的知识,在今天这个时候,这个挑战依然存在,在这篇文章中,我将面对这个挑战,但是,在我开始之前,让我们来回忆一下以前泛型编程,是如何糟糕实现这个算法的。

自从"Generic<Programming: volatile - Multithreaded Programmer''s Best Friend" 发表后,我接到很多邮件。在这些邮件中,我接到很多的嘉奖,同时,也有很多对the Usenet newsgroups comp.lang.c++新闻组和 comp.programming.threads的抱怨。这个讨论比较激烈,如果,你有兴趣,你可以去参加。标题是:"volatile, was: memory visibility between threads."一个讨论。

在这些讨论中,我觉得,我学到很多的知识,在这里很多独立的例子,好了,长话短说,很多系统不会修改volatile 数据(例如在POSIX编译系统中),同时在另外的一些系统中,加入volatile量,也无助于程序的质量提高,关于volatile mutexes正确使用的最重要问题,是它依赖于类似于posix mutexes,同时,在多进程系统中,这种互斥量往往是不够的,因此,你必须使用内存保护。

另外一个更具有哲学意义的问题是,严格的讲,volatile规则远离变量是不合理的,就算你添加的volatile符合你应用volatile的规则。

一个系统能存储volatile数据在不同的位置,不像non-volatile数据那样,因此,固定其存储地址将使得系统不稳定。volatile的正确性也是另外一个被批评的对象,尽管它可以在低水平的race condition,但是,不能在更高的层次检测逻辑上的race condition。例如,你有一个像std::vector的类mt_vector,同时还有一些同步的成员函数。

如下:

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com)
volatile mt_vector<int> vec;...if (!vec.empty()) {vec.pop_back();}

原来的想法是从容器vector中移走最后一个元素,在单线程环境下,这段代码会运行的很好,但是,如果你在多线程使用这样的代码,往往会出现异常的,就算你的empty(),pop_bock()已经适当的同步了。因此,可以说,低层次的数据一致性得到保护,但是,更高水平的数据操作,往往是不稳定的。

至少,根据以上的分析,我开始坚持我的求证volatile方法,这是个有效检测在类似posix互斥量race conditions的好方法。但是,如果你从事多进程系统的内存存取权限安排的话,那么,你首先应该细听你的编译器文档资料。你应该知道你该干什么。Kenneth Chiu 提到一篇很有趣的论文: http://theory.stanford.edu/~freunds/race.ps, pape讲解了 "Type-Based Race Detection for Java."

由于Java类型系统只有很少的限制条件,这就使得编译器有可能和程序员一起来在编译时刻检测race conditions。

Min 和Max

(本文来源于图老师网站,更多请访问http://www.tulaoshi.com)

来让我们再看看Scott提出的挑战,基于宏定义的min()如下:

#define min(a, b) ((a) < (b) ? (a) : (b))

由于它是完全范型的,因此,它常常能很好的发挥作用。(只要这个表达式中 < 、?是有定义的)很不幸的是min()总是要计算它中间一个参数两次,这样,就导致很多令人困惑的问题。(译注:假如如下调用,a=3,b=5 int c=min(a++,b);结果我们会得到c=4的结果。显然不是我们所希望的)宏定义只是在表面形式上跟函数相像,但是,它的行为往往跟函数两个样。(如果你想得到更多的相关知识,那么,你可以查阅Herb的有关这方面的资料)在C++标准库中有一个更加有效的实现,它是基于模板的解决方案,如下:

const T& min(const T& lhs, const T& rhs){return lhs < rhs ? lhs : rhs;}

你可以看出这个方案中参数和返回值都是const型,这也就导致一个问题。也许,你想把两个数值中小的那个的数值加2,那么,你也许会这么写:

double a, b;...min(a, b) += 2;

基于宏定义min()就不会出现问题,但是,如果是模板基于模板上实现就不会那么听话了。因为你是不能改变const变量的值的,如同Scott所注意的一样。我们来更新我们的实现:

T& min(T& lhs, T& rhs)
                        

来源:http://www.tulaoshi.com/n/20160129/1485720.html

延伸阅读
觉得作者写得太好了,不得不收藏一下。 对这个例子的理解: //类型参数不能用基本类型,T和U其实是同一类型。 //每次放新数据都成为新的top,把原来的top往下压一级,通过指针建立链接。 //末端哨兵既是默认构造器创建出的符合end()返回true的节点。 代码如下: //: generics/LinkedStack.java // A stack implemented with an internal l...
Java 5 提供泛型支持,泛型支持是开发人员多年以来所要求的特性。它代表了 Java 编程语言一次具有重要意义的升级。像泛型这么复杂的技术,不仅对工具供给商也对开发人员带来了挑战。 !-- frame contents -- !-- /frame contents -- 本文着重介绍 Eclipse 如何应对泛型挑战以及泛型给 Java 语言带来的变化,展示了如何在 Eclipse 中...
泛型是Java SE 1.5的新特性,泛型的本质是参数化类型,也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中,分别称为泛型类、泛型接口、泛型方法。 Java语言引入泛型的好处是安全简单。 在Java SE 1.5之前,没有泛型的情况的下,通过对类型Object的引用来实现参数的“任意化”,“任意化”...
    看过电影《英雄》的观众一定对场景中那优美的意境所感染,其中有一段场景是章子怡同张曼玉在一处遍地黄叶的树林中比武。从画面来看,意境就极之凄美。张曼玉和章子怡于烈风中对打,黄叶在身边旋绕飞舞,据说场景中的黄树叶是导演张艺谋发动老乡捡来的,因此令画面效果更加丰富(如图1-1所示)。 其实这种黄叶漫天飞舞...
返回给出的零个或多个数值表达式中较小的值。 Math.min( [ number1 [, number2 [. . . [, numberN ]]]] ) 可选项 number1, number2, . . ., numberN 参数为需要进行比较的数值表达式。 说明 假如没有给出参数,返回值等于 POSITIVE_INFINITY 。假如有参数为 NaN ,返回值也为 NaN 。

经验教程

855

收藏

77
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部