容器們,奮起吧!—以常整數映射型別改進 STL Containers 的介面類別

承續前篇「容器們,奮起吧!—實做 STL Containers 的包裝介面」的內容,本文將進一步改善容器 Wrapper Class 的實做設計。文中將利用《C++ 設計新思維》(Modern C++ Design) 書中,第二章第四節的常整數映射型別 (Mapping Integral Constants to Types) 技術,將原來程式碼重複性極高的 ValueDictionary 與 AutoPtrDictionary 類別合而為一。

所謂的常整數,就是一個整數型別 (Integer) 的編譯期常數值 (Constant)。而利用以下這個簡單的 template 結構就能夠將常整數映射成不同的型別 (Type):

template< int V >
struct Int2Type
{
    enum { value = V };
};

這個長相奇怪的 Int2Type template 結構,是如何將常整數映射成為不同的型別呢?根據書中的論述:

Int2Type 會根據引數所得的不同數值來產生不同型別。這是因為「不同的 template 具現體」本身便是「不同的型別」。

請仔細地思考這句話:「不同的 template 具現體」本身就是代表「不同的型別」。瞭解這句話的意涵,也是欲將 template 程式設計技術融會貫通的必經途徑!因此,由 Int2Type 這個 template 結構所具現化出來的 Int2Type< 0 >、Int2Type< 1 >、Int2Type< 2 > 等等實體物件,全部都能夠視為不同的資料型別來進行處理。那麼在什麼樣的情況下,會需要使用到這個奇怪的 Int2Type 具現體型別?

一般而言,符合下列兩個條件便可使用 Int2Type:

  • 有必要根據某個編譯期常數呼叫一個或數個不同的函式。
  • 有必要在編譯期實施「分派」(dispatch)。

「根據某個編譯期常數呼叫一個或數個不同的函式」,似乎和前篇文章中的所遇到的實做問題有點關連性?回顧先前 RemoveAll() 函式中的問題點:

template < class TKey, class TValue >
inline void Dictionary< TKey, TValue >::RemoveAll()
{
    // 如果是內存 Heap 物件
    if (m_bUseHeapObject) {
        // 巡訪整個map
        for (m_kIter = m_kMap.begin(); m_kIter != m_kMap.end(); m_kIter ++) {
            // 使用 C++ 的 operator delete
            delete m_kIter->second;
        }
    }

    // 不是 Heap 物件,只需要直接清除map
    m_kMap.clear();
}

// 無法通過編譯!
Dictionary< int, float > kItWillNotCompileDict;

如果試著將這段程式碼敲入你最愛的程式編輯器中,然後輕鬆愉快地按下「建置」,期待著美好圓滿的成果,編譯器會立刻冷冷地打回這天真爛漫的作法。上述的程式碼,在傳入非 Heap 型別物件時無法成功編譯

即使做為上述程式碼使用者的我們,知道當使用的物件型別不是 Heap 物件時,在 if 敘述句中的程式碼不應該也不會被執行。但是對於編譯器來說,並無法評估出條件式的哪一條分支不會被執行。所以,編譯器依舊會勤勞地編譯程式碼中的每個分支,因而造成編譯錯誤的產生。如果,編譯器能夠判斷哪個分支需要執行才進行編譯,而不去編譯不需要的部分,就能夠順利達到我們所需要的目標了。而這樣的情況有可能成功實現嗎?

請在心無旁騖、真心誠意的狀態下,默唸以下咒語七遍:

如果在 class template 中有一個成員函式未曾被使用到,它不會被編譯器具體實現出來。編譯器不理會它,甚至也許不會為它進行語法檢驗。

腦袋裡有沒有突然被閃電擊中的快感?如果沒有,請先去除心中雜念,再回頭念咒語三遍。

於是在有了 Int2Type 這項能夠用來「將數值轉換為型別」的武器之後,就得以應付這個本來非常棘手的介面設計問題了。我們能夠以 Int2Type 具現化出來的型別,使編譯器能夠判斷哪個函式會被編譯生成程式碼,然後再依據不同的型別,呼叫不同的實做函式。為了能夠在同一個類別內,做到「自動毀滅 Heap 物件」與「一般非 Heap 型別」兩者的處理,在建構 Templated 化的 Dictionary 物件時,需要多傳入一個 true 或 false 的 Boolean 數值用來做為 Wrapper Class 內部的判斷依據:

// 建構一個處理「一般非 Heap 型別」的 Dictionary 物件
Dictionary< int, float, false >* pkDict = new Dictionary< int, float, false >();
// 建構一個處理「Heap 型別物件」的 Dictionary 物件
Dictionary< int, TestObjectType*, true >* pkAutoPtrDict = new Dictionary< int, TestObjectType*, true >();

同樣地,在 Dictionary 類別宣告中需要新增一個 Boolean 型別的 template parameter 成為:

template < class TKey, class TValue, bool UseAutoPtr >
class Dictionary
{
    // ...
};

將介面更改完畢之後,就能夠開始處理原先無法實做的刪除程序細節了。以 RemoveAt() 函式為例:

template < class TKey, class TValue, bool UseAutoPtr >
class Dictionary
{
public:
    inline void RemoveAt(TKey _kKey);
    
private:
    inline void RemoveAt(TKey _kKey, Int2Type< true >);
    inline void RemoveAt(TKey _kKey, Int2Type< false >);
};

除了原有的 RemoveAt() 公開成員函式之外,在類別裡再新增了兩個同名稱的私有成員函式,其一處理自動毀滅 Heap 物件的刪除程序,其二則是處理一般非 Heap 型別的刪除:

template < class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAt(TKey _kKey, Int2Type< true >)
{
    m_kIter = m_kMap.find(_kKey);

    if (m_kIter != m_kMap.end()) {
        SAFE_DELETE(m_kIter->second);
        m_kMap.erase(_kKey);
    }
}

template < class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAt(TKey _kKey, Int2Type< false >)
{
    m_kMap.erase(_kKey);
}

然後在原有公開介面的 RemoveAt() 函式中,依建構 Dictionary 物件時所傳入的 true 或 false 值,以及 Int2Type 結構的巧妙利用,以決定要呼叫哪個版本的私有成員函式:

template< class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAt(TKey _kKey)
{
    RemoveAt(_kKey, Int2Type< UseAutoPtr >());
}

還記得之前建構 Dictionary 物件時額外傳入的 Boolean 值嗎?就是利用這個傳入的 true 或 false 值做為 Int2Type 的建構參數型別,從而建構出 Int2Type< true >Int2Type< false > 兩種不同的「型別」。也正是因為兩者代表著不同的型別,所以才能成為重載化 (Overloaded) 的成員函式

  • 如果建構時傳入 true,編譯器會產生對應於 RemoveAt(TKey _kKey, Int2Type< true >) 的實做程式碼。
  • 如果建構時傳入 false,編譯器會產生對應於 RemoveAt(TKey _kKey, Int2Type< false>) 的實做程式碼。

以上只會有其中一個狀況為真,而不論是哪個狀況成真,另一個不成立而沒有被使用到的 RemoveAt() 私有成員函式,就不會被編譯器所理會,也就因此得以逃過一劫!

依照上述的方式,在 RemoveAll() 函式的部分,也是以相同的方式處理:

template < class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAll()
{
    RemoveAll(Int2Type< UseAutoPtr >());
}

template < class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAll(Int2Type< true >)
{
    for (m_kIter = m_kMap.begin(); m_kIter != m_kMap.end(); m_kIter ++) {
        SAFE_DELETE(m_kIter->second);
    }

    m_kMap.clear();
}

template < class TKey, class TValue, bool UseAutoPtr >
inline void Dictionary< TKey, TValue, UseAutoPtr >::RemoveAll(Int2Type< false >)
{
    m_kMap.clear();
}

按照上述的步驟進行,就能將原來重複性極高的 ValueDictionary 類別與 AutoPtrDictionary 類別,合併成為唯一一個的 Dictionary 類別了。

善加利用 Template,以及 Template Metaprogramming 的強大威力,將能夠使程式架構的設計與實做層面更加完善。本篇文章裡,只使用了 Template 程式設計其中非常微小的一部份技術而已,在往後的文章裡,將會陸續探討其他 Template 技術的實做與應用。

然而,使用上述這種 Template 實做方法並非全無缺點。要在專案中實際運用的困難點在於:業界中太少人會使用這種技術!所以在你迫不及待想要對主管與同事推銷宣揚這項技術之前,請先準備好你的工具書、參考書以及相關的應用實例。要能夠在多數團隊成員都能瞭解並熟習 Template Programming 的情況下,才能夠真正獲得使用這些 Template 技術的益處。目前來說,仍然有一段不算短的路需要努力。

以編譯器的能力來說,一開始對於 Template Metaprogramming 的各種設計實做程式碼,往往處於支援不完善而無法通過編譯的窘境;而如今,也已經逐漸改進並且更新至比較穩定的狀態了。雖然 IntelliSense 常常不夠聰明得以辨認出 Template 的相關語意,雖然編譯器與除錯器總會在出錯時吐出一大堆奇怪的訊息,但是做為一個程式設計者,我們絕對不能忽略這個新型(其實也不新了)且強大的技術利器。等到 C++0x(新一代的 C++ 語言標準,將加入更多新的語言特性與技術應用)將這些技術正式納入語言標準後,學習並且熟習 Template 相關技術,就不僅止是小孩子對於新奇玩具的把玩心態而已,而將會成為每個 C++ 程式設計者必備的基礎知識以及程式工具

在這兩篇文章裡,提到了將 STL Container 包裝成 Wrapper Class 的一種實做方法,能夠為程式設計者免除些許未來可能遭遇的不幸厄運。而其實世界上的聰明腦袋們,還有更多更聰明的設計與實做方法。以 OGRE 為例,在這個繪圖引擎的物件架構中,使用了 Iterator Pattern 的方法,封裝整個引擎系統對於容器物件的巡訪行為,也是一個非常值得借鏡參考的包裝手法。詳細的作法,可以參照 Ogre::MapIterator< T >Ogre::VectorIterator< T > 的文件說明。

完整程式碼下載:ContainerInt2TypeImp_SampleCode.zip (下載次數: 1191 )

2 thoughts on “容器們,奮起吧!—以常整數映射型別改進 STL Containers 的介面類別”

  1. 遊戲對 containers 的要求和一般應用程式確有很大的分別。我之前工作的團隊也花了很多心力做自訂的 containers,例如intrusive list,用binary search 的 set 和 map (dictionary)等,後來還想做 lock-free containters。這絕尌是影響效能的重要部分。

    之前看到了一篇關於 Electronic Arts 的 STL 文章,我還未詳細去看。不知道半路有沒有看過,可能可以參考。

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

    半路:
    這篇文章很有意思啊。
    我現在才知道原來 EA 有自己搞出一套公開規格的 STL,真是太令人驚訝了!稍微瀏覽了一下文章中的幾個重點,真的是很值得細讀的內容,我一定要找時間好好地仔細研讀看看。

    目前我還沒辦法很清楚瞭解 Non-Intrusive 與 Intrusive Containers 的分別與優劣勝敗之處,而 Lock-Free Containers 就更沒有接觸過了。
    看來要學的東西還真的是很多很多呀~ Orz

    大大地感謝您的資訊分享與回應! :D

  2. 最近找了些資料來讀,其中 Boost.Intrusive 的資訊相當詳細而且豐富,我也終於能夠完整搞懂 intrusive container 的必要性與優點。

    關於 Intrusive 與 Non-Intrusive Container 的比較,可以參考 Intrusive and Non-Intrusive Container 以及 When to Use 這兩篇的內容。而實際的效能測試結果,則可以參考其中的 Performance 小節。

    另外,在 Intrusive Data Structures 這篇文章裡,也很詳細地介紹了各種基本概念與實作方法。

    看起來 Boost.Intrusive 的實作版本相當不錯啊~
    不只有提供 base hook 和 member hook 兩種 intrusive 的形式,還有許多常用的資料結構與演算法。之後應該會找個主題,實驗看看實際應用的效果與效能如何。

Leave a Reply