C++的泛型程式設計

代碼膨脹

C++ 的泛型程式設計是基于模闆實作的，而 C++ 的模闆采用的是代碼膨脹技術。例如 std::list 容器，如果你将 int 類型的資料存進去，C++ 編譯器就為你生成一個專門用來存 int 類型資料的清單資料結構。也就是說，你向 std::list 容器中存放什麼類型，C++ 編譯器就為你生成相應的清單資料結構。理論上，資料的類型是無限的，是以 C++ 要生成的清單資料結構也是無限的。如果你的程式中有大量的資料類型要存到 std::list 容器，那麼代碼就會高度膨脹，這種膨脹是 C++ 編譯器在目标檔案連接配接階段無法優化的。

現實中，可能你沒經曆過模闆引起的代碼膨脹問題，是以對此不以為然。我也沒經曆過，因為我屬于幾乎不寫 C++ 代碼并且幾乎不關注 C++ 世界都發生了什麼的那種人。沒見過，不等于沒有。我看到的一本講 C++ 模闆程式設計的書（擔心有人再認為我将一本國産書視為聖經，書名我就不提了）裡提到應用 boost::spirit 時很容易出現代碼極度膨脹的情況，類似的事在 [1] 中也提到了。

如果有興趣一起交流學習c/c++的小夥伴可以加群：941636044，裡面有大神會給予解答，也會有許多的資源可以供大家學習分享，歡迎大家前來一起學習進步！

《Effective C++》的作者可能見過代碼膨脹的例子，是以他在條款 44 中建議『将與參數無關的代碼抽離 templates』。這個條款也許是 C++ 應對模闆導緻的代碼膨脹問題的唯一解決方案了，然而這個方案往往并不是那麼容易實作。你需要仔細審度你的代碼，認真的從模闆類（或模闆函數）中将那些不涉及模闆參數的代碼抽離出來做成基類（或輔助函數）。即使你能很好的做到這一點，但是請認真想一想，這樣做真的有意義麼？

模闆技術原本是為了簡化程式設計任務而被提出來的，但是要消除模闆帶來的代碼膨脹，你不得不對本來邏輯很清晰的代碼進行肢解再重新整合，這個過程或多或少的會破壞甚至扭曲原有的代碼邏輯，結果弄出來一個渾身插着電源線的怪獸般的模闆類或模闆函數。

C++ 模闆代碼所導緻的膨脹，主要帶來以下問題：

1.源代碼膨脹了，因為程式猿要做『将與參數無關的代碼從模闆中抽離』這件事。有人做過試驗，即使是一個不太大的 List 實作，将代碼從模闆中抽離後，導緻源代碼膨脹了 20%……其實開發效率也自然降低了很多。

2.編譯時間被拖長了，因為編譯器在代碼編譯階段要對模闆代碼進行『惰性計算』，要産生模闆的執行個體代碼，在目标檔案連接配接階段還要消除各個目标檔案中重複的模闆代碼。

3.目标檔案膨脹了。有人說他用 boost::spirit 實作了一個很小的文法解析器，開了 GCC 的最大化優化選項，目标檔案也要幾十 MB，而一個 Lua 或 Python 解釋器還不到 1 MB，Haskell 的解釋器 ghc 剛 1 MB 多一點……

4.模闆代碼中如果存在錯誤，編譯器産生的錯誤資訊也膨脹了，特别是模闆類的嵌套嵌套再嵌套，或者模闆執行個體非常多的時候，編譯出錯資訊無法卒讀，甚至有人說編譯出錯資訊甚至超出了他用的文本編輯器的緩存空間大小。
           

類型擦除

兩天前，我不知道類型擦除是個什麼東西，隻是看了 Vala 語言 所實作的泛型之後才知道這個概念。因為 Vala 語言是編譯到 C 的，是以很容易看到它的泛型是如何實作的。

下面是 Vala 模闆類的示例：

public class Wrapper : GLib.Object {

private G data;

public void set_data(G data) {

this.data = data;

}

public G get_data() {

return this.data;

}

}

void main() {

var wrapper_str = new Wrapper();

wrapper_str.set_data(“test”);

var s = wrapper_str.get_data();

var wrapper_int = new Wrapper();

wrapper_int.set_data(100);

var n = wrapper_int.get_data();

}

泛型之處在于：

private G data;

wrapper_str.set_data(“test”);

var s = wrapper_str.get_data();

wrapper_int.set_data(100);

var n = wrapper_int.get_data();

上述代碼片段，會被 Vala 編譯器編譯為下面的 C 代碼：

gpointer data;

wrapper_set_data (wrapper_str, “test”);

tmp1 = wrapper_get_data (wrapper_str);

s = (gchar*) tmp1;

wrapper_set_data (wrapper_int, (gpointer) ((gintptr) 100));

tmp3 = wrapper_get_data (wrapper_int);

n = (gint) ((gintptr) tmp3);

如果不打算看懂這些代碼也沒關系。簡單的說，Vala 的模闆或泛型就是基于 void * 指針的強制類型轉換。 C 語言要模拟泛型程式設計，最自然的方式就是程式猿手動對 void * 進行類型轉換，GLib 庫中的所有資料容器都是這麼做出來的。由于 Vala 編譯器會對模闆參數進行類型檢查，是以基本上不需要擔心 void * 的強制類型轉換會導緻類型不安全的問題。後來，看了幾篇 Java 泛型的文檔，才知道原來 Vala 的這個做法叫『類型擦除』。

類型擦除的最大特點是沒有什麼東西會膨脹，因為一個模闆的全部執行個體會共享同一份代碼。

誰是真泛型？

很多人說 Java 的泛型是僞泛型，那麼 Vala 的泛型自然也是僞泛型了。也許我的世界觀有問題，我總覺得類型擦除才是真的泛型，因為它能真實的模拟現實中的『泛型』。

現實中，我們所謂的泛型，例如一個登山包，你可以用它來裝任何它能裝得下的東西。你去驢行時，登山包裡可以裝水杯、書籍、手機/平闆、充電器、帳篷、睡袋、救生用品等等；如果你不是去旅遊，而是去逛超市，依然可以用這個登山包将所買的東西帶回家。你肯定不會背着一大堆包去旅遊或者去逛超市，其中裝水杯包的叫水杯包，裝手機的包叫手機包，裝平闆的包叫平闆包，裝面包的包叫面包……而且這些包都跟登山包差不多大——在 C++ 中，你所生成的程度必須背着這樣的一大堆包去驢行或逛超市。

從 C++ 11 開始，有右值引用了，模闆變得比以前更好用了。在 C++ 14 中，連匿名函數也支援泛型了……我覺得 C++ 模闆所帶來的代碼膨脹遲早會走進尋常百姓家的。

事實上，Boost 庫中的一些容器已經引入了類型擦除技術[2]，例如 boost::any, boost::variant, boost::function 等等。雖然它們采用類型擦除技術的本意并非針對模闆代碼膨脹問題，隻是一種模拟，而且依然存在着模闆代碼膨脹的問題。很久以前還看過一篇論文，名字忘記了，講的是如何在 C++ 中利用類型擦除技術來調和面向對象程式設計與泛型程式設計之間的沖突的。在 C++ 社群，類型擦除技術絕對是很進階的技術，之是以如此窮折騰，真的不是因為 C++ 編譯器不支援類型擦除的緣故嗎？

C++ 中的類型擦除技術是基于模闆模拟出來的，其基本原理就是将類模闆轉化為函數模闆[3]。C++ 編譯器能夠自動推導出函數模闆參數的執行個體，進而讓程式猿在寫代碼的時候無需設定模闆參數，再借助運作時類型識别（RTTI）或函數模闆取出被擦除了類型的資料。從本質上來說，這種類型擦除技術依然無法避免模闆的膨脹，但是這個模拟過程已經将大部分與模闆參數無關的代碼抽離了出來。

有趣的是，《C++ Primer》第四版的中文譯本在第 16 章『模闆與泛型程式設計』中的導言部分很不嚴肅的将泛型程式設計定義為『以獨立于任何特定類型的方式編寫代碼』。難道真的泛型不應該是以獨立于任何特定類型的方式去編寫獨立于特定類型的代碼麼？如果 C++ 模闆真的适合做編寫獨立于特定類型的代碼這樣的事，那麼就不需要去将與參數無關的代碼從模闆中抽離出來了，也不需要有運算符重載、Traits 類、模闆特化與偏特化等補救機制了（一直都感覺 C++ 太擅長解決那些它自身制造出來的問題了）。《C++ Primer》第 5 版的『模闆與泛型程式設計』章的導言部分已将這個不嚴肅的泛型程式設計定義去掉了。

泛型的敵人

Vala 語言除了 GNOME 開發者之外沒有多少人用，是以它是真泛型還是僞泛型，對這個世界幾乎沒有影響。

Java 的泛型引起的問題已經廣為人知 [4-6]，而且也是以獲得『僞泛型』的僞大稱号。但是，我覺得他們所說的 Java 泛型所引起的那些問題是面向對象程式設計範式引起的。因為他們所指出的那些問題，往往是在面向對象程式設計範式中使用泛型程式設計範式的場景中出現的。如果類型擦除真的不行，那麼 Java 是如何實作了它的『STL』的？連 Vala 這種微不足道的小語言也實作了一些『STL』容器。

面向對象程式設計範式與泛型程式設計範式是沖突的，熟悉 C++ STL 的人應該知道這個事實。

STL 之父 Alexander Stepanov 是反面向對象程式設計範式的。他在 1995 年的一次訪談[7]中說：『STL 不是面向對象的。我認為面向對象和人工智能差不多，都是個騙局……我發現面向對象程式設計在技術上是錯誤的，它妄圖用基于單一類型的不同接口來分解世界，為了處理不同的實際問題你需要不同種類的代數學——橫跨不同類型的接口族；我發現面向對象程式設計在哲學上是錯誤的，它聲稱一切都是一個對象。即使真的是這樣這也不是很有趣─說一切都是對象跟什麼都沒說一樣；我發現面向對象程式設計的方法論是錯誤的，它從類開始。就好像數學要從公理開始一樣。你不是從公理開始——你是從證明開始。直到你找到了一大堆相關證據你才能歸納出公理。你是以公理結束。程式設計上存在着同樣的事實：你要從有趣的算法開始。隻有很好地了解了算法，你才有可能提出接口以讓其工作。』

雖然 Alexander Stepanov 說的挺精彩，然而 STL 庫裡依然有一些類的繼承，例如五種疊代器之間的關系；應該将 Alexander Stepanov 的話了解為他反對的是程式設計工作從類的設計開始。如果将很沖突的兩種世界觀體混在在代碼中，出現了沖突，這難道不是很正常麼？為何要将這種沖突歸罪于類型擦除？C++ 模闆之是以被大家視為真泛型，無非是因為 C++ 模闆本來也是從面向對象程式設計範式中誕生的。用模闆膨脹出一堆重複的代碼，這種方式與面向對象程式設計範式中的類的派生如出一轍，這也恰恰就是 STL 之父所反對的『數學要從公理開始』。

泛型的世界是平坦的，沒有繼承，沒有多态，例如你不能在自己的代碼中去繼承 STL 容器。我覺得 STL 的精華之處并不在與它提供了許多有用的資料容器，而在于容器、疊代器與算法這三者處于一個平坦的世界，并且被優美的組合了起來。

最後，如果有興趣一起交流學習c/c++的小夥伴可以加群：941636044，裡面有大神會給予解答，也會有許多的資源可以供大家學習分享，歡迎大家前來一起學習進步！