科技

C++的泛型程式設計

C++ · 發表 2019-01-18 14:57:28

摘要：程式碼膨脹 C++ 的泛型程式設計是基於模板實現的，而 C++ 的模板採用的是程式碼膨脹技術。例如 std::list 容器，如果你將 int 型別的資料存進去，C++ 編譯器就為你生成一個專門用來存 int 型別資料的列表資料結構。也就是說，你向 std::list 容器...

程式碼膨脹

C++ 的泛型程式設計是基於模板實現的，而 C++ 的模板採用的是程式碼膨脹技術。例如 std::list 容器，如果你將 int 型別的資料存進去，C++ 編譯器就為你生成一個專門用來存 int 型別資料的列表資料結構。也就是說，你向 std::list 容器中存放什麼型別，C++ 編譯器就為你生成相應的列表資料結構。理論上，資料的型別是無限的，因此 C++ 要生成的列表資料結構也是無限的。如果你的程式中有大量的資料型別要存到 std::list 容器，那麼程式碼就會高度膨脹，這種膨脹是 C++ 編譯器在目標檔案連線階段無法優化的。

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

《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;  /* gpointer 型別就是 void * 型別 */
 
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 的精華之處並不在與它提供了許多有用的資料容器，而在於容器、迭代器與演算法這三者處於一個平坦的世界，並且被優美的組合了起來。