Effective C++:七、Templates and Generic Programming－BOOK

七、Templates and Generic Programming
C++ template 的最初發展動機是：
建立「type-safe」的容器，如 vector, list 和 map。
後來發現 C++ template 有能力完成愈多可能的變化，容器當然很好，但 generic programming 寫出的程式碼和其所處理的物件型別彼此獨立 - 則更好。
最終發現 C++ template 機制本身是一部完整的 Turning-complete：
它可以被用來計算任何可計算的值，於是導出了 template metaprogramming，創造出「在 C++ 編譯期內執行並於編譯完成時停止執行」的程式。
儘管 template 的應用如此廣泛，有一組核心觀念一直支撐著所有以 template 為基礎的 programming，這些觀念就是本章的重點。

41、Understand implicit interfaces and compile-time polymorphism.
Object oriented programming 總是以 explicit interface 及 runtime polymorphism 解決問題：

class Widget {
  public:
    Widget();
    virtual ~Widget();
    virtual std::size_t size() const;
    virtual void normalize();
    void swap(Widget& other);
    ...
};

void doProcessing(Widget& w) {
    if (w.size() > 10 && w != someNastyWidget) {
        Widget temp(w);
        temp.normalize();
        temp.swap(w);
    }
}

在 doProcessing 的 w：

由於 w 的型別被宣告為 Widget，所以 w 必須支援 Widget 介面，而這個介面，可以在源碼中找到，所以稱為 explicit interface。
由於 Widget 的某些 member function 是 virtual，w 對那些 function 的呼叫將表現出 runtime polymorphism，也就是說將在執行期根據 w 的 dynamic type 來決定究竟要喚起哪個 function。

template 及 generic programming 的世界與 Object-oriented 有根本上的不同，在此世界，explicit interface 及 runtime polymorphism 仍然存在，例重要性降低，反倒是 implicit interface 及 compile-time polymorphism 較具有重要性：

template 
void doProcessing(T& w) {
    if (w.size() > 10 && w != someNastyWidget) {
        T temp(w);
        temp.normalize();
        temp.swap(w);
    }
}

在 doProcessing 的 w：

w 必須支援哪種介面，是由 template 中執行於 w 身上的操作來決定，從上例看，w 的型別好像必須支援 size(), normalize() 和 swap member function, copy constructor(用以建立 temp), inequality comparison。
凡涉及 w 的任何 function 的呼叫，例如 operator> 和 operator!=，都有可能造成 template 具現化(instantiated)，使這些呼叫得以成功，這樣的具現行為發生在編譯期，「以不同的 template 參數具現化 function templates」會導致喚起不同的函式，也就是所謂的 compile-time polymorphism。

通常 explicit interface 由 function 的 signature (也就是 function name, 參數型別、回返型別) 構成：

class Widget {
  public:
    Widget();
    virtual ~Widget();
    virtual std::size_t size() const;
    virtual void normalize();
    void swap(Widget& other);
    ...
};

其 public interface 是由一個 constructor、一個 destructor、function size()、normalize()、swap() 及其參數型別、回返型別、constness 構成，當然也包括 compiler 產生的 copy constructor 及 copy assignment operator。

implicit interface 就完全不同了，它不奠基於 function signature，而是由有效算式(valid expression)組成：

template 
void doProcessing(T& w) {
    if (w.size() > 10 && w != someNastyWidget) {
        ...
    }
}

T(w 的型別) 的 implicit interface 看來好像有這些約束：

必須提供一個名為 size 的 member function，並傳回一個整數值。
必須支援一個 operator!= function，用來比較兩個 T 物件。

不過由於有 operator overloading 帶來的可能性，所以這兩個約束都不需要滿足。
雖然 T 必須支援 size function，但這個 function 可以從 base class 繼承，而且並不需要回傳一個整數值，甚至不需要回傳一個數值型別，它甚至不需要回傳一個定義有 operator> 的型別。
它唯一需要做的是傳回一個型別為 X 的物件，而 X 物件加上一個 int(10 的型別) 必須能夠喚起一個 operator>。
這個 operator> 不需要非得取得一個型別為 X 的參數，也可以取得型別 Y 參數，只有存在一個隱式轉換能夠將型別 X 的物件轉換為型別 Y 的物件。

同理，T 也不需要支援 operator!=，只要 operator!= 接受一個型別為 X 的物件和一個型別為 Y 的物件，T 可被轉換為 X，而 someNastyWidget 的型別可被轉換為 Y，這樣就可以有效喚起 operator!=。

以上分析並未考慮這樣的可能性：operator&& 被重載，從一個連接詞改變或許完全不同的某種東西，從而改變上述算式的意義。

加諸於 template 參數身上的 implicit interface，就像加諸於 class 物件身上的 explicit interface 一樣真實，而且兩者都在編譯期完全檢查，就像無法以一種「與 class 提供之 explicit interface 矛盾」的方式來使用物件，也無法在 template 中使用「不支援 template 所要求之 implicit interface」的物件，兩者都會造成無法通過 compile。

classes 和 templates 都支援 interfaces 和 polymorphism。
對 class 而言，interfaces 為 explicit，以 function signatures 為中心， polymorphism 則是透過 virtual functions 發生於 run-time。
對 template 而言，interfaces 為 implicit，奠基於 valid expressions， polymorphism 則是透過 template instantiation 和 function overloading resolution 發生於 compilation。

42、Understand the two meanings of typename.
以下 template 宣告式中，class 和 typename 有何不同：

template&ltclass T&gt class Widget;// 使用 "class"
template&lttypename T&gt class Widget;// 使用 "type name"

答案是：沒有不同，在宣告 template 型別參數時，從 C++ 的角度來看，不論使用關鍵字 class 或 typename，意義完全相同。

然而 C++ 並不總是把 class 和 typename 視為等價，有時候一定得使用 typename，為了解其時機，先談談在 template 內所指涉的兩種名稱：

template&lttypename C&gt
void print2nd(const C& container) {  // 列印容器內的第二個元素
    if (container.size() >= 2) {  // 注意，這不是有效的程式碼
        C::const_iterator iter(container.begin());
        ++iter;
        int value = *iter;
        std::out

程式碼中，iter 的型別是 C::const_iterator，實際是什麼必須取決於 template 參數 C；在 template 內出現的名稱如果相依於某個 template 參數，稱之為從屬名稱(dependent name)；如果從屬名稱在 class 內呈巢狀，稱為巢狀從屬名稱(nested dependent name)。
C::const_iterator 就是這樣一個名稱，事實上它還是個巢狀從屬型別名稱(nested dependent type name)，也就是個巢狀從屬名稱並且指涉某型別。

print2nd() 內的另一個 local 變數 value，型別為 int，並不依賴任何 template 參數內的名稱，這樣的名稱稱為非從屬名稱(non-independent name)。

nested dependent name 有可能導致 parsing 困難，修改 print2nd()：

void print2nd(const C& container) {
    C::const_iterator* x;
    ...
}

看起來像是宣告 x 為一個 local variable，它是個指標，指向一個 C::const_iterator，但，之所以會這麼認為，是因為已經認定 C::const_iterator 是個型別。
如果 C::const_iterator 不是個型別呢？如果 C 有個 static 成員變數碰巧命名為 const_iterator，或如果 x 碰巧是個 global variable ？這樣的話，上述的程式碼就會變成一個相乘動作：C::const_iterator 乘以 x 。

在知道 C 是什麼之前，沒有辦法可以知道 C::const_iterator 是否為一個型別，而當 compiler 開始解析 template print2nd 時，尚未確知 C 是什麼東西，在 C++ 中有個規則可以決議此一歧義狀態：
如果解析器在 template 中遭遇一個 nested dependent name，將預設這個名稱不是個型別，除非明確告訴它是，方法是在緊臨這個名稱之前放置關鍵字 typename 即可：

template&lttypename C&gt
void print2nd(const C& container) {  // 列印容器內的第二個元素
    if (container.size() >= 2) {
        typename C::const_iterator iter(container.begin());
        ++iter;
        int value = *iter;
        std::out

typename 只被用來驗明 nested dependent type name，其它名稱不該有它的存在：

template&lttypename C&gt  // 允許使用 "typename" 或 "class"
void f(const C& container,  // 不允許使用 "typename"
         typename C::iterator iter);  // 一定要使用 "typename"

「typename 必須做為 nested dependent type name 的前導詞」這一規則的例外是，typename 不可以出現在 base class list 內的 nested dependent type name 之前，也不可以在 member initialization list 中做為 base class 飾詞：

template&lttypename T&gt
class Derived : public Base::Nested {  // 不允許 "typename"
  public:
    explicit Derived(int x)
        : Base::Nested(x) {  // 不允許 "typename"
        typename Base::Nested temp;  // 需要加上 "typename"
        ...
    }
    ...
};

最後一個 typename 的例子，這也是可以會在真實程式中所看到的代表性例子，假設正在撰寫一個 function template，它接受一個 iterator，在 function 中，打算為該 iterator 指涉的物件做一份 local 複件 temp：

template&lttypename IterT&gt
void workWithIterator(IterT iter) {
    typename std::iterator_traits::value_type temp(*iter);
    ...
}

typename std::iterator_traits::value_type 只不過是標準 trait class 的一種運用，詳見條款 47，相當於說「型別為 IterT 之物件所指之物的型別」，這個述句宣告一個 local variable - temp，使用 IterT 物件所指物的相同型別，並將 temp 初始化為 iter 所指物。
也就是說如果 IterT 是 vector&ltint&gt::iterator，temp 的型別就是 int，如果 IterT 是 vector&ltstring&gt::iterator，temp 的型別就是 string。

加上 typedef 的應用是：

template&lttypename IterT&gt
void workWithIterator(IterT iter) {
    typedef typename std::iterator_traits::value_type value_type;
    value_type temp(*iter);
    ...
}

宣告 template 參數時，前綴關鍵字可以是 class 也可以是 typename。
nested dependent type names 必須使用關鍵字 typename 來標識，除非是在 base class lists 或 member initialization list 內。

43、Know how to access names in templatized base classes.
以下程式，能夠傳送訊息到不同的公司，訊息要嘛是明碼，要嘛是加密過的，如果在編譯期間，有足夠資訊來決定哪一個訊息傳至哪一家公司，就可以採用奠基於 template 之上的解法：

class CompanyA {
  public:
    ...
    void sendCleartext(const std::string& msg);
    void sendEncrypted(const std::string& msg);
    ...
};

class CompanyB {
  public:
    ...
    void sendCleartext(const std::string& msg);
    void sendEncrypted(const std::string& msg);
    ...
};

class MsgInfo { ... };  // 用來保存資訊，以產生訊息

template
class MsgSender {
  public:
    ...
    void sendClear(const MsgInfo& info) {
        std::string msg;
        ...  // 根據 info，產生 msg
        Company c;
        c.sendCleartext(msg);
    }
    void sendSecret(const MsgInfo& info) {
        std::string msg;
        Company c;
        c.sendEncrypted(msg);
    }
};

template
class LoggingMsgSender : public MsgSender {
  public:
    ...
    void sendClearMsg(const MsgInfo& info) {
        ...  // 紀錄傳送前的 log
        sendClear(info);
        // 呼叫 base class function，尚無法通過 compile
        ...  // 紀錄傳送後的 log
    }
    ...
};

上述程式碼無法通過編譯的原因在於，當 compiler 遭遇 class template LoggingMsgSender 定義式時，並不知道是繼承什麼樣的 class，當然它繼承的是 MsgSender，但其中的 Company 是個 template 參數，不到 LoggingMsgSender 被具現化後，無法確切得知 Company 是什麼，更簡單的說，就是沒辦法知道 Company 是否有個 sendClear function。

為了讓問題更具體化，假設有個 class CompanyZ 堅持使用加密通訊：


class CompanyZ {  // 不提供 sendCleartext function
  public:
    ...
    void sendEncrypted(const std::string& msg);
    ...
};

一般性的 MsgSender template 對 companyZ 並不適合，因為 CompanyZ 並不提供 sendCleartext function，所以必須針對 CompanyZ 產生一個 MsgSender specialization：

template&lt&gt  // MsgSender total template specialization
class MsgSender&ltCompanyZ&gt {
  public:
    ...
    void sendSecret(const MsgInfo& info) {
        ...
    }
};

class 定義式最前頭的 "template&lt&gt" 語法象徵這既不是 template，也不是標準 class，而是個 specialized 的 MsgSender template，在 template 引數是 CompanyZ 時被使用。
這是所謂的 total template specialization：
template MsgSender 針對型別 CompanyZ 特化了，而且其特化是全面性的，也就是說一旦型別參數被定義為 CompanyZ，再沒有其它 template 可供變化。

如此，考慮到 MsgSender 針對 CompanyZ 進行了 total template specialization，則在 derived class - LoggingMsgSender 中，將不存在 sendClear(info) 這個 function，而這也是這段程式碼無法通過 compile 的原因。

就某種意義而言，當從 Object Oriented C++ 跨進 Template C++，inheritance 就不像以前那般暢行無阻了。

有三種方式，可以將上述無法通過 compile 的程式作修正，第一是在 base class function 呼叫動作之前加上 "this->"：

template
class LoggingMsgSender : public MsgSender {
  public:
    ...
    void sendClearMsg(const MsgInfo& info) {
        ...  // 紀錄傳送前的 log
        this->sendClear(info);  // 假設 sendClear 將被繼承
        ...  // 紀錄傳送後的 log
    }
    ...
};

第二是使用 using 宣告式，詳見條款 33：

template
class LoggingMsgSender : public MsgSender {
  public:
    ...
    void sendClearMsg(const MsgInfo& info) {
        using MsgSender::sendClear;
        ...  // 紀錄傳送前的 log
        sendClear(info);  // 假設 sendClear 位於 base class 內
        ...  // 紀錄傳送後的 log
    }
    ...
};

第三種作法是明白指出被呼叫的 function 位於 base class 內：

template
class LoggingMsgSender : public MsgSender {
  public:
    ...
    void sendClearMsg(const MsgInfo& info) {
        ...  // 紀錄傳送前的 log
        MsgSender::sendClear(info);  // 假設 sendClear 將被繼承
        ...  // 紀錄傳送後的 log
    }
    ...
};

但第三種，往往是最不讓人滿意的，因為如果被呼叫的是 virtual function，上述的 explicit qualification 會關閉「virtual 綁定行為」。

從名稱 visibility point 的角度出發，上述每個解法所做的事情都相同：
對 compiler 承諾「base class template 的任何特化版本都將支援其一般版本所提供的介面」，但如果這個承諾最終未被實踐出來，往後的 compile 還是會無法通過：

LoggintMsgSender zMsgSender;
MsgInfo msgData;
...
zMsgSender.sendClearMsg(msgData);  // 無法通過 compile

因為此時 compiler 知道 base class 是個 template 特化版本 MsgSender，而且還知道這個 class 並不提供 sendClear function，但卻被 sendClearMsg() 嘗試呼叫。

可在 derived class template 內透過 "this->" 指涉 base class template 內的 member name，或利用 using declaration，又或藉由 explicit base class qualification，來達到使用 base classes 內的 member name。

44、Factor parameter-independent code out of templates.
template 是節省時間和避免程式碼重複的一個妙方，不再需要鍵入 20 個類似的 class 而每個帶有 15 個 member function，只需要鍵入一個 class template，接著留給 compiler 去具現化那 20 個需要的相關 class 及 300 個 function。
(class template 的 member function 只有在被使用時才被具現化。)
function template 也有類似的訴求，取代寫取多 function，只需要寫一個 function template，然後讓 compiler 做剩餘的事情。

不過，如果不小心，使用 template 將可能會導致程式碼膨脹(code bloat)：
其二進制碼帶著重複的程式碼、資料。
這樣的結果有可能 source code 看起來整齊，但 object code 卻不是這麼回事。

舉個例子，為固定尺寸的正方矩陣編寫一個 template，該矩陣的性質之一是支援反矩陣運算：

template&lttypename T, std::size_t n&gt
class SquareMatrix {
  public:
    ...
    void invert();  // 逆反矩陣
};

SquareMatrix sm1;
...
sm1.invert();  // 呼叫 SquareMatrix::invert

SquareMatrix sm2;
...
sm2.invert();  // 呼叫 SquareMatrix::invert

這個 template 接受一個型別參數 T，還接受一個型別為 size_t 的參數，這是個非型別參數(non-type parameter)。
而在接下來的程式碼中，會造成具現化兩份 invert，這些 function 並非完全相同，因為其中一個操作的是 5x5 矩陣，另一個是 10x10 矩陣，但除了常數 5 和 10 之外，兩個 function 的其它部分完全相同，這是 template 引出程式碼膨脹的一個典型例子。

如果看到兩個 function 完全相同，除了一個使用 5，另一個使用 10，本能地會為它們建立一個帶數值參數的 function：

template&lttypename T&gt
class SquareMatrixBase {
  protected:
    ...
    void invert(std::size_t matrixSize);  // 逆反矩陣
};

template&lttypename T, std::size_t n&gt
class SquareMatrix : private SquareMatrixBase&ltT&gt {
  private:
    using SquareMatrixBase::invert;  // 避免遮掩 base 版的 invert
  public:
    ...
    void invert(s) { this->invert(n) };
    // 避免遮掩 templatized base class 內的 function
};

帶參數的 invert() 位於 base class SquareMatrixBase 中，而 SquareMatrixBase 也是個 template，但只對「矩陣元素物件的型別」參數化。

還有個棘手的問題，SquareMatrixBase::invert() 如何知道該操作什麼資料？
雖然從參數中可以知道矩陣尺寸，但如何得知哪個特定矩陣的資料在哪？
一個可能的作法是為 SquareMatrixBase::invert() 添加參數，也許是個 pointer，指向一塊用來放置矩陣資料的記憶體起始點。
又或是令 SquareMatrixBase 貯存一個 pointer，指向矩陣數值所在的記憶體：

template&lttypename T&gt
class SquareMatrixBase {
  protected:
    SquareMatrixBase(std::size_t n, T* pMem)
            : size(n)
            , pData(pMem) {
    }
    void setDataPtr(T* ptr) { pData = ptr; }
    ...
  private:
    std::size_t size;  // 矩陣大小
    T* pData;  // pointer，指向矩陣內容
};

template&lttypename T, std::size_t n&gt
class SquareMatrix : private SquareMatrixBase&ltT&gt {
  public:
    SquareMatrix()
            : SquareMatrixBase(n, data)
            , pData(new T[n*n]) {
         this->setDataPtr(pData.get());
    }
    ... 
  private:
    boost::scoped_array pData;  // 祥見條款 13
};

Template 會生成多個 classes 和 functions，所以任何 template 程式碼都不該與某個造成膨脹的 template 參數產生相依關係。
因非型別模板參數(non-type template parameters) 而造成的程式膨脹，往往可消除，作法是以 function parameters 或 class data members 取代 template parameters。
因型別參數(type parameters) 而造成的程式膨脹，往往可降低，作法是讓帶有完全相同二進制表述 (identical binary representation) 的具現型別 (instantiation type) 共享實作碼

45、Use member function templates to accept "all compatible types."
所謂 smart pointer 是「行為像指標」的物件，如條款 13 提及 std::auto_ptr 及 tr1::shared_ptr 如何能被用來在正確時機自動刪除 heap-based 資源。

不過真實指標做得很好的一件事是，支援 implicit conversion，derived class pointer 可以隱式轉換為 base class pointer，「指向 non-const 物件」的 pointer 可以轉換為「指向 const 物件」… 等等：

class Top { ... };
class Middle : public Top { ... };
class Bottom : public Middle { ... };

Top* pt1 = new Middle;  // 將 Middle* 轉換為 Top*
Top* pt2 = new Bottom;  // 將 Bottom* 轉換為 Top*
const Top* pct2 = pt1;  // 將 Top* 轉換為 const Top*

如果要在使用者定義的 smart pointer 中模擬上述轉換，則稍稍有點麻煩：

template&lttypename T&gt
class SmartPtr {
  public:  // smart pointer 通常以
    explicit SmartPtr(T* realPtr);  // 內建原始 pointer 完成初始化
    ...
};

SmartPtr&ltTop&gt pt1 = SmartPtr&ltMiddle&gt(new Middle);
SmartPtr&ltTop&gt pt2 = SmartPtr&ltBottom&gt(new Bottom);
SmartPtr&ltconst Top&gt pct2 = pt1;

同一個 template 的不同具現體(instantiation) 之間並不存在什麼與生俱來的固有關係，所以 compiler 將視 SmartPtr&ltMiddle&gt 和 SmartPtr&ltBottom&gt 為完全不同的 class，而為了獲得 SmartPtr class 之間的轉換能力，則必須將它們明確地編寫出來。

template 和 generic programming
在上個例子中，每個述句產生了一個新式 smart pointer 物件，所以要關注的是如何編寫 smart pointer 的 constructor，使其行為能夠滿足轉型需要。
一個很關鍵的觀察結果是：可能永遠無法寫出所需要的所有 constructor，因為這個繼承體系在未來可能會有所擴充。

就原理而言，此例中所需要的 constructor 數量沒有止盡，因為一個 template 可被無限量具現化，因此，似乎此時需要的不是為 SmartPtr 寫一個 constructor function，而是為它寫一個 constructor template，這樣的 template 是所謂 member function template，簡稱為 member template，其作用是為 class 生成 function：

template&lttypename T&gt
class SmartPtr {
  public:  
    template&lttypename U&gt  // member template
    SmartPtr (const SmartPtr&ltU&gt& other);  // 為了生成 copy constructor
    ...
};

上述例子是，對任何型別 T 和任何型別 U，可以根據 SmartPtr&ltU&gt 生成一個 SmartPtr&ltT&gt。
這一類 constructor 根據物件 u 產生物件 t，而 u 和 t 的型別是同一個 template 的不同具現體，有時也被稱為 generalized copy constructor。

此例中的 copy constructor 並未被宣告為 explicit，因為在原始 pointer 型別之間的轉換是隱式轉換，無需明白寫出轉型動作(cast)。

不過上述這個為 SmartPtr 而寫的 generalized copy constructor 提供的東西比需要的還多，因為除了可以根據一個 SmartPtr&ltBottom&gt 生成一個 SmartPtr&ltTop&gt，但也造成可以根據一個 SmartPtr&ltTop&gt 生成一個 SmartPtr&ltBottom&gt，這對 public inheritance 而言是矛盾的，詳見條款 32。

假設 SmartPtr 遵循 auto_ptr 和 tr1::shared_ptr 所提供的榜樣，也提供一個 get member function，傳回 smart pointer 所持有的那個原始 pointer 的副本，則可以在「建構模板」實作碼中約束轉換行為：

template&lttypename T&gt
class SmartPtr {
  public:  
    template&lttypename U&gt
    SmartPtr (const SmartPtr&ltU&gt& other)  // 以 other 的 heldPtr
            : heldPtr(other.get()) { ... }  // 初始化 this 的 heldPtr
    T* get() const { return heldPtr; }
    ...
  private:
    T* heldPtr;  // 這個 SmartPtr 持有的內建原始 pointer
};

使用 member initialization list 來初始化 SmartPtr&ltT&gt 之內型別為 T* 的 member variable，並以型別為 U* 的 pointer 作為初值，這個行為只有當「存在某個隱式轉換可將一個 U* pointer 轉換為一個 T* pointer」時才能通過 compile，這正是此例子中所需要的。
最終效益是 SmartPtr&ltT&gt 現在有了一個泛化 copy constructor，這個 constructor 只在其所獲得的引數隸適當(相容)型別時，才會通過 compile。

member function template 的效用不限於 constructor，它們常扮演的另一個角色是支援賦值操作。

member function template 並不改變語言規則，而語言規則說，如果程式需要一個 copy constructor，如果沒有宣告它，則 compiler 會暗自生成一個，而在 class 內宣告 generalized copy constructor 並不會阻止 compiler 生成它們自己的 copy constructor，相同的規則也適用於 copy assignment operator，下面這個例子正是 tr1::shared_ptr 的定義摘要：

template&ltclass T&gt
class shared_ptr {
  public:
    shared_ptr(shared_ptr const& r);  // copy constructor
    template&ltclass Y&gt  // generalized copy constructor
    shared_ptr(shared_ptr&ltY&gt const& r);

    shared_ptr& operator=(shared_ptr const& r);  // copy assignment
    template&ltclass Y&gt  // generalized copy assignment
    shared_ptr& operator=(shared_ptr&ltY&gt const& r);
    ...
};

請使用 member function template 生成「可接受所有相同型別」的 function。
如果宣告 member template 用於「generalized copy constructor」或「generalized assignment operator」，還是得需要宣告正常的 copy constructor 及 copy assignment operator。

46、Define non-member functions inside templates when type conversions are desired.
條款 24 討論過為什麼唯有 non-member function 才有能力「在所有引數身上實施隱式型別轉換」，該條款以 Rational class 的 operator* function 為例，本討論將 Rational 和 operator* 模板化了：

template&lttypename T&gt
class Rational {
  public:
    Rational(const T& numerator = 0, const T& denominator = 1);
    const T numerator() const;
    const T denominator() const;
    ...
};

template&lttypename T&gt
const Rational&ltT&gt operator* (const Rational&ltT&gt& lhs,
                             const Rational&ltT&gt& rhs) {
    ...
}

Rational&ltint&gt oneHalf(1, 2);
Rational&ltint&gt result = oneHalf * 2;  // 錯誤，無法通過 compile

如果條款 24一樣，也希望可以支援 mixed-mode 算術運算，但從上例的 compile error 來看，模板化的 Rational 內的某些東西似乎和其 non-template 版本不同。
在條款 24內，compiler 知道嘗試呼叫的 function 是接受兩個 Rational 參數的那個 operator*，但在這個例子，compiler 不知道哪個 function 該被呼叫。
此例中，compiler 試圖想出什麼 function 被名為 operator* 的 template 具現化出來，compiler 知道它可以具現化某個「名為 operator* 並接受兩個 Ration&ltT&gt 參數」的 function，但要完成這一具現化行為，必須先算出 T 是什麼。

為了推導 T，compiler 看了 operator* 呼叫動作用的引數型別，分別是 Rational&ltint&gt 和 int。
以 operator* 的第一參數被宣告為 Rational&ltT&gt，而傳遞給 operator* 的第一引數的型別就是 Rational&ltint&gt，所以 T 一定是 int。
但 operator* 的第二參數型別是 int，而 compiler 在 template 引數推導過程中從不將隱式型別轉換納入考慮，所以不會將 int 轉換為 Rational&ltint&gt。

雖然這樣的轉換在 function call 過程中被使用，但在能夠呼叫一個 function 之前，首先必須知道那個 function 的存在，而為了知道它，必須先為相關的 function template 推導出參數型別，但 template 引數推導過程中，並不考慮採納「藉由 constructor 而發生的」隱式型別轉換。

只要利用一個事實，就可以緩和 compiler 在 template 引數推導方面到的挑戰：
template class 內的 friend 宣告式可以指涉某個特定 function。
這意味著 class Rational&ltT&gt 可以宣告 operator* 是它的一個 friend function，class template 並不倚賴 template 引數推導，所以 compiler 總是能夠在 class Rational&ltT&gt 具現化時得知 T：

template&lttypename T&gt
class Rational {
  public:
    ...
    friend const Rational operator*(const Rational& lhs,
                                    const Rational& rhs);
    // 在 class template 內，template 名稱可被用來做為
    //「template 和其參數」的簡略表達方式
};

template&lttypename T&gt
const Rational&ltT&gt operator* (const Rational&ltT&gt& lhs,
                             const Rational&ltT&gt& rhs) {
    ...
}

現在對 operator* 的 mixed mode 呼叫可以通過 compile，因為當物件 oneHalf 被宣告為一個 Rational&ltint&gt，class Rational&ltint&gt 於是被具現化出來，而作為過程的一部分，所以 friend function operator* 也就被自動產生出來，而這個 function 並非 function template，所以 compiler 可在呼叫它時使用隱式轉換，而這就是 mixed mode 呼叫之所以成功的原因。

但目前為止，雖然可以通過 compile，因為 compiler 知道要呼叫哪一個 function，卻無法 link，因為那個 function 只被宣告於 Rational 內，並沒有被定義出來。

或許最簡單的的可行辦法是將 operator* function 本體合併至其宣告式內：

template&lttypename T&gt
class Rational {
  public:
    ...
    friend const Rational operator*(const Rational& lhs,
                                    const Rational& rhs) {
        return Rational(lhs.numerator() * rhs.umerator() ,
                        lhs.denominator() * rhs.denominator());
    }
};

這個技術中，雖然使用了 friend，卻與 friend 的傳統用途「存取 class 的 non-public 成分」毫不相干。
為了讓型別轉換可能發生在所有引數身上：需要一個 non-member function；為了令這個 function 被自動具現化：需要將它宣告在 class 內部；而在 class 內宣告 non-member function 的唯一辦法就是：令它成為一個 friend 。

如同條款 30 所說，定義在 class 內的 function 都暗自成為 inline，為了將 inline 宣告所帶來的衝擊最小化，作法是令 operator* 不做任保事，只呼叫一個定義於 class 外部的輔助 function。
但在上例中，這樣做，並沒有太大意義，因為 operator* 已經是個單行 function。

「Rational 是個 template」所以上述的輔助 function 通常也是個 template：

template&lttypename T&gt class Rational;  // 宣告 Rational template
template&lttypename T&gt  // 宣告 helper template
class Rational&ltT&gt doMultiply(const Rational& lhs,
                             const Rational& rhs);

template&lttypename T&gt
class Rational {
  public:
    ...
    friend const Rational operator*(const Rational& lhs,
                                    const Rational& rhs) {
        return doMultiply(lhs, rhs);  // 令 friend 呼叫 helper
    }
};

template&lttypename T&gt
const Rational&ltT&gt doMultiply(const Rational& lhs,
                             const Rational& rhs) {
    return Rational(lhs.numerator() * rhs.umerator() ,
                    lhs.denominator() * rhs.denominator());
}

做為一個 template，doMultiply 當然不支援 mixed mode 乘法，但它其實不需要，它只被 operator* 呼叫，而 operator* 支援了 mixed mode 操作。

當在編寫一個 class template，而它所提供之「將此 template 相關的」function 支援「所有參數之隱式型別轉換」時，將那些 function 定義為「class template 內部的 friend function」。

47、Use traits classes for information about types.
STL 主要由「用以表現容器、iterator 和演算法」的 template 構成，但也函蓋若干工具性 template，其中之一是 advance，用來將 iterator 移動某個距離：

template&lttypename IterT, typename DistT&gt
void advance(IterT& iter, DistT d);
// 將 iterator 向前移動 d 單位，如果 d

觀念上 advance 只是做 iter + = d 動作，但其實不可以全然這麼實踐，因為只有 random access iterator 才支援 += 操作，其它威力不那麼強大的 iterator，advance 須反覆執行 ++ 或 --，共 d 次。

STL 的 iterator 分成 5 個 categories：

input iterator:
output iterator:
forward iterator:
bidirectional iterator:
random access iterator:

對於這 5 種分類，C++ 標準程式庫分別提供專屬的 tag struct 加以確認：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

所以在實作 advance 時，希望能以下列方式實作：

template&lttypename IterT, typename DistT&gt
void advance(IterT& iter, DistT d) {
    if (iter is a random access iterator) {
        iter += d;  // 針對 random access iterator 使用算術運算
    } else {
        if (d >= 0) { while (d--) ++iter; }  // 其它 iterator
        else { while (d++) --iter; }  // 則反覆呼叫 ++ 或 --
    }
}

這種作法首先必須判斷 iter 是否為 random access iterator，也就是需要取得型別的某些資訊，這也是 traits 存在的理由：
traits 的存在，將使得可以在 compile 期間取得某些型別資訊。

traits 並不是 C++ keyword，也不是一個預先定義好的構件，它們是一種技術，也是 C++ programmer 所共同遵守的協定。
這個技術的要求之一是，它對 build-in 型別和 user-defined 型別的表現必須一樣好。

traits 的標準技術是把型別資訊放進一個 template 及其一或多個特化版本中，這樣的 template 在標準函式庫有若干個，其中針對 iterator 被命名為 iterator_traits：

template&lttypename IterT&gt  // template，用來處理
struct iterator_traits;  // iterator 的相關資訊

iteractor_traits 是個 struct，習慣上 traits 總是被實作為 structs，但卻又往往被稱為 struct classes。

iterator_traits 的運作方式是：
針對每一個型別 IterT，在 struct iterator_traits&ltIterT&gt 內一定宣告某個 typedef 名為 iterator_category，這個 typedef 用來確認 IterT 的 iterator category。

iterator_traits 以兩個部分實現上述所言，首先它要求每一個「user-defined iterator type」必須嵌套一個 typedef，名為 iterator-category，用來確認適當的 tag struct：

template &lt ... &gt  // 略而未寫 template 參數
class deque {
  public:
    class iterator {
        typedef random_access_iterator_tag iterator_category;
    };
    ...
};

template &lt ... &gt
class list {
  public:
    class iterator {
        typedef bidirectional_iterator_tag iterator_category;
    };
    ...
};

template &lttypename IterT&gt
struct iterator_traits {
    typedef typename IterT::iterator_category iterator_category;
};

但上述要求對 user-defined type 行得通，但對 pointer (也是一種 iterator) 行不通，因為 pointer 不可能存在嵌套式 typedef，所以 iterator_traits 的第二部分如下，專門用來對付 pointer。

為了支援 pointer iterator，iterator_traits 特別針對 pointer type 提供一個 partial template specialization，由於 pointer 的行徑與 random access iterator 類似，所以 iterator_traits 為 pointer 指定的 iterator type 是：

template &lttypename IterT&gt  // partial template specialization
struct iterator_traits&ltIterT*&gt {  // 針對 built-in pointer
    typedef random_access_iterator_tag iterator_category;
};

總結，要如何設計並實作一個 traits class：

確認若干希望將來可取得的型別相關資訊，以 iterator 為例，希望可以取得其 category 資訊。
為該資訊選擇一個名稱，如：iterator_category
提供一個 template 和一組 partial template specialization，如上述的 iterator_traits，內含希望支援的型別相關資訊。

有了 iterator_traits 後(實際上是 std::iterator_traits，因為它是 C++ 標準函式庫的一部分)，可以對 advance 實踐先前的 pseudocode：

template&lttypename IterT, typename DistT&gt
void advance(IterT& iter, DistT d) {
    if (typeid(typename std::iterator_traits&ltIterT&gt::iterator_category)
            == typeid(std::random_access_iterator_tag)) {
        ...
}

但這樣子的作法並非正確，首先它會導致 compile 問題，這在條款 48 才探討。
此刻要根本考慮的問題是 IterT 型別在 compile 期間獲知，所以 iterator_traits&ltIterT&gt::iterator_category 也可以 compile 期間確定，但 if 述句卻是在執行期才會核定。

有沒有一個條件式判斷「compile 期核定成功」之型別？
恰巧 C++ 有一個取得這種行為的辦法，也就是 overloading。

所需要做的，就是讓 advance 產生兩版重載 function，內含 advance 的本質內容，但接受不同類型的 iterator_category 物件：

template&lttypename IterT, typename DistT&gt
void doAdvance(IterT& iter, DistT d, std::random_access_iterator_tag) {
    iter += d;
}

template&lttypename IterT, typename DistT&gt
void doAdvance(IterT& iter, DistT d, std::bidirectional_iterator_tag) {
    if (d >= 0) { while (d--) ++iter; }
    else { while (d++) --iter; }
}

template&lttypename IterT, typename DistT&gt
void doAdvance(IterT& iter, DistT d, std::input_iterator_tag) {
    if (d //

有了這些 doAdvance overloading 版本，advance 需要做的只是呼叫它們並額外傳遞一個帶有適當 iterator type 的物件，於是 compiler 會運用 overloading resoluation 來呼叫適當的實作碼：

template&lttypename IterT, typename DistT&gt
void advance(IterT& iter, DistT d) {
    doAdvance(iter, d,
        typename std::iterator_traits&ltIterT&gt::iterator_cagetory()
    );
}

總結如何使用一個 traits class：

建立一組 overloading function(身份像勞工) 或 function template(如 doAdvance)，彼此間的差異只在於各自的 traits 參數，令每個 function 實作碼與其接受之 traits 資訊相應。
建立一個控制 function(身份像工頭)，或 function template(如 advance)，用來呼叫上述的那些「勞工 function」，並傳遞 traits class 所提供的資訊。

traits 廣泛用於標準函式庫，除了包含上述討論的 iterator_traits，還有另外四份 iterator 相關資訊，其中最有用的是 value_type，詳見條款42。

TR1 ，見條款52，導入許多新的 traits classes 用以提供型別資訊，包括 is_fundamental&ltT&gt，is_array&ltT&gt 以及 is_base_of&ltT1, T2&gt，總計 TR1 為標準 C++ 添加了 50 個以上的 traits classes。

traits classes 使得「型別相關資訊」在 compile 期可用，以 template 和 partial template specialization 完成實作。
整合 overloading 後，traits classes 有可能在 compile 期間，就對型別執行 if ... else 測試。

48、Be ware of template metaprogramming.
template metaprogramming(TMP, 模板超編程) 是編寫 template-based C++ 程式並執行於 compile 期的過程。
而所謂 template metaprogram 是以 C++ 寫成、執行於 C++ 編譯器內的程式，一旦 TMP 程式結束執行，其輸出，也就是從 template 具現出來的若干 C++ source code，便會一如往常地被編譯。

TMP 有兩個偉大的效力：

它讓某些事情更容易，如果沒有它，那些事情是困難的，甚至不可能的。
由於 template metaprograms 執行於 compile-time，因此可將工作從 run-time 轉到 compile-time，這導致兩個結果：
- 某些錯誤原本通常在 run-time 才能偵測到，現在可在 compile-time 找出來。
- 使用 TMP 的 C++ 程式可能在每一方面都更高效：較小的可執行檔、較短的執行期、較少的記憶體需求；然而將工作從 run-time 移到 compile-time 也會造成編譯時間變長。

考慮條款47 中導入的 STL advance pseudo code ，可以使用 typeid 讓其中的 pseudo code 成真，但條款47 指出，這個 typeid-based 解法的效率比 traits 解法低，因為：

型別測試發生於 run-time 而非 compile-time。
「run-time 型別測試」程式碼會被連結於可執行檔中。

條款47

曾經提過 advance 的 typeid-based 實作方式可能導致 compile-time 問題，例子如下：

std::list&ltint&gt::iterator iter;
...
advance(iter, 10);  // 無法通過 compile

將 template 參數 IterT 和 DistT 分別替換為 iter 和 10 的型別之後，可以得到：

void advance(std::list&ltint&gt::iterator& iter, int d) {
    if (typeid(std::iterator_traits<:list>::iterator_category
            == typeid(std::random_access_iterator_tag)) {
        iter += d;  // 錯誤
    } else {
        if (d >= 0) { while (d--) ++iter; }
        else { while (d++) --iter; }
    }
}

問題就出在那行使用了 += 運算子的程式碼，那便是嘗試在一個 list&ltint&gt::iterator身上使用 +=，因為 compiler 必須確保所有的 source code 都有效，縱使是不會執行起來的 source code。

TMP 已被證明是個「turing-complete machine」，意思是它的威力大到足以計算任何事物。
使用 TMP 可以宣告變數、執行迴圈、編寫及呼叫 function…，但這般構件相對於「正常的」C++ 對應物看起來很是不同，如條款 47 展示的 TMP if ... else 條件句是藉由 templates 和其特化體表現出來。

TMP 並沒有真正的迴圈構件，所以迴圈效果係藉由 recursion 完成，而 TMP 的 recursion 甚至不是正常種類，因為 TMP 迴圈並不涉及 recursiive function 呼叫，而是涉及「recursive template instantiation」。

TMP 的起手程式是在 compile-time 計算 factorial，而 factorial 運算將示範如何透過「recursive template instantiation」實現迴圈，以及如何在 TMP 中產生和使用變數：

template&ltunsigned n&gt
struct Factorial {
    enum { value = n * Factorial::value };
};

template&lt&gt
struct Factorial {
    enum { value = 1 };
};

int main() {
    std::cout ::value // 120
    std::cout ::value // 3628800
    return 0;
}

迴圈發生在 template instantiate Factorial&ltn&gt 內部指涉另一個 template instantiate Factorial&ltn-1&gt 之時，和所有良好 recursion 一樣，需要一個特殊情況來造成 recursion 結束：
template specialization Factorial&lt0&gt。

每個 factorial template instantiation 都是一個 struct，每個 struct 都使用 enum hact (見條款2) 宣告一個名為 value 的 TMP 變數，value 用來保存當前計算所得的階乘值，如果 TMP 擁有真正的 recursion 構件， value 應該在每次 recursion 內獲得更新，但由於 TMP 係以「recursive template instantiation」取代迴圈，所以每個 instantiation 都有自己的一份 value，而每個 value 都有其迴圈內的適當值。

為求領悟 TMP 之所以值得學習，很重要的一點是先對它能夠達成什麼目標有一個比較好的理解，以下舉出三個例子：

確保量度單位正確：
優化矩陣運算：
可以生成客戶訂製之設計範式(custom design pattern) 實作品：

template metaprogramming(TMP, 模板超編程) 可將工作由 run-time 移往 compile-time，因而得以實現早期錯誤偵測和更高的執行效率。
TMP 可被用來生成「植基於政策選擇組合」(based on combinations of policy choices) 的客戶訂製碼，也可用來避免生成對某些特殊型別並不適合的碼。

silverfoxkkk

BOOK

silverfoxkkk 發表在痞客邦留言(0) 人氣()

E-mail轉寄

BOOK

BOOK

Effective C++:七、Templates and Generic Programming

留言列表