本文共 9054 字，大约阅读时间需要 30 分钟。

Andrei Alexandrescu

ye_feng译　

在1995年1月，Scott Meyers在他发表于C++ Report里的一篇名为《min, max and more》[]的文章里，对C++社群提出了一个挑战。在仔细地分析了基于宏和代表当时模板技术水平的实现后，他得出结论：那么究竟什么才是最好的方法——正确的方法——来实现max？借用Tevye的不朽名言来说：“我告诉你：我不知道。”面对以上的分析，我越来越觉得我是在告诉人们使用宏的方法可能是最好的，但我讨厌宏。如果你知道max的一种优雅实现，请告诉我。据我所知，这个问题跟六年前一样富有挑战性。本文将尝试这个挑战。

Min和Max

好，我们先来回顾一下Scott的问题。基于宏的min一般看起来是这样的：

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

这个宏工作得很好，因为它非常通用（能支持所有表达式，只要operator<和operator?:有意义）。不幸的是min总是要将每个参数计算两次，这可能会引起很多混乱。它的用法看上去太象一个函数了，但它的行为却不象。（关于min和一般的宏所引起的各种问题，如果你想了解更广泛的讨论，请参考Herb的文章[]。）在C++标准库里，提供了一个基于模板的解决方案，简单有效：

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

你可以看到，这个方法在所有地方（参数和返回值）都用了const，这是它的问题之一。假设你想做这样一件事：把两个浮点数a和b中的较小的一个的值加上2。那么你会想这么写：

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

如果用基于宏的min，这样一点也没有问题，但是基于模板的那个就不行了，因为你不能修改const对象。Scott指出，引入第二个版本：

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

同样不能令人满意，因为编译器无法对付混合情况——两个参数一个是const而另一个不是。而且，模板不能很好地处理自动类型转换和提升（promotion），就是说下面的代码不能编译：

int a;short int b;...int smallest = min(a, b); // error: can't figure out T                                // in template instantiation

不用说，基于宏的min在需要类型转换的情况下还是可以很好工作。而用基于模板的方法，你就必须写：

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

提供一个好的min/max实现的要点就是：它的行为要类似于宏，而又没有宏的各种问题。

一个（几乎是）好的开始

下面这个聪明的方法是打破成规思维方式的一个好例子：

template 
   
    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 MinResult
     
       {    LR& lhs_;    LR& rhs_;public:    operator LR() { return lhs_ < rhs_ ? lhs_ : rhs_; }    MinResult(LR& lhs, LR& rhs) : lhs_(lhs), rhs_(rhs) {}};template 
      
       MinResult min(L lhs, R rhs){    return MinResult(lhs, rhs);}
      
     
    
   

我们需要用部分特化的MinResult<LR, LR>来把两个运算符合成一个，否则operator L&和operator R&就会形成重复定义。

基于MinResult的方法把计算推迟到必须的时候，只有在取得结果的时候才会去做计算。比如：

int a, b;...min(a, b);

实际上什么也不做。另一方面，如果你写：

int c = min(a, b);

编译器会调用min返回的MinResult<int, int>临时对象的operator 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!

MaxResult<int, short int>支持两种转换：转成int&和转成short int&。结果编译器无法在Fun的两个重载版本中决定选择哪一个。而基于宏的方法再一次通过了测试，如你所期望的那样，最终会调用Fun(int)。

寻找一个类型

真正能够解决问题的应该是这样一个工具：对于两个类型L和R，能够得到min(L,R)的恰当类型。例如，如果L是char，R是int，那么结果应该是int。假设我们已经有了这么一个工具（让我们叫它MINTYPE），我们就可以得到最终的解决方案，即下面四个函数：

template 
   
    MINTYPE(L, R) Min(L& lhs, R& rhs){ return lhs < rhs ? lhs : rhs; }template 
    
     MINTYPE(const L, R) Min(const L& lhs, R& rhs){ return lhs < rhs ? lhs : rhs; }template 
     
      MINTYPE(L, const R)Min(L& lhs, const R& rhs){ return lhs < rhs ? lhs : rhs; }template 
      
       MINTYPE(const L, const R) Min(const L& lhs, const R& rhs){ return lhs < rhs ? lhs : rhs; }
      
     
    
   

这四个重载的Min对应于const和非const参数的四种可能的组合。

到现在为止，一切顺利。但是怎么定义MINTYPE呢？好，能进行类型计算的神圣的技术之一就是traits[]。当然，我们可以这样来得到Min的类型：

#define MINTYPE(L, R) typename MinTraits
   
    ::Resulttemplate 
    
      struct MinTraits;// Specialization for the L == R casetemplate 
     
       struct MinTraits
      
        {    typedef LR& Result;};// Specialization for bool and chartemplate <> struct MinTraits
       
         {    typedef char Result;};...
       
      
     
    
   

这虽然可行，但是你要写非常非常多的代码。C++里一共有14种算术类型，你必须对于它们间的每一种组合都写一个特化的MinTraits。然后你还必须加入const变种。有一些技巧可以帮你简化这件工作，比如说宏，但是这还不是一流的解决方案。

即使那样，这个方案还不完整。你必须考虑指针和用户定义的类。还有，如果对于基类和派生类调用Min怎么办？比如说你定义了一个Shape类，而且定义了operator<来根据面积对Shape对象排序。

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，并且返回Shape的一个引用，那不是很好吗？因为Rectangle的引用可以自动转换为Shape的引用，所以这是很合理的。

但是，在你开始想做这件事的时候，你的想法已经超出min宏所能做的了。对于上面的例子，min宏不能正确工作，因为表达式：

shape < frame ? shape : frame

将把两部分都转换成同样的类型，所以它相当于：

shape < frame ? shape : Shape(frame)

这不是我们想要的。事实上，它做了一件很糟糕的事——对象切片（slicing）。

这篇文章将讲述一个Min的实现，它能让你得到基于宏的版本的所有优点，并且更多。更好的是，这个实现大小也很合理——总共只有80行左右代码（还包括Max）。感兴趣吗？把你的咖啡放到微波炉里再热一下，我们慢慢谈。

Loki

Okey，刚才我撒谎了。代码只有80行，但这没有把使用的类库计算在内。更确切地说，我用了Loki，在我写的书[]里介绍的一个通用库。在众多功能中，Loki提供了高级的类型操纵手段。Min实现里用到的Loki工具有：

1. Typelists。除了保存的是类型而不是值外，Typelists[]和通常的列表一样。例如下面语句：

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

创建了一个包含三个类型的typelist，保存在FloatingPointTypes里。给出一个typelist（例如FloatingPointTypes）和任意一个类型T，你可以通过一个编译时的算法Loki::TL::IndexOf得到T在typelist里的位置，例如：

Loki::TL::IndexOf
   
    ::value
   

结果等于1。如果类型不在typelist里，结果是-1。

2. 我们要用到的第二个工具是Select类模板，它在[]里有详细描述。简单来说，Select允许你根据一个编译时的布尔常量在两个类型中选择一个。例如：

typedef Loki::Select
   
    <    sizeof(short int), wchar_t, short int>::Result    SmallInt;
   

把SmallInt定义为wchar_t和short int中最小的整数类型。

3. TypeTraits该类模板可以进行各种关于类型的推演，例如“这个类型是指针吗？它指向什么类型？”等等。我们只用到TypeTraits中的NonConstType类型定义。TypeTraits<T>::NonConstType是一个typedef，用来去掉T的const修饰，如果有的话。

4. 最后，我们会用到Conversion类[]，它可以检测任意一个类型是否可以被隐式地转换为另一个类型。Conversion是实现上面提到的关于Shape和Rectangle的魔术的基础。

MinMaxTraits类模板

为了简化类型计算，我建立了一个简单的线性层次，列出各种算术类型。基本上我是按照特定顺序列出所有算术类型的：对于任意两个算术类型，Min的结果都是排在列表后面的那个。下面就是这个列表（现在先不考虑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;}

基本上，无符号类型在有符号类型的后面，尺寸大的类型在尺寸小的后面，浮点类型在整数类型后面。举例来说，如果你把一个long int和一个double传给Min，那么结果将是double类型，因为在ArithTypes中double排在long int后面。

现在来看求Min结果类型的算法。给出两个非引用的类型L和R，那么步骤是这样的：

　先假设Result为R。

　如果R可以被隐式地转换为L，那么把Result改成L。

　如果L和R是算术类型，并且在上面的Private::ArithTypes里R排在L后面，那么把Result改为R。这一步用来处理所有算术转换。

　如果L&可以被自动转换为R&，而不需要引入临时变量，那么把Result改为R&。这一步确保Min(frame, shape) 之类的调用返回Shape&。

　如果R&可以被自动转换为L&，而不需要引入临时变量，那么把Result改为L&。这一步确保Min(shape,frame) 之类的调用返回Shape&。

你可以在下载的代码里看到MinMaxTraits的实现。上面算法里最难的部分就是判断“不牵涉临时变量的转换”。本质上，当一个非const的T的引用可以转换非const的U的引用时，T就可以转换U而不引入临时变量。

Min和Max重载函数

Min和Max各有四个重载函数，对应于const和非const参数的四种组合。为了防止上面Shape/Rectangle例子里所讨论的对象切片（slicing）问题，Min的实现和经典的a < b ? a : b略有不同：

template 
   
    typename MinMaxTraits
    
     ::ResultMin(L& lhs, R& rhs){ if (lhs < rhs) return lhs; return rhs; }template 
     
      typename MinMaxTraits
      
       ::ResultMin(const L& lhs, R& rhs){ if (lhs < rhs) return lhs; return rhs; }... two more overloads ..... similar Max implementation ...
      
     
    
   

两个return语句保证了正确的类型转换，而不会产生对象切片。四个重载函数覆盖了所有混合情况，例如：Min(a + b, c + d)或Min(a + b, 5)。

分析

让我们来看看这个新开发的Min是怎么满足Scott Meyers的要求的。他认为一个好的Min/Max实现应该能做到下面四件事：

1. 提供函数调用的语义（包括类型检查），而不是宏的语义。Min显然可以做到。

2. 支持const和非const参数（包括在同一个调用里混用）。由于那四个重载函数，Min支持const和非const参数的任意组合。

3. 支持两个不同类型的参数（当然指有意义的情况）。Min的确支持不同类型的参数，而且还有很多宏和简单模板方法所达不到的智能：Min会分辨各种算术类型，并进行合理的转换。类型转换的选择过程（基于Private::ArithTypes）可以由库的作者控制。

4. 不需要显式实例化。Min不需要显式实例化。

Min对于指针也可以正确工作（甚至指向不同但有关联的类型的指针，如Shape*和Rectangle*）。这是由于算法中的第一步。

一个值得注意的功能是：Min用了一个可以由你配置的算法来推导结果类型，而不限于类型系统里预先定义的规则。如果你对这里的算法不满意，你通过对它进行调整，可以做到相当多你想做的事情，包括根据语义进行类型选择。例如，unsigned char和unsigned int的最小值始终选unsigned char类型，因为unsigned char的值域包含在unsigned int里。通过改变类型推导算法，你可以做到这样 “聪明” 的类型选择。

到目前为止，一切都非常好，但是还有一点细节需要说明。很遗憾，我可以得到的所有编译器都不能编译Min。公正地说，每个编译器都在不同的代码段中翻了船。我确信代码是正确的，因为如果把那些编译器组合起来就可以编译了。但到现在为止，我还没有见到过一个可以运行的例子。所以，如果你可以得到一个最新的编译器，并且能够试试这段代码的话，请告诉我。

Look Ahead in Anger

这些天我在读Ray Kurzweil的《The Age of Spiritual Machines》[]。Kurzweil认为——而且相当有说服力——在2020年代你将可以用1000美元买到有和人脑一样能力的机器。

当我想到人们——也许就是我自己，希望只是有一点点老，但聪明得多——在20年后再读这篇文章时的情形，我就忍不住想笑。“哎呀，在2001年，这帮家伙用当时最流行的编程语言，连实现min和max这种不需要大脑的东西也会有麻烦。哈，这个人还写了一整篇文章，用了这么多深奥的技术，才把min和max搞定。”

是不是min和max不重要呢？我不这么认为。最小和最大是出现在数学和现实生活中的两个简单概念。如果一个编程语言无法表达数学和生活中的简单概念，那么这个语言一定有很严重的问题。“妈妈，我不在乎单词和文法，我只想写诗！”如果你必须加入一些临时变量，然后写“a < b ? a : b”，而这时候你脑子里实际上想的是“min(expr1, expr2)”，这说明你碰到一个严重问题：你是在用一个只会计算任意两个表达式的最小值的机器工作，而它不能表达最小值的概念。

这里有些不对劲，不是吗？C++不是唯一要指责的。Java和C#——两个被认为更高级的新语言——同样完全没有能力表达min和max。因为，你知道，min和max不是对象。

也许将来这个时期会被称为“对象疯狂”。谁知道呢……我不禁懊恼地问：“程序员，你究竟去向何方？”

致谢

感谢所有在Usenet上参加关于volatile讨论的人们，特别是Dave Butenhof，Kenneth Chiu，James Kanze，Kaz Kylheku，Tom Payne和David Schwartz。

参考书目

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

[] http://www.cuj.com/experts/1902/alexandr.htm

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

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

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

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

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

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

转载地址：http://dmfci.baihongyu.com/