C++ 的靜態多型:CRTP

這篇來寫個 C++ 的老東西、curiously recurring template pattern(CRTP、中文被翻譯成「奇異遞迴模板模式」、維基百科);這東西其實很早就有了,在 1980 年就有了,當時似乎是被稱為「F-bounded quantification」?

CRTP 基本上是一種 template + 繼承的變形語法、形式很特別,基本上會長的像下面的樣子:

template <class T>
class Base
{
public:
  void interface()
  {
    static_cast<T*>(this)->implementation();
  }
};
 
class Derived : public Base<Derived>
{
public:
  void implementation() {}
};

這邊的寫法很有趣,基礎的類型 Base 算是用來定義介面,是一個 template class。

Derived 這個類別則是 Base 的一個實作,會去繼承 Base,而同時,他又把本身的型別作為 Base 的 template 參數來使用;如此一來,變成兩者會有相當的相依性、名稱的「recurring」應該也是這樣來的。

而在使用時,基本上會是下面的樣子:

Derived a;
a.interface();

在呼叫 interface() 這個函式的時候,他會在 Base 這邊,把代表自己的指標 this 透過 static_cast<>() 強制轉型成 Derived、然後去呼叫 Derived::implementation()

如果以一般的繼承的方法來寫的話,大概就等同於下面的形式:

class Base
{
public:
  virtual void interface() = 0;
};

class Derived : public Base
{
public:
  void interface() override {}
};

在這邊,Derived 這個實作的類別並沒有 implementation() 這個函式,而是直接透過 override interface() 這個函式來完成實作。


CRTP 的優點

但是既然已經有繼承可以用簡單的方法可以用了,那為什麼要用 CRTP 這種奇怪的寫法呢?

因為實際上我們一般在寫類別的繼承的時候,如果有用到 virtual function 的話,就會變成是動態多型的形式,編譯器在編譯的時候,會去建立「Virtual method table」(vtable、維基百科)來產生表格來紀錄哪個類別最後要去呼叫哪個實作;而在執行時,則是會透過「virtual table pointer」(vpointer)去記錄這個物件要去使用哪個 vtable。
這部分可以參考《Understandig Virtual Tables in C++》。

而這些機制,不但會增加記憶體使用量,同時在執行的時候也會因為要去查表、而增加執行時的額外負擔。

而透過 CRTP 來實作的話,由於沒有的 virtual function,所有東西都在編譯階段決定好了,所以基本上不需要產生 vtable,在使用的時候,也可以因此避免虛擬函式額外造成的負擔。


比較完整的例子

再來,來寫個稍微完整點的例子。

比如說要做繪圖的東西,這邊先定義了一個 Shape 的基礎型別:

template <class T>
class Shape
{
public:
  size_t points_count() const
  {
    return static_cast<const T*>(this)->points_count_impl();
  }
 
  void draw() const
  {
    // pre-draw call
    std::cout << "do something before draw" << std::endl;
 
    // draw
    const T* pImpl = static_cast<const T*>(this);
    std::cout << "draw " << pImpl->points_count_impl() << "points\n";
    pImpl->draw_impl();
 
    // post-draw call
    std::cout << "do something after draw" << std::endl;
  }
};

這邊提供了兩個介面,一個是 points_count() 可以取得點的數量;另一個則是 draw(),用來繪製,不過這邊就只有輸出一些文字了。

接下來,就可以按照 Shape 的定義,透過 CRTP 來實作不同的形狀:

class Square : public Shape<Square>
{
  friend  Shape<Square>;
 
protected:
  size_t points_count_impl() const
  {
    return 4;
  }
 
  void draw_impl() const
  {
    std::cout << " > draw a square" << std::endl;
  }
};
 
class Triangle : public Shape<Triangle>
{
  friend  Shape<Triangle>;
 
protected:
  size_t points_count_impl() const
  {
    return 3;
  }
 
  void draw_impl() const
  {
    std::cout << " > draw a triangle" << std::endl;
  }
};

這邊定義了 SquareTriangle,兩者都根據 Shape 的需求,提供了 points_count_impl()draw_impl() 的實作。

這邊為了不要讓使用者直接使用各自的實作,所以使用 protected 來做保護;而這樣的話,就需要加上 friend Shape<> 來讓 Shape 可以存取了。

這樣當要繪製一個三角形的時候,就可以寫成下面的形式了:

Triangle v;
v.draw();

這樣的寫法,就可以讓所有的形狀,都可以透過 Shape 定義的介面來做操作,而沒有 vtable 的效能損失了。同時,共同的程式也可以寫在 Shape 裡面,來盡量增加程式碼共用。

而如果要針對所有的形狀撰寫函式的話,則就需要寫成 template 的形式:

template<class TImpl>
void draw_with_color(const Shape<TImpl>& rRhape)
{
  std::cout << "set pen color\n";
  // ...
  rRhape.draw();
}

這樣 draw_with_color() 這個函式就可以處理所有繼承自 Shape 的形狀了。


安全防護

CRTP 在撰寫實作的時候,基本上就是下面的形式:

class Derived : public Base<Derived>

重點就是自身的型別會是基礎型別的 template 參數。

但是在撰寫的時候,很有可能難免會手殘寫錯、或是複製貼上忘了改;例如以上面 Shape 的例子來說,當要寫圓形的實作的時候,如果複製貼上沒弄好,很可能就變成:

class Circle : public Shape<Triangle>

然後如果都沒注意到的話,之後真的跑就爆炸了。 XD

而想要在編譯階段防止這種手殘的錯誤的話,則可以在 Shape 裡面,將建構子改成 private 的、並加上 friend T、變成只有 T 這個型別可以存取。

template <class T>
class Shape
{
private:
  Shape() = default;
  friend T;
//  ...
}

如此一來,在撰寫實作的時候型別名稱和給 Shape 的 template 參數型別不一致的時候,就會因為無法存取建構子、而無法完成編譯了。


CRTP 的缺點

當然,CRTP 也不是沒有缺點的。

相較於直接使用 virtual function 的方法,CRTP 的繼承最大的問題,就是上面例子中的 SquareTriangle 雖然看起來都是繼承 Shape 寫出來的,但是由於實際上繼承的分別是 Shape<Square>Shape<Triangle>,在系統內還是會被視為不同的型別。

也因此,他們實質上並沒有共同的基底型別,所以會無法用單一型別來儲存;也就是沒辦法寫成下面的形式:

Triangle t;
Square s;
std::vector<Shape> vObjs;
vObjs.push_back(t);
vObjs.push_back(s);

所以實際上如果是採用 CRTP 定義的物件,實際上是沒辦法集中管理的…這點在很多時候會讓開發上麻煩而多。

也因此,這東西也不是所有狀況都適合拿來用的。

再來,由於要定義 CRTP 的函式的時候,都需要使用 template 的形式,所以其實也是很有可能會增加編譯的時間、還有編譯出來的檔案大小的。


參考:

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *