劉未鵬(pongba) /文

C++的羅浮宮(http://blog.csdn.net/pongba)

為什么泛型

　　泛型編程（Generic Programming）最初提出時(shí)的動(dòng)機(jī)很簡單直接：發(fā)明一種語言機(jī)制，能夠幫助實(shí)現(xiàn)一個(gè)通用的標(biāo)準(zhǔn)容器庫。所謂通用的標(biāo)準(zhǔn)容器庫，就是要能夠做到，比如用一個(gè)List類存放所有可能類型的對象,這樣的事情；熟悉一些其它面向?qū)ο蟮恼Z言的人應(yīng)該知道，如Java里面這是通過在List里面存放Object引用來實(shí)現(xiàn)的。Java的單根繼承在這里起到了關(guān)鍵的作用。然而單根繼承對C++這樣的處在語言鏈底層的語言卻是不能承受之重。此外使用單根繼承來實(shí)現(xiàn)通用容器也會(huì)帶來效率和類型安全方面的問題，兩者都與C++的理念不相吻合。

　　于是C++另謀他法——除了單根繼承之外，另一個(gè)實(shí)現(xiàn)通用容器的方案就是使用“參數(shù)化類型”。一個(gè)容器需要能夠存放任何類型的對象，那干脆就把這個(gè)對象的類型“抽”出來，參數(shù)化它[1]：

template<class T> class vector {
T* v;
int sz;
public:
vector(int);
T& operator[](int);
T& elem(int i) { return v[i]; }
//
};

　　一般來說看到這個(gè)定義的時(shí)候，每個(gè)人都會(huì)想到C的宏。的確，模板和宏在精神上的確有相仿之處。而且的確，也有人使用C的宏來實(shí)現(xiàn)通用容器。模板是將一個(gè)定義里面的類型參數(shù)化出來，而宏也可以做到參數(shù)化類型。甚至某種意義上可以說宏是模板的超集——因?yàn)楹瓴粌H可以參數(shù)化類型，宏實(shí)質(zhì)上可以參數(shù)化一切文本，因?yàn)樗緛砭褪且粋€(gè)文本替換工具。然而，跟模板相比，宏的最大的缺點(diǎn)就是它并不工作在C++的語法解析層面，宏是由預(yù)處理器來處理的，而在預(yù)處理器的眼里沒有C++，只有一堆文本，因此C++的類型檢查根本不起作用。比如上面的定義如果用宏來實(shí)現(xiàn)，那么就算你傳進(jìn)去的T不是一個(gè)類型，預(yù)處理器也不會(huì)報(bào)錯(cuò)；只有等到文本替換完了，到C++編譯器工作的時(shí)候才會(huì)發(fā)現(xiàn)一堆莫名其妙的類型錯(cuò)誤，但那個(gè)時(shí)候錯(cuò)誤就已經(jīng)到處都是了。往往最后會(huì)拋出一堆嚇人的編譯錯(cuò)誤。更何況宏基本無法調(diào)試。

注1

　　實(shí)際上，還有一種實(shí)現(xiàn)通用容器的辦法。只不過它更糟糕：它要求任何能存放在容器內(nèi)的類型都繼承自一個(gè)NodeBase，NodeBase里面有pre和next指針，通過這種方式，就可以將任意類型鏈入一個(gè)鏈表內(nèi)了。但這種方式的致命缺點(diǎn)是：(1)它是侵入性的，每個(gè)能夠放在該容器內(nèi)的類型都必須繼承自NodeBase基類。(2)它不支持基本內(nèi)建類型（int、double等），因?yàn)閮?nèi)建類型并不，也不能繼承自NodeBase。這還姑且不說它是類型不安全的，以及效率問題。

　　我們再來看一看通用算法，這是泛型的另一個(gè)動(dòng)機(jī)。比如我們熟悉的C的qsort：

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

　　這個(gè)算法有如下幾個(gè)問題：

1. 類型安全性：使用者必須自行保證base指向的數(shù)組的元素類型和compar的兩個(gè)參數(shù)的類型是一致的；使用者必須自行保證size必須是數(shù)組元素類型的大小。

2. 通用性：qsort對參數(shù)數(shù)組的二進(jìn)制接口有嚴(yán)格要求——它必須是一個(gè)內(nèi)存連續(xù)的數(shù)組。如果你實(shí)現(xiàn)了一個(gè)巧妙的、分段連續(xù)的自定義數(shù)組，就沒法使用qsort了。

3. 接口直觀性：如果你有一個(gè)數(shù)組char* arr = new arr[10];那么該數(shù)組的元素類型其實(shí)就已經(jīng)“透露”了它自己的大小。然而qsort把數(shù)組的元素類型給“void”掉了（void *base），于是丟失掉了這一信息，而只能讓調(diào)用方手動(dòng)提供一個(gè)size。為什么要把數(shù)組類型聲明為void*？因?yàn)槌酥鈩e無它法，聲明為任意一個(gè)類型的指針都不妥（compar的參數(shù)類型也是如此）。qsort為了通用性，把類型信息丟掉了，進(jìn)而導(dǎo)致了必須用額外的參數(shù)來提供類型大小信息。在這個(gè)特定的算法里問題還不明顯，畢竟只多一個(gè)size參數(shù)而已，但一旦涉及的類型信息多了起來，其接口的可伸縮性（scalability）問題和直觀性問題就會(huì)逐漸顯現(xiàn)。

4. 效率：compar是通過函數(shù)指針調(diào)用的，這帶來了一定的開銷。但跟上面的其它問題比起來這個(gè)問題還不是最嚴(yán)重的。

泛型編程

　　泛型編程最初誕生于C++中，由Alexander Stepanov[2]和David Musser[3]創(chuàng)立。目的是為了實(shí)現(xiàn)C++的STL（標(biāo)準(zhǔn)模板庫）。其語言支持機(jī)制就是模板（Templates）。模板的精神其實(shí)很簡單：參數(shù)化類型。換句話說，把一個(gè)原本特定于某個(gè)類型的算法或類當(dāng)中的類型信息抽掉，抽出來做成模板參數(shù)T。比如qsort泛化之后就變成了：

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

　　其中first，last這一對迭代器代表一個(gè)前閉后開區(qū)間，迭代器和前開后閉區(qū)間都是STL的核心概念。迭代器建模的是內(nèi)建指針的接口（解引用、遞增、遞減等）、前開后閉區(qū)間是一個(gè)簡單的數(shù)學(xué)概念，表示從first（含first）到last（不含last）的區(qū)間內(nèi)的所有元素。此外，comp是一個(gè)仿函數(shù)（functor）。仿函數(shù)也是STL的核心概念，仿函數(shù)是建模的內(nèi)建函數(shù)的接口，一個(gè)仿函數(shù)可以是一個(gè)內(nèi)建的函數(shù)，也可以是一個(gè)重載了operator()的類對象，只要是支持函數(shù)調(diào)用的語法形式就可成為一個(gè)仿函數(shù)。
　　通過操作符重載，C++允許了自定義類型具有跟內(nèi)建類型同樣的使用接口；又通過模板這樣的參數(shù)化類型機(jī)制，C++允許了一個(gè)算法或類定義，能夠利用這樣的接口一致性來對自身進(jìn)行泛化。例如，一個(gè)原本操作內(nèi)建指針的算法，被泛化為操縱一切迭代器的算法。一個(gè)原本使用內(nèi)建函數(shù)指針的算法，被泛化為能夠接受一切重載了函數(shù)調(diào)用操作符（operator()）的類對象的算法。
　　讓我們來看一看模板是如何解決上面所說的qsort的各個(gè)問題的：
1. 類型安全性：如果你調(diào)用std::sort(arr, arr + n, comp);那么comp的類型就必須要和arr的數(shù)組元素類型一致，否則編譯器就會(huì)幫你檢查出來。而且comp的參數(shù)類型再也不用const void*這種不直觀的表示了，而是可以直接聲明為對應(yīng)的數(shù)組元素的類型。
2. 通用性：這個(gè)剛才已經(jīng)說過了。泛型的核心目的之一就是通用性。std::sort可以用于一切迭代器，其compare函數(shù)可以是一切支持函數(shù)調(diào)用語法的對象。如果你想要將std::sort用在你自己的容器上的話，你只要定義一個(gè)自己的迭代器類（嚴(yán)格來說是一個(gè)隨機(jī)訪問迭代器，STL對迭代器的訪問能力有一些分類，隨機(jī)訪問迭代器具有建模的內(nèi)建指針的訪問能力），如果需要的話，再定義一個(gè)自己的仿函數(shù)類即可。
3. 接口直觀性：跟qsort相比，std::sort的使用接口上沒有多余的東西，也沒有不直觀的size參數(shù)。一個(gè)有待排序的區(qū)間，一個(gè)代表比較標(biāo)準(zhǔn)的仿函數(shù)，僅此而已[4]。
4. 效率：如果你傳給std::sort的compare函數(shù)是一個(gè)自定義了operator()的仿函數(shù)。那么編譯器就能夠利用類型信息，將對該仿函數(shù)的operatpr()調(diào)用直接內(nèi)聯(lián)。消除函數(shù)調(diào)用開銷。

動(dòng)態(tài)多態(tài)與靜態(tài)多態(tài)

　　泛型編程的核心活動(dòng)是抽象：將一個(gè)特定于某些類型的算法中那些類型無關(guān)的共性抽象出來，比如，在STL的概念體系里面，管你是一個(gè)數(shù)組還是一個(gè)鏈表，反正都是一個(gè)區(qū)間，這就是一層抽象。管你是一個(gè)內(nèi)建函數(shù)還是一個(gè)自定義類，反正都是一個(gè)Callable（可調(diào)用）的對象（在C++里面通過仿函數(shù)來表示），這就是一層抽象。泛型編程的過程就是一個(gè)不斷將這些抽象提升（lift）出來的過程，最終的目的是形成一個(gè)最大程度上通用的算法或類。

　　有人肯定會(huì)問，既然同是抽象，那為什么不用基于多態(tài)的面向?qū)ο蟪橄竽兀勘热鏢TL的std::for_each，用Java的多態(tài)機(jī)制也可以解決：

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;
}

　　其實(shí)，這里最主要的原因很簡單，效率。面向?qū)ο蟮亩鄳B(tài)引入了間接調(diào)用。當(dāng)然，并不是說間接調(diào)用不好，有些時(shí)候，比如確實(shí)需要運(yùn)行期多態(tài)的時(shí)候，只能訴諸繼承這樣的手段。但當(dāng)能夠利用編譯期類型信息的時(shí)候，為什么要付出不必要的間接調(diào)用開銷呢？比如這里的for_each，利用接口來實(shí)現(xiàn)其通用性，就付出了所謂的“抽象懲罰”（abstraction penalty）。而C++的模板，就是為了消除這樣的抽象懲罰。利用模板編寫的std::for_each，對于每一個(gè)特定的參數(shù)類型組合都有一個(gè)獨(dú)立的，最高效的實(shí)例化版本，就跟你手寫一個(gè)特定于這些類型的專門的for_each算法一樣[5]。于是抽象懲罰消失了，而這也正是C++模板庫能夠真正被工業(yè)界廣泛用在C++最擅長的領(lǐng)域（重視效率的領(lǐng)域）的重要原因之一。

　　另一方面，對于每一組參數(shù)類型組合實(shí)例化一個(gè)版本出來的做法增加了代碼空間，這是一個(gè)典型的以空間換時(shí)間的例子，不過對于一門靜態(tài)并追求效率的語言來說，這個(gè)代碼空間的開銷反正也是必不可少的，因?yàn)榧幢隳闶謩?dòng)為各種不同的參數(shù)類型組合編寫特定的算法版本的話，也是付出一樣的代碼空間開銷，而且還順便違反了DRY原則[6]。此外，由于在抽象的時(shí)候不用總想著要建立的接口，所以泛型算法編寫起來也更為直觀。

　　C++泛型的另一個(gè)好處就是，跟面向?qū)ο缶幊痰幕诶^承和虛函數(shù)的運(yùn)行時(shí)多態(tài)機(jī)制不同，C++模板是非侵入性的。你不需要讓你的類繼承自某個(gè)特定的接口才能用于某個(gè)算法，只要支持特定的語法接口就行了（比如只要支持begin()調(diào)用）。這也被稱為結(jié)構(gòu)一致性（Structural Conformance），意即只要語法結(jié)構(gòu)一致即可。而另一方面，基于接口繼承的面向?qū)ο蠖鄳B(tài)則必須要顯式地聲明繼承自一個(gè)接口，這就是所謂的名字一致性（Named Conformance）。

　　當(dāng)然，泛型支持的靜態(tài)多態(tài)和虛函數(shù)支持的動(dòng)態(tài)多態(tài)并沒有任何程度上絕對的優(yōu)劣之分。它們適用于不同的場合。當(dāng)類型信息可得的時(shí)候，利用編譯期多態(tài)能夠獲得最大的效率和靈活性。當(dāng)具體的類型信息不可得，就必須訴諸運(yùn)行期多態(tài)了。Bjarne Stroustrup曾經(jīng)用了一個(gè)典型的例子來澄清這個(gè)區(qū)別：

std::vector<Shape*> v;
// fill v
std::for_each(v.begin(), v.end(), std::mem_fun(&Shape::draw));

　　這里，v里面到底將來會(huì)存放什么類型的Shape，編譯期無法知道，因而必須求助于動(dòng)態(tài)多態(tài)。另一方面，編譯器倒的確知道它們都繼承自Shape，利用這僅有的靜態(tài)類型信息，我們使用了泛型算法std::for_each和泛型容器std::vector。這里尤其值得注意的是for_each的靜態(tài)多態(tài)行為：for_each只有一份模板實(shí)現(xiàn)，然而根據(jù)傳給它的第三個(gè)參數(shù)（本例中是std::mem_fun(&Shape::draw)）的不同，for_each的行為也不同（這里最終被for_each調(diào)用的是Shape::draw，但實(shí)際上你可以包裝任何函數(shù)，只要這個(gè)函數(shù)接受一個(gè)Shape*型的參數(shù)），for_each這種“行為不同”是發(fā)生在編譯期的，所以是靜態(tài)多態(tài)。

　　前面說過，模板與接口繼承比較，模板是非侵入的。這是C++泛型與面向?qū)ο蟮亩鄳B(tài)機(jī)制的本質(zhì)區(qū)別之一。但實(shí)際上，面向?qū)ο笪幢鼐鸵馕吨欢ㄒ媒涌趤韺?shí)現(xiàn)動(dòng)態(tài)的多態(tài)。一些動(dòng)態(tài)類型的腳本語言，如Ruby，它的多態(tài)機(jī)制就既是運(yùn)行期（動(dòng)態(tài)）的，又是非傾入性的（不用通過繼承自某個(gè)特定的接口來達(dá)到復(fù)用）。人們把這個(gè)叫做Duck Typing[7]。如果不是因?yàn)樾蕟栴}，其實(shí)這樣的多態(tài)機(jī)制才是最直觀的，從使用方面來說，它既有非侵入性，又沒有只能工作在編譯期的限制。但效率至少在可見的將來、在某些領(lǐng)域仍是一個(gè)顧慮。因此像C++這種區(qū)分編譯期和運(yùn)行期多態(tài)的語言，仍有其獨(dú)特的優(yōu)勢。

　　此外，泛型編程的類型安全優(yōu)勢也讓它從C++走入了其它主流的靜態(tài)類型語言當(dāng)中，尤其是C家族的Java和C#，在前幾年相繼接納泛型。

特化，圖靈完備性，元編程

　　C++的模板是支持特化的，這就給了它實(shí)現(xiàn)編譯期控制結(jié)構(gòu)的可能性，進(jìn)而帶來了一個(gè)圖靈完備的子語言。模板特化的引入原本只是為了效率目的——針對不同的類型提供不同的實(shí)現(xiàn)。但后來卻被發(fā)現(xiàn)能夠?qū)崿F(xiàn)編譯期的if/else和遞歸等控制結(jié)構(gòu)。

　　模板元編程最初由Erwin Unruh在1994年的一次會(huì)議上提出；當(dāng)時(shí)他寫了一個(gè)程序，在編譯錯(cuò)誤里面打印出一個(gè)素?cái)?shù)序列。這個(gè)事件在C++歷史上的地位就仿佛哥倫布發(fā)現(xiàn)新大陸。用Bjarne Stroustrup的話來說就是當(dāng)時(shí)他當(dāng)時(shí)和其他幾個(gè)人覺得太神奇了。實(shí)際上，這個(gè)事情正標(biāo)志了C++模板系統(tǒng)的圖靈完備性被發(fā)現(xiàn)；后來Todd Veldhuizen寫了一篇paper，用C++模板構(gòu)建了一個(gè)元圖靈機(jī)，從而第一次系統(tǒng)證明了C++模板的圖靈完備性。接下來的事情就順理成章了——一些ad hoc的模板元編程技巧不斷被發(fā)掘出來，用于建造高效、高適應(yīng)性的通用組件。最終，David Abrahams編寫了boost庫中的基本組件之一：Boost.MPL庫。Boost.MPL以類型和編譯期常量為數(shù)據(jù)，以模板特化為手段，實(shí)現(xiàn)了一個(gè)編譯期的STL。你可以看到常見的vector，你可以看到transform算法，只不過算法操縱的對象和容器存放的對象不再是運(yùn)行期的變量或?qū)ο螅蔷幾g期的類型和常量。想知道模板元編程是如何用在庫構(gòu)建中的，可以打開一個(gè)Boost的子庫（比如Boost.Tuple或Boost.Variant）看一看。

　　然而，畢竟C++的模板元編程是一門被發(fā)現(xiàn)而不是被發(fā)明的子語言。一方面，它在構(gòu)建泛型庫的時(shí)候極其有用。然而另一方面，由于它并非語言設(shè)計(jì)初始時(shí)考慮在內(nèi)的東西，所以不僅在語法上面顯得不那么first-class（比較笨拙）；更重要的是，由于本不是一個(gè)first-class的語言特性，所以C++編譯器并不知道C++元編程的存在。這就意味著，比如對下面這樣一個(gè)編譯期的if/else設(shè)施[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;

　　編譯器并沒有真的去進(jìn)行if/else的分支選擇，而是按部就班毫不知情地進(jìn)行著模板的特化匹配。如果遇到Boost.MPL這樣的模板元編程非常重的庫，就會(huì)嚴(yán)重拖累編譯速度，編譯器進(jìn)行了一重一重的特化匹配，實(shí)例化了一個(gè)又一個(gè)的模板實(shí)例，就是為了去獲取里面定義的一個(gè)typedef，完了之后中間所有實(shí)例化出來的模板實(shí)例類型全都被丟棄[9]。

　　模板元編程最全面深入的介紹是Boost.MPL庫的作者David Abrahams的《C++ Template Metaprogramming》，其中的樣章（第三章）[10]對模板元編程作了一個(gè)非常高屋建瓴的概覽[11]。

　　關(guān)于模板元編程，需要提醒的是，它并不屬于“大眾技術(shù)”。日常編程中極少需要用到元編程技巧。另一方面，C++模板里面有大量ad hoc的技巧，如果一頭扎進(jìn)去的話，很容易只見樹木不見森林，所以需要提醒初學(xué)者的是，即便要學(xué)習(xí)，也要時(shí)刻保持“高度”，始終記得元編程的意義和目的，這樣才不至于迷失在無窮無盡的語言細(xì)節(jié)中。

C++09——進(jìn)化

　　泛型編程在C++中取得了工業(yè)程度上的成功，得益于其高效性和通用性。但同時(shí)，在經(jīng)過了近十年的使用之后，C++模板，這個(gè)作為C++實(shí)現(xiàn)泛型的機(jī)制的缺點(diǎn)也逐漸暴露出來。比如其中對于初學(xué)者最嚴(yán)重的一個(gè)問題就是在使用一個(gè)模板庫時(shí)常常遇到無法理解的編譯錯(cuò)誤，動(dòng)輒長達(dá)上K字節(jié)。這些編譯錯(cuò)誤很容易把一個(gè)初學(xué)者嚇走。究其本質(zhì)原因，為什么編譯器會(huì)報(bào)出令人難以卒讀的編譯錯(cuò)誤，是因?yàn)樵诰幾g器的眼里，只有類型，而沒有“類型的類型”。比如說，迭代器就是一個(gè)類型的類型，C++里面也把它稱為“概念”（Concept）。例如，std::sort要求參數(shù)必須是隨機(jī)訪問迭代器，如果你一不小心給了它一個(gè)非隨機(jī)訪問的迭代器，那么編譯器不是抱怨“嘿！你給我的不是隨機(jī)訪問迭代器”，而是抱怨找不到某某重載操作符（典型的比如operator+(int)）。因?yàn)樵诰幾g器眼里，沒有“迭代器”這么個(gè)概念，這個(gè)概念只存在于程序員腦子里和STL的文檔里。為了幫助編譯器產(chǎn)出更友好的信息（當(dāng)然，還有許多非常重要的其它原因[12]），C++09將對“類型的類型”加入first-class的支持，其帶來的眾多好處會(huì)將C++中的泛型編程帶向一個(gè)新的高度：更友好、更實(shí)用、更直觀。

　　此外，C++的模板元編程尚沒有first-class的語言支持，一方面是因?yàn)槠溥\(yùn)用不像一般的模板編程這么廣泛，因而沒有這么緊急。另一方面，C++09的時(shí)間表也等不及一個(gè)成熟的提案。如果以后模板元編程被運(yùn)用得越來越廣泛的話，那first-class的語言支持是難免的。

總結(jié)

　　本文對C++模板，以及C++模板所支持的泛型編程作了一個(gè)概覽。著重介紹了泛型編程誕生的原因，泛型編程的過程和意義，與其它抽象手段的比較。并對C++中的模板元編程做了一些介紹。最后介紹了C++模板在C++09中的增強(qiáng)。