泛型编程：再现Min和Max

原文出处：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，同时还有一些同步的成员函数。

如下：

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

来让我们再看看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)