[C++] type function

前陣子看到一個有趣的資料結構叫 pairing heap，單純看複雜度來說比 fibonacci heap 高
不過 pairing heap 的操作很簡單，所以複雜度的 constant 不大
是個頗吸引我的資料結構，所以這陣子有想要自己實做，然後試著做成像 STL 那樣的架構
一研究下去發現，STL 果真是集工程師智慧之大成，一大堆看不懂的技巧在裡面Orz

這篇是記錄之前看不懂得其中一樣設計：type function
這幾天翻書翻到才搞懂這設計的意義為何


 當時為了大概了解 STL 的 class 會怎樣設計，所以到 [2] 這邊去翻了一下那些 container 的介面是怎麼做的，其中看到一個我當時看了老半天都搞不懂的一行：

void push_back (const value_type& val);

而那個 value_type 是這個東西：

value_type: The first template parameter (T)

當時我怎樣都搞不懂為什麼要在 class 內部多弄 member type 出來? 直到我遇到這個情況：

template <typename T>
class Coor
{
private:
    T x, y;
public:
    T getX();
    T getY();
};

假設 Coor 定義了二維平面的座標點，而一個線段由 2 個端點構成：

template <typename T> 
class Segment 
{ 
private:
    Coor<T> begin, end; 
public:
    T getLength(); 
}; 

so far so good，但是考慮下面這個情況：
我希望在線段的兩個端點附加上一些資訊，於是我希望可以擴充 Coor 的功能，如此一來，強制指定 Segment 內的 type 非得是 Coor<T> 顯然會出事，因此稍做修改，讓兩個端點的型別變成 template parameter：

template <typename COOR>
class Segment
{
private:
    COOR begin, end;
public:
    ??? getLength();
};

好啦，問題來了，這邊 ??? 要填什麼呢? 顯然的我們沒有足夠的資訊去判斷
只知道 COOR 內的 x 跟 y 是什麼型別， ??? 就至少要是那個型別，或是儲存範圍更大的型別。舉例來說，COOR 內的 x 跟 y 如果型別是 int，那麼 ??? 就至少要是 int，當然也可以是 long 或 double。

為了處理這問題，一個最簡單的方法就是在 Segment 的 template parameter 再多加一個來標示出這項資訊：

template <typename T, typename COOR> 
class Segment 
{
private:
    COOR begin, end;
public:
    T getLength();
}; 

如此一來問題是解決了，只是使用上變得有點困擾：

Segment< int, Coor<int> > seg;

我們都已經在 Coor 那邊註明了 member data 的 type 是 int，但是還要再多寫一個 int 來讓 Segment 的介面知道這件事情。有沒有什麼好方法可以解決呢?這就是 STL 之所以會有那個 value_type 的原因...首先小修改 Coor 的介面：

template <typename T>
class Coor
{
private:
    T x, y;
public:
    // type function
    typedef T value_type;

    T getX();
    T getY();
};

先在 Coor 內部加上一個 typedef 讓 template paramter T 變成 Coor 的 member type，這樣我們就可以藉由 Coor<T>::value_type 這種方式來得知 T 的型別。因此我們可以再次修改 Segment 的介面：

template <typename COOR>
class Segment
{
private:
    COOR begin, end;
public:
    COOR::value_type getLength();
};

原本的 ??? 如今我們可以知道就是 COOR::value_type，因此也不必再多一個 template parameter 來得知這樣資訊，使用上也就更直覺囉!

Segment< Coor<int> > seg;

當然，如果今天 ??? 所要求的型別其可儲存的值的範圍必須要大於 value_type，例如 value_type 是 int 則 ??? 至少要是 long；如果 value_type 是 float 則 ??? 至少要是 double；如果 value_type 是 short int 則 ??? 至少要是 int ... etc，這種情況則可以靠 type trait + partial instantiation 來達成，不過這是另一個主題，這邊就不討論了。

關於 type function 這邊只是很粗淺的介紹，所以這邊的用法是看不出為何會叫 type "function"，type function 其價值要在與其他技巧結合時才會顯現，更詳細的用法及介紹就請自己翻書查資料囉~

然後本來預計要寫 type erasure 難產中...這東西有夠難


Reference:
[1] "C++ Templates, The Complete Guide," 侯捷、姜宏、榮耀 譯
(作者名? 那一堆字我懶得打...又不是寫論文...呵呵呵)
[2] http://www.cplusplus.com/reference/