泛型編程：源起、實現與意義
為什么泛型
泛型編程（Generic Programming）最初提出時的動機很簡單直接：發明一種語言機制，能夠幫助實現一個通用的標準容器庫。所謂通用的標準容器庫，就是要能夠做到，比如用一個List類存放所有可能類型的對象,這樣的事情；熟悉一些其它面向對象的語言的人應該知道，如Java里面這是通過在List里面存放Object引用來實現的。Java的單根繼承在這里起到了關鍵的作用。然而單根繼承對C++這樣的處在語言鏈底層的語言卻是不能承受之重。此外使用單根繼承來實現通用容器也會帶來效率和類型安全方面的問題，兩者都與C++的理念不相吻合。
于是C++另謀他法——除了單根繼承之外，另一個實現通用容器的方案就是使用“參數化類型”。一個容器需要能夠存放任何類型的對象，那干脆就把這個對象的類型“抽”出來，參數化它[1]：
template<class T> class vector {
T* v;
int sz;
public:
vector(int);
T& operator[](int);
T& elem(int i) { return v[i]; }
// ...
};
一般來說看到這個定義的時候，每個人都會想到C的宏。的確，模板和宏在精神上的確有相仿之處。而且的確，也有人使用C的宏來實現通用容器。模板是將一個定義里面的類型參數化出來，而宏也可以做到參數化類型。甚至某種意義上可以說宏是模板的超集——因為宏不僅可以參數化類型，宏實質上可以參數化一切文本，因為它本來就是一個文本替換工具。然而，跟模板相比，宏的最大的缺點就是它并不工作在C++的語法解析層面，宏是由預處理器來處理的，而在預處理器的眼里沒有C++，只有一堆文本，因此C++的類型檢查根本不起作用。比如上面的定義如果用宏來實現，那么就算你傳進去的T不是一個類型，預處理器也不會報錯；只有等到文本替換完了，到C++編譯器工作的時候才會發現一堆莫名其妙的類型錯誤，但那個時候錯誤就已經到處都是了。往往最后會拋出一堆嚇人的編譯錯誤。更何況宏基本無法調試。
注1
實際上，還有一種實現通用容器的辦法。只不過它更糟糕：它要求任何能存放在容器內的類型都繼承自一個NodeBase，NodeBase里面有pre和next指針，通過這種方式，就可以將任意類型鏈入一個鏈表內了。但這種方式的致命缺點是(1)它是侵入性的，每個能夠放在該容器內的類型都必須繼承自NodeBase基類。(2)它不支持基本內建類型（int、double等），因為內建類型并不，也不能繼承自NodeBase。這還姑且不說它是類型不安全的，以及效率問題。
我們再來看一看通用算法，這是泛型的另一個動機。比如我們熟悉的C的qsort：
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
這個算法有如下幾個問題：
1. 類型安全性：使用者必須自行保證base指向的數組的元素類型和compar的兩個參數的類型是一致的；使用者必須自行保證size必須是數組元素類型的大小。
2. 通用性：qsort對參數數組的二進制接口有嚴格要求——它必須是一個內存連續的數組。如果你實現了一個巧妙的、分段連續的自定義數組，就沒法使用qsort了。
3. 接口直觀性：如果你有一個數組char* arr = new arr[10];那么該數組的元素類型其實就已經“透露”了它自己的大小。然而qsort把數組的元素類型給“void”掉了（void *base），于是丟失掉了這一信息，而只能讓調用方手動提供一個size。為什么要把數組類型聲明為void*？因為除此之外別無它法，聲明為任意一個類型的指針都不妥（compar的參數類型也是如此）。qsort為了通用性，把類型信息丟掉了，進而導致了必須用額外的參數來提供類型大小信息。在這個特定的算法里問題還不明顯，畢竟只多一個size參數而已，但一旦涉及的類型信息多了起來，其接口的可伸縮性（scalability）問題和直觀性問題就會逐漸顯現。
4. 效率：compar是通過函數指針調用的，這帶來了一定的開銷。但跟上面的其它問題比起來這個問題還不是最嚴重的。
泛型編程
泛型編程最初誕生于C++中，由Alexander Stepanov[2]和David Musser[3]創立。目的是為了實現C++的STL（標準模板庫）。其語言支持機制就是模板（Templates）。模板的精神其實很簡單：參數化類型。換句話說，把一個原本特定于某個類型的算法或類當中的類型信息抽掉，抽出來做成模板參數T。比如qsort泛化之后就變成了：
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
其中first，last這一對迭代器代表一個前閉后開區間，迭代器和前開后閉區間都是STL的核心概念。迭代器建模的是內建指針的接口（解引用、遞增、遞減等）、前開后閉區間是一個簡單的數學概念，表示從first（含first）到last（不含last）的區間內的所有元素。此外，comp是一個仿函數（functor）。仿函數也是STL的核心概念，仿函數是建模的內建函數的接口，一個仿函數可以是一個內建的函數，也可以是一個重載了operator()的類對象，只要是支持函數調用的語法形式就可成為一個仿函數。
通過操作符重載，C++允許了自定義類型具有跟內建類型同樣的使用接口；又通過模板這樣的參數化類型機制，C++允許了一個算法或類定義，能夠利用這樣的接口一致性來對自身進行泛化。例如，一個原本操作內建指針的算法，被泛化為操縱一切迭代器的算法。一個原本使用內建函數指針的算法，被泛化為能夠接受一切重載了函數調用操作符（operator()）的類對象的算法。
讓我們來看一看模板是如何解決上面所說的qsort的各個問題的：
1. 類型安全性：如果你調用std::sort(arr, arr + n, comp);那么comp的類型就必須要和arr的數組元素類型一致，否則編譯器就會幫你檢查出來。而且comp的參數類型再也不用const void*這種不直觀的表示了，而是可以直接聲明為對應的數組元素的類型。
2. 通用性：這個剛才已經說過了。泛型的核心目的之一就是通用性。std::sort可以用于一切迭代器，其compare函數可以是一切支持函數調用語法的對象。如果你想要將std::sort用在你自己的容器上的話，你只要定義一個自己的迭代器類（嚴格來說是一個隨機訪問迭代器，STL對迭代器的訪問能力有一些分類，隨機訪問迭代器具有建模的內建指針的訪問能力），如果需要的話，再定義一個自己的仿函數類即可。
3. 接口直觀性：跟qsort相比，std::sort的使用接口上沒有多余的東西，也沒有不直觀的size參數。一個有待排序的區間，一個代表比較標準的仿函數，僅此而已[4]。
4. 效率：如果你傳給std::sort的compare函數是一個自定義了operator()的仿函數。那么編譯器就能夠利用類型信息，將對該仿函數的operatpr()調用直接內聯。消除函數調用開銷。
動態多態與靜態多態
泛型編程的核心活動是抽象：將一個特定于某些類型的算法中那些類型無關的共性抽象出來，比如，在STL的概念體系里面，管你是一個數組還是一個鏈表，反正都是一個區間，這就是一層抽象。管你是一個內建函數還是一個自定義類，反正都是一個Callable（可調用）的對象（在C++里面通過仿函數來表示），這就是一層抽象。泛型編程的過程就是一個不斷將這些抽象提升（lift）出來的過程，最終的目的是形成一個最大程度上通用的算法或類。
有人肯定會問，既然同是抽象，那為什么不用基于多態的面向對象抽象呢？比如STL的std::for_each，用Java的多態機制也可以解決：
interface IUnaryFun
{
void invoke(Object o);
}
interface IInputIter
{
IInputIter preIncrement();
boolean equals(IInputIter otherIter);
… // other methods
}
IUnaryFun for_each(IInputIter first, IInputIter last, IUnaryFun func)
{
for(;!first.equals(last); first.preIncrement())
func.invoke(*first);
return func;
}
其實，這里最主要的原因很簡單，效率。面向對象的多態引入了間接調用。當然，并不是說間接調用不好，有些時候，比如確實需要運行期多態的時候，只能訴諸繼承這樣的手段。但當能夠利用編譯期類型信息的時候，為什么要付出不必要的間接調用開銷呢？比如這里的for_each，利用接口來實現其通用性，就付出了所謂的“抽象懲罰”（abstraction penalty）。而C++的模板，就是為了消除這樣的抽象懲罰。利用模板編寫的std::for_each，對于每一個特定的參數類型組合都有一個獨立的，最高效的實例化版本，就跟你手寫一個特定于這些類型的專門的for_each算法一樣[5]。于是抽象懲罰消失了，而這也正是C++模板庫能夠真正被工業界廣泛用在C++最擅長的領域（重視效率的領域）的重要原因之一。
另一方面，對于每一組參數類型組合實例化一個版本出來的做法增加了代碼空間，這是一個典型的以空間換時間的例子，不過對于一門靜態并追求效率的語言來說，這個代碼空間的開銷反正也是必不可少的，因為即便你手動為各種不同的參數類型組合編寫特定的算法版本的話，也是付出一樣的代碼空間開銷，而且還順便違反了DRY原則[6]。此外，由于在抽象的時候不用總想著要建立的接口，所以泛型算法編寫起來也更為直觀。
C++泛型的另一個好處就是，跟面向對象編程的基于繼承和虛函數的運行時多態機制不同，C++模板是非侵入性的。你不需要讓你的類繼承自某個特定的接口才能用于某個算法，只要支持特定的語法接口就行了（比如只要支持begin()調用）。這也被稱為結構一致性（Structural Conformance），意即只要語法結構一致即可。而另一方面，基于接口繼承的面向對象多態則必須要顯式地聲明繼承自一個接口，這就是所謂的名字一致性（Named Conformance）。
當然，泛型支持的靜態多態和虛函數支持的動態多態并沒有任何程度上絕對的優劣之分。它們適用于不同的場合。當類型信息可得的時候，利用編譯期多態能夠獲得最大的效率和靈活性。當具體的類型信息不可得，就必須訴諸運行期多態了。Bjarne Stroustrup曾經用了一個典型的例子來澄清這個區別：
std::vector<Shape*> v;
… // fill v
std::for_each(v.begin(), v.end(), std::mem_fun(&Shape::draw));
這里，v里面到底將來會存放什么類型的Shape，編譯期無法知道，因而必須求助于動態多態。另一方面，編譯器倒的確知道它們都繼承自Shape，利用這僅有的靜態類型信息，我們使用了泛型算法std::for_each和泛型容器std::vector。這里尤其值得注意的是for_each的靜態多態行為：for_each只有一份模板實現，然而根據傳給它的第三個參數（本例中是std::mem_fun(&Shape::draw)）的不同，for_each的行為也不同（這里最終被for_each調用的是Shape::draw，但實際上你可以包裝任何函數，只要這個函數接受一個Shape*型的參數），for_each這種“行為不同”是發生在編譯期的，所以是靜態多態。
前面說過，模板與接口繼承比較，模板是非侵入的。這是C++泛型與面向對象的多態機制的本質區別之一。但實際上，面向對象未必就意味著一定要用接口來實現動態的多態。一些動態類型的腳本語言，如Ruby，它的多態機制就既是運行期（動態）的，又是非傾入性的（不用通過繼承自某個特定的接口來達到復用）。人們把這個叫做Duck Typing[7]。如果不是因為效率問題，其實這樣的多態機制才是最直觀的，從使用方面來說，它既有非侵入性，又沒有只能工作在編譯期的限制。但效率至少在可見的將來、在某些領域仍是一個顧慮。因此像C++這種區分編譯期和運行期多態的語言，仍有其獨特的優勢。
此外，泛型編程的類型安全優勢也讓它從C++走入了其它主流的靜態類型語言當中，尤其是C家族的Java和C#，在前幾年相繼接納泛型。
特化，圖靈完備性，元編程
C++的模板是支持特化的，這就給了它實現編譯期控制結構的可能性，進而帶來了一個圖靈完備的子語言。模板特化的引入原本只是為了效率目的——針對不同的類型提供不同的實現。但后來卻被發現能夠實現編譯期的if/else和遞歸等控制結構。
模板元編程最初由Erwin Unruh在1994年的一次會議上提出；當時他寫了一個程序，在編譯錯誤里面打印出一個素數序列。這個事件在C++歷史上的地位就仿佛哥倫布發現新大陸。用Bjarne Stroustrup的話來說就是當時他當時和其他幾個人覺得太神奇了。實際上，這個事情正標志了C++模板系統的圖靈完備性被發現；后來Todd Veldhuizen寫了一篇paper，用C++模板構建了一個元圖靈機，從而第一次系統證明了C++模板的圖靈完備性。接下來的事情就順理成章了——一些ad hoc的模板元編程技巧不斷被發掘出來，用于建造高效、高適應性的通用組件。最終，David Abrahams編寫了boost庫中的基本組件之一：Boost.MPL庫。Boost.MPL以類型和編譯期常量為數據，以模板特化為手段，實現了一個編譯期的STL。你可以看到常見的vector，你可以看到transform算法，只不過算法操縱的對象和容器存放的對象不再是運行期的變量或對象，而是編譯期的類型和常量。想知道模板元編程是如何用在庫構建中的，可以打開一個Boost的子庫（比如Boost.Tuple或Boost.Variant）看一看。
然而，畢竟C++的模板元編程是一門被發現而不是被發明的子語言。一方面，它在構建泛型庫的時候極其有用。然而另一方面，由于它并非語言設計初始時考慮在內的東西，所以不僅在語法上面顯得不那么first-class（比較笨拙）；更重要的是，由于本不是一個first-class的語言特性，所以C++編譯器并不知道C++元編程的存在。這就意味著，比如對下面這樣一個編譯期的if/else設施[8]：
template<bool b, class X, class Y>
struct if_ {
typedef X type; // use X if b is true
};
template<class X, class Y>
struct if_<false,X,Y> {
typedef Y type; // use Y if b is false
};
typedef if_<(sizeof(Foobar)<40), Foo, Bar>::type type;
編譯器并沒有真的去進行if/else的分支選擇，而是按部就班毫不知情地進行著模板的特化匹配。如果遇到Boost.MPL這樣的模板元編程非常重的庫，就會嚴重拖累編譯速度，編譯器進行了一重一重的特化匹配，實例化了一個又一個的模板實例，就是為了去獲取里面定義的一個typedef，完了之后中間所有實例化出來的模板實例類型全都被丟棄[9]。
模板元編程最全面深入的介紹是Boost.MPL庫的作者David Abrahams的《C++ Template Metaprogramming》，其中的樣章（第三章）[10]對模板元編程作了一個非常高屋建瓴的概覽[11]。
關于模板元編程，需要提醒的是，它并不屬于“大眾技術”。日常編程中極少需要用到元編程技巧。另一方面，C++模板里面有大量ad hoc的技巧，如果一頭扎進去的話，很容易只見樹木不見森林，所以需要提醒初學者的是，即便要學習，也要時刻保持“高度”，始終記得元編程的意義和目的，這樣才不至于迷失在無窮無盡的語言細節中。
C++09——進化
泛型編程在C++中取得了工業程度上的成功，得益于其高效性和通用性。但同時，在經過了近十年的使用之后，C++模板，這個作為C++實現泛型的機制的缺點也逐漸暴露出來。比如其中對于初學者最嚴重的一個問題就是在使用一個模板庫時常常遇到無法理解的編譯錯誤，動輒長達上K字節。這些編譯錯誤很容易把一個初學者嚇走。究其本質原因，為什么編譯器會報出令人難以卒讀的編譯錯誤，是因為在編譯器的眼里，只有類型，而沒有“類型的類型”。比如說，迭代器就是一個類型的類型，C++里面也把它稱為“概念”（Concept）。例如，std::sort要求參數必須是隨機訪問迭代器，如果你一不小心給了它一個非隨機訪問的迭代器，那么編譯器不是抱怨“嘿！你給我的不是隨機訪問迭代器”，而是抱怨找不到某某重載操作符（典型的比如operator+(int)）。因為在編譯器眼里，沒有“迭代器”這么個概念，這個概念只存在于程序員腦子里和STL的文檔里。為了幫助編譯器產出更友好的信息（當然，還有許多非常重要的其它原因[12]），C++09將對“類型的類型”加入first-class的支持，其帶來的眾多好處會將C++中的泛型編程帶向一個新的高度：更友好、更實用、更直觀。
此外，C++的模板元編程尚沒有first-class的語言支持，一方面是因為其運用不像一般的模板編程這么廣泛，因而沒有這么緊急。另一方面，C++09的時間表也等不及一個成熟的提案。如果以后模板元編程被運用得越來越廣泛的話，那first-class的語言支持是難免的。
總結
本文對C++模板，以及C++模板所支持的泛型編程作了一個概覽。著重介紹了泛型編程誕生的原因，泛型編程的過程和意義，與其它抽象手段的比較。并對C++中的模板元編程做了一些介紹。最后介紹了C++模板在C++09中的增強。
[2] http://
en.wikipedia.org/wiki/Alexander_Stepanov
[3] http://www.cs.rpi.edu/~musser
[4] 實際上，STL的區間概念被證明是一個不完美的抽象。你有沒有發現，要傳遞一個區間給一個函數，如std::sort，你需要傳遞兩個參數，一個是區間的開頭，一個是區間的末尾。這種分離的參數傳遞方式被證明是不明智的，在一些場合會帶來使用上不必要的麻煩。比如你想迭代一組文件，代表這組文件的區間由一個readdir_sequence函數返回，由于要分離表達一個區間，你就必須寫：
readdir_sequence entries(".", readdir_sequence::files);
std::for_each(entries.begin(), entries.end(), ::remove);
如果你只想遍歷這個區間一次的話，你也許不想聲明entries這個變量，畢竟多一個名字就多一個累贅，你也許只想：
std::for_each(readdir_sequence(".", readdir_sequence::files), ::remove);
下一代C++標準（C++09）會解決這個問題（將區間這個抽象定義為一個整體）。
[5] 當然，語言并沒有規定模板實例化的底層實現一定要是對每組參數類型組合實例化一個版本出來。但目前的實現，這種方案是最高效的。完全消除了抽象懲罰。另一方面，One size fit all的方案也不是不可行，但總會有間接調用。這也正說明了靜態類型系統的一個典型優點：幫助編譯器生成更高效的代碼。
[6] http://
en.wikipedia.org/wiki/Don't_repeat_yourself
[7] http://
en.wikipedia.org/wiki/Duck_typing
[8] 摘自Bjarne Stroustrup的paper：Evolving a language in and for the real world: C++ 1991-2006
[9] 也正因此，D語言加入了語言直接對模板元編程的支持，比如真正工作在編譯期的static if-else語句。
[10] http://www.boost-consulting.com/mplbook/
[11] 第三章的翻譯見我的blog：《深度探索元函數》http://blog.csdn.net/pongba/archive/2004/09/01/90642.aspx
[12] 由于篇幅原因，這里無法展開詳述Concept對C++泛型編程的其它重要意義，有興趣的可以參見我的一篇blog：《C++0x漫談系列之：Concept! Concept!》。http://blog.csdn.net/pongba/archive/2007/08/04/1726031.aspx