泛型编程：再现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，同时还有一些同步的成员函数。

如下：

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)

{

return lhs < rhs ? lhs : rhs;

}

但是，这样还是不能令人满意。因为编译器不能处理混合类型－一个参数是const，一个是non-const。

例如：

int a;

short int b;

...

int smallest =min(a,b);// error: can''t figure out T

// in template instantiation

不用说，基于宏的min()在这样的情况下又一次表现良好。基于模板的min()，必须这样写：

int smallest = min(a, int(b)); // aha, T is int

要想提供一个好的min/max，我们首先，要使得行为很像macros，同时，要避免macros带来的麻烦。

下面是一个聪明实现的开始：

emplate <class L, class R>

class MinResult {

L& lhs_;

R& rhs_;

public:

operator L&() { return lhs_ < rhs_ ? lhs_ : rhs_; }

operator R&() { return lhs_ < rhs_ ? lhs_ : rhs_; }

MinResult(L& lhs, R& rhs) : lhs_(lhs), rhs_(rhs) {}

};

template <class LR>

class MinResult<LR, LR> {

LR& lhs_;

LR& rhs_;

public:

operator LR() { return lhs_ < rhs_ ? lhs_ : rhs_; }

MinResult(LR& lhs, LR& rhs) : lhs_(lhs), rhs_(rhs) {}

};

template <class L, class R>

MinResult min(L lhs, R rhs)

{

return MinResult(lhs, rhs);

}

为了把两个转换符统一为一个，在MinResult<LR,LR>要进行一些特殊局部处理。不然，L&,R&操作会被认为重复定义。这个方案推迟了计算，直到它需要的时候，同时，在结果取出之前，它表现了良好的惰性原则。例如：

int a, b;

...

min(a, b);

实际上，上面的代码，没有做别的事情，同时，如果，你对类型有很多的思考的话，那么这样的代码将使得你对森林中的树的概念有着更多的思考。另一方面，如果，你这么使用：

int c = min (a,b);

那么，编译器将调用int&来转化min返回值(MinResult<int,int>)的临时变量。这个强制转化能够正确的工作，返回无误的结果。

尽管你能够解决完美的const相关问题了，但是MinResult还不是一个完美的方案。我们考虑一下下面的代码：

int a;

short int b;

extern Fun(int);

extern Fun(short int);

...

Fun(min(a, b)); // error! Don''t know which overload to invoke!

MinResult<int,short int>支持两种转化：int&,short int&，结果是，编译器可以调用平等的调用任何一个fun()函数，在这一方面，基于宏的min()又顺利通过，它将调用像你想象的一样Fun(int)函数。

Quest for a Type

那么怎样才能天才般的解决这个问题。假设有两个类型L和R，考虑min(L,R)返回值的正确类型应该...。例如：L是char，R是int，毫无疑问，应该返回int。这样，我们可以清晰的为min()定义四个函数。

template <class L, class R>

MINTYPE(L, R)

Min(L& lhs, R& rhs)

{ return lhs < rhs ? lhs : rhs; }

template <class L, class R>

MINTYPE(const L, R)

Min(const L& lhs, R& rhs)

{ return lhs < rhs ? lhs : rhs; }

template <class L, class R>

MINTYPE(L, const R)

Min(L& lhs, const R& rhs)

{ return lhs < rhs ? lhs : rhs; }

template <class L, class R>

MINTYPE(const L, const R)

Min(const L& lhs, const R& rhs)

{ return lhs < rhs ? lhs : rhs; }

这四个重载的函数对应着在const和non-const之间四个可能的组合。这个主意不错，但是，我们该怎样来定义MINTYPE?我们知道有一个对应的技术traits，的确我们可以使用traits来完成MINTYPE比如：

#define MINTYPE(L, R) typename MinTraits<L, R>::Result

template <class L, class R> struct MinTraits;

// Specialization for the L == R case

template <class LR> struct MinTraits<LR, LR> {

typedef LR& Result;

};

// Specialization for bool and char

template <> struct MinTraits<bool, char> {

typedef char Result;

};

...

这样实现不错，但是你将不得不写很多糟糕的代码。由于有14数据类型，因此，你将不得不为了每一个组合编MinTraits。其实，你可以简化这个工作，就像macros一样，但是，这不是一个很完美的方案。

这个方案还没有完成，你必须考虑到用户定义的类。

另外，怎样为基类，子类调用Min()函数，看看下面的例子：

class Shape {

...

unsigned int Area() = 0;

};

bool operator<(const Shape& lhs, const Shape& rhs) {

return lhs.Area() < rhs.Area();

}

class Rectangle : public Shape { ... };

void Hatch(Shape& shape)

{

Rectangle frame;

...

Shape& smallest = Min(shape, frame);

... use smallest ...

}

事实上，如果，min()处理Rectangle那么它将返回一个Shape的引用，这样就不好了。由于Rectangle会自动转化为Shape引用类型，这样，我们必须做很多事情。

同时，在上例中，我们也可以看出基于macro的min()函数也不会正常发挥作用，看下例子：

shape < frame ? shape : frame

它将两个参数转化为同样的类型，所以它等同于

shape < frame ? shape :(Shape) frame

显然，这不是我们所希望的(这种糟糕的行为叫slicing)

在这篇文章中实现的min()，能给予你像macro-based版本一样的min()功能，甚至更多。同时，它的实现大概只有80行(包括Max)

我们再温热一下我们的coffee，同时，开始讨论Loki。这些代码使用了Loki，Loki提高比较先进的符号操作，Min()用到的Loki工具有：

1 Typelists Typelists提供正规的Lists，它存储类型，不存储数值。

定义如下：

typedef TYPELIST_3(float, double, long double) FloatingPointTypes;

FloatingPointTypes 中包含三个类型

假设定义一个typelist 变量FloatingPointTypes，和任意类型 T，你可以通过使用编译时刻算法 Loki::TL::IndexOf察觉T是否在 FloatingPointTypes 。

例如：

Loki::TL::IndexOf<FloatingPointTypes, double>::value

将返回1，如果 T不在这个list中返回－1。

2。Select Class Template 它的完全说明在参考 7中，简单的说，Select允许你选择一两个基于编译时刻的Boolean 常量。例如：

typedef Loki::Select<sizeof(wchar_t) <

sizeof(short int), wchar_t, short int>::Result

SmallInt;

SmallInt将是wchar_t,short int 中最小的整数类型。

3 TypeTraits 这是一个模板类它是用来推断类型的，例如判断是否这个类型是指针，这个指针指向什么变量等等。我们在这之使用了NonConstType TypeTraits<T>::NonConstType 是用来转化掉const。

4 Conversion 在参考7 中有它的详细说明。

这个类可以用来检测是不是一个一类型可以隐转化为另外的一个类型。Conversion是整个实现的基础。

The MinMaxTraits Class Template

为了简化类型的计算，我建立了一个简单的线性types结构。首先我把所以types以固定的顺序放入。同时，我假定返回值的类型将是list中靠近底部的类型。定义如下：(不考虑const)

namespace Private

{

typedef TYPELIST_14(

const bool,

const char,

const signed char,

const unsigned char,

const wchar_t,

const short int,

const unsigned short int,

const int,

const unsigned int,

const long int,

const unsigned long int,

const float,

const double,

const long double)

ArithTypes;

}

本身，unsigned types 应该在signed types后面， float 应该int 后面。例如

Min(long,double)那么返回结果应该是double类型，因为在list中double在long后面(译者：我们知道结果也应该是double)

现在，一般的算法就可以计算Min()的结果类型了。如果你的参数类型为不是引用的T，R具有如下条件：

1 假设结果为R。

2 如果R可以隐转化为L,那么可以把结果转化为L型。

3 如果在Private::ArithTypes中R在L的后面，那么，转化结果为R型，这一步要处理很多的数学转化。

4 如果在不要引入临时变量的情况下，L&可以自动的转化为R&，那么结果转化为R&，这一步确保Min(frame,shape)将返回Shape&型。

5 如果在不要引入临时变量的情况下，R&可以自动的转化为L&，那么结果转化为L&，

这一步确保Min(shape,frame)返回Shape&.

在这中间罪艰难的一步是“不引入临时变量的类型间的转化”。本质如果not-const T的引用可以转化为not-const U的引用的话，那么，T可以在引入临时变量的情况下，转化为U。

The Min and Max Overloads

对应于const与not-const的参数的四个不同组合，这里有四个Min(),Max()函数重载了。为了避免在Shape/Rectangle例子中的Slicing问题，Min()有个不同于a<b?a:b的实现。如下：

template <class L, class R>

typename MinMaxTraits<L, R>::Result

Min(L& lhs, R& rhs)

{ if (lhs < rhs) return lhs; return rhs; }

template <class L, class R>

typename MinMaxTraits<const L, R>::Result

Min(const L& lhs, R& rhs)

{ if (lhs < rhs) return lhs; return rhs; }

... two more overloads ...

.. similar Max implementation ...

这两个返回语句确保正确的转化而且没有slicing现象。这四个重载函数可以处理如下的情况：Min(a +b, c + d) 、 Min(a +b, 5)。

分析：

让我看看这个新的实现是怎样满足Scott Meyers''先生的要求的。他的要求如下：

1 函数在语意上要进行类型检查。明显Min()满足。

2 支持const ，non-const 参数。由于重载了四个函数。Min()支持non-const const的参数的任何组合。

3 支持不同参数类型。Min()很显然是支持不同的类型的，它做了大量的智能工作，这是macro和简单模板所无法完成的。Min()消除了不同类型之间的差别。主动的进行类型转化。这个转化过程是掌握在library编写人的手中。

4 不需要强制实例化，Min()不需要。

在不同的指针的情况下(Shape* ,Rectangle*)Min()也能表现的很好。

这是由于算法的第一步所实现的。

Min()的一个重要的特征是它可以一个算法来推断结果类型，而这个算法是你可以编写的。

如果你发现这个算法有什么不满意的地方。你可以自行修改。

很遗憾的是这个实现在一些编译器上无法通过，我知道代码是没有问题的。如果你有什么好的建议请联系我。

Look Ahead in Anger

这些天我在看 The Age of Spiritual Machines by Ray Kurzweil [8]. Kurzweil 说充分证明，在2020左右你将用不到$1000买到一个有人脑一样的机器。在那个时候人们可能再说“你看，在2001年，那些家伙在实现max()还那么困难，一个家伙还特此写了一篇论文，”

min()不重要吗，我不这么认为，最大化，最小化是数学上，现实生活中两个简单的概念。如果，程序语言不能表达这样简单的概念，那么说明在语言的深处，还存在问题。

也许有小孩说“妈妈我不想学语法和字汇，我只想学写诗”这样能成功吗？

如果你写了一个a < b ? a : b，也许你还想它能够处理表达式，它能实现吗？

那么，这里存在一些错误？不只有C++这样，在Java和C#中也如此，因为你知道min和max不是objects。

感谢：

感谢所有参与者，希望大家的支持。

参考文献：

[1] http://aristeia.com/Papers/C++ReportColumns/jan95.pdf

[2] http://cuj.com/experts/1902/alexandr.html

[3] http://www.gotw.ca/gotw/077.htm

[4] A. Alexandrescu. "Traits: the else-if-then of Types," C++ Report, April 2000.

[5] A. Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001).

[6] J. Vlissides and A. Alexandrescu. "To Code or Not to Code," C++ Report, March 2000.

[7] A. Alexandrescu. "Generic<Programming>: Mappings between Types and Values," C/C++ Users Journal Experts Forum, September 2000, http://www.cuj.com/experts/1810/alexandr.html.

[8] R. Kurzweil. The Age of Spiritual Machines: When Computers Exceed Human Intelligence (Penguin USA, 2000).

Andrei Alexandrescu is a Development Manager at RealNetworks Inc. (www.realnetworks.com), based in Seattle, WA, and author of the acclaimed book Modern C++ Design. He may be contacted at http://www.moderncppdesign.com/. Andrei is also one of the featured instructors of The C++ Seminar (www.gotw.ca/cpp_seminar).

译者：感谢所以浏览本文的人，希望大家批评指教。

联系方式： taozhangzhi9@yeah.net

地址：南京市信息产业部电子28研究所

南京市1406信箱39分箱

陶章志

邮编： 210007