Generic<Programming>: 再談Min和Max

在1995年1月，Scott Meyers在他發表于C++ Report里的一篇名為《min, max and more》[]的文章里，對C++社群提出了一個挑戰。在仔細地分析了基于宏和代表當時模板技術水平的實現后，他得出結論：那么究竟什么才是最好的方法——正確的方法——來實現max？借用Tevye的不朽名言來說：“我告訴你：我不知道?！泵鎸σ陨系姆治?，我越來越覺得我是在告訴人們使用宏的方法可能是最好的，但我討厭宏。如果你知道max的一種優雅實現，請告訴我。據我所知，這個問題跟六年前一樣富有挑戰性。本文將嘗試這個挑戰。

Min和Max

好，我們先來回顧一下Scott的問題?；诤甑膍in一般看起來是這樣的： #define min(a, b) ((a) < (b) ? (a) : (b)) 這個宏工作得很好，因為它非常通用（能支持所有表達式，只要operator<和operator?:有意義）。不幸的是min總是要將每個參數計算兩次，這可能會引起很多混亂。它的用法看上去太象一個函數了，但它的行為卻不象。（關于min和一般的宏所引起的各種問題，如果你想了解更廣泛的討論，請參考Herb的文章[]。）在C++標準庫里，提供了一個基于模板的解決方案，簡單有效： template <class T> 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 <class T> 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 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>來把兩個運算符合成一個，否則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 <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; } 這四個重載的Min對應于const和非const參數的四種可能的組合。

到現在為止，一切順利。但是怎么定義MINTYPE呢？好，能進行類型計算的神圣的技術之一就是traits[]。當然，我們可以這樣來得到Min的類型： #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; }; ... 這雖然可行，但是你要寫非常非常多的代碼。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<FloatingPointTypes, double>::value 結果等于1。如果類型不在typelist里，結果是-1。

2. 我們要用到的第二個工具是Select類模板，它在[]里有詳細描述。簡單來說，Select允許你根據一個編譯時的布爾常量在兩個類型中選擇一個。例如： typedef Loki::Select<sizeof(wchar_t) < 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類模板

為了簡化類型計算，我建立了一個簡單的線性層次，列出各種算術類型?；旧衔沂前凑仗囟樞蛄谐鏊兴阈g類型的：對于任意兩個算術類型，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 <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 ... 兩個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://www.anti-gravitydesign.com