猴子靈藥 [Monkey Potion]

做為一個程式設計者，在 C++ 的程式設計領域中，我們無可避免的會經常使用到各種 STL 的容器 (Container)，包括 vector、map、set、list 等等。熟習這些容器的功能特徵與操作行為並且和它們成為好朋友，是每個 C++ 程式設計者必備的基礎知識。在大多數的情況下，我們都能心滿意足地使用著這些前人的心血結晶，不會產生任何的問題。

然而，如果某天，在現存運行的程式專案中，需要將 STL Container 替換成其他實做方案時怎麼辦？本文中將以 STL Container 中，最常用來儲存與索引資料用的 std::map 容器為例，探討容器包裝介面的必要性、實做目標以及各項實做細節，並且提供完整的程式碼範例下載。

在遊戲的程式設計中，map（或 hash_table）可以說是最常使用的資料結構之一，通常會用來存放需要進行快速檢索的資料；例如在 MMO 遊戲中以 Unique ID 做為鍵值，索引至存放玩家資料的物件指標。而對於 map 容器的操作行為，一般來說至少會用到創建、插入、刪除、尋找與巡訪結構的動作，如範例所示：

// 創建map變數
std::map< int, std::string > kMap;
std::map< int, std::string >::iterator kIter;

// 插入value
kMap.insert(std::make_pair(11, "a test"));
kMap.insert(std::make_pair(12, "the second test"));

// 巡訪map
for (kIter = kMap.begin(); kIter != kMap.end(); ++ kIter) {
    // 對每個元素進行所需的動作
}

// 取得map中的value
std::string kValue;
int iKey = 11;

kIter = kMap.find(iKey);
if (kIter != kMap.end()) {
    kValue = kIter->second;
}

以上看起來是充滿祥和之氣，完全無害的程式碼。但是日子並不會就這麼順心如意地過下去。有什麼理由與可能性，會需要更換已經是 C++ 標準函式庫又超級好用的 STL Container？

• STL Container 是屬於泛用型的設計，實做上存在著某些效能上的妥協，以換取絕大的彈性與泛用能力。如果是對於系統效能要求極高的專案，應該考慮自製 Domain-Specific 的容器以提升系統的整體表現。
• 繪圖引擎或遊戲引擎中，有一組引擎開發者自己實做的 Container，同時使用兩種 Container 可能會面臨資料轉換的問題，既不便於操作使用也不能保持一致性，所以必須更換成引擎實做的 Container 版本。
• 專案的程式 Crash 在一堆莫名其妙看不懂的 STL 程式碼當中，於是有人疾呼：「STL 這該死的 Bug！」而這個人又非常恰巧地剛好是你的老闆。所以，你需要負責將 STL Container 整個換掉。

於是，苦命悲情的程式設計者，需要開始發揮超乎常人的堅持、毅力與勇氣，嘗過無數編譯器的冷面駁回以及除錯器的慘烈哀嚎之後，才能把原先散落在程式庫各處的 STL Container 改寫成新的語法與操作方式。

（讓我們為這些勇者默禱三分鐘）

為了避免上述的慘案發生在自己身上，如果能在一開始撰寫程式時，就使用經過包裝的 STL Container，保持 Container 介面的一致性，就能夠使未來的改寫與重構任務不再是個令人頭大想撞牆的麻煩事。STL Container 經過了介面類別的包裝之後，容器就可以改頭換面、重新做人，不論以後內部的實做細節如何變動，都不會影響其他外部系統的使用。

實做包裝容器用的 Wrapper Class，有三項首要的目標：

• 一致化的介面
• 簡單易用的操作方法
• 自動管理 Heap 物件的毀滅

前兩項很容易理解，本來就是為了預防慘案發生所需達到的目標，但第三項目標是什麼緣由？

在遊戲專案中以 STL Container 管理各種遊戲物件的時候，常常會需要在存有容器的物件解構時，將容器內部所存放的物件指標也一併解構。但是，程式設計者經常是健忘或者懶惰的，常常只記得要初始化 Container，然後開心地使用便利的操作行為，卻很容易忘記在清除 Container 內容時將其中的物件指標一一抓取出來解構，於是就造成了程式的 Memory Leak。上述這種情境，經常是許多新手常犯的無心之過。最好的方法就是保持自己撰寫程式碼的紀律，在寫出建構與初始化的程式碼區塊之後，立即撰寫相對應的解構程式碼，才能夠避免發生這樣的糟糕問題。

更進一步，如果能夠將容器中存放的物件指標解構行為自動化，將能夠免除許多搭配容器操作 Heap 物件上的負擔與潛在問題。以玩家角色的 Class 為例，如果其中內含著一個 map 容器，用來存放玩家身上的各種裝備物件：

class CPlayer
{
private:
    std::map< int, CEquipment* > m_kEquipment;

public:
    CPlayer()
    {
        m_kEquipment.insert(std::make_pair(1, new CEquipment("Head")));
        m_kEquipment.insert(std::make_pair(2, new CEquipment("Chest")));
        m_kEquipment.insert(std::make_pair(3, new CEquipment("Hand")));
    }

    ~CPlayer()
    {
        // 記憶體漏掉了！
        m_kEquipment.clear();
    }
};

在以上的程式碼範例中，糟糕的記憶體漏洞問題就這樣輕易地發生了。而 Memory Leak 往往並不是很容易能察覺的一種臭蟲，常需要藉助外部的 Profiling 工具才能找出在龐大程式碼中有所疏漏的部分。更糟的是，在沒有早期發現、早期治療的情況下，在專案開發的越後期，程式庫越加複雜龐大， Memory Leak 的問題就更加不容易發現了。

其實，做為一個程式設計者，我們的心裡只有幾個小小的微薄心願：

• 程式不要有 Memory Leak，只管創建物件不管毀滅物件！
• 程式不要有 Memory Overwrite，記憶體怎麼用都沒問題！
• 程式不要有 Runtime Error，例外狀況通通抓起來做標本！

（我想，可能中大樂透的機會或許還大得許多。 XD）

所以如果能在 Container 毀滅時，就自動幫我們把其中存放的所有物件解構掉，就真的是方便多了。再也不用不好意思地搔搔頭說：「拍寫～不小心忘記了。」因此，實做 Container 的目標之一，就是希望能夠自動管理存放在容器中的物件。讓我們開始吧！

首先利用 Preprocessor Macro 定義的方式，將資料型態定義在獨立的 Header File 中：

// @file DataType.h

#include < vector >
#include < map >
#include < list >
#include < deque >

#define GaocVectorContainer std::vector
#define GaocMapContainer std::map
#define GaocListContainer std::list
#define GaocDequeContainer std::deque

將 STL Container 的型別以 Preprocessor Macro 重新定義，有利於容器基本型別的變動與修改。然後就可以在 Templated 化的 Wrapper Class 中把 map 的型別以及其他相關的型別定義，以 typedef 的方法抽取出來，轉變成簡短易於使用的資料型別。在此我採用 C#/.NET 中的容器名稱，將 Wrapper Class 命名為 Dictionary：

// @file Dictionary.h

template < class TKey, class TValue >
class Dictionary
{
private:

    typedef GaocMapContainer< TKey, TValue >   MapType;
    typedef typename GaocMapContainer< TKey, TValue >::iterator   MapIter;
    typedef typename GaocMapContainer< TKey, TValue >::value_type   MapValueType;

    MapType    m_kMap;
    MapIter    m_kIter;
};

有了基本的容器型別與其他相關型別定義後，就可以開始定義 Wrapper Class 的介面。在容器的 Public Methods 中，應該要包含基本的操作行為包括插入、取得、巡訪與刪除函式。這些 Method 大致上會長得像這樣：

// @file Dictionary.h

template < class TKey, class TValue >
class Dictionary
{
public:
    // 插入元素
    void SetAt(TKey _kKey, TValue _kValue);
    // 取得元素
    bool GetAt(TKey _kKey, TValue& _rkValue);
    // 巡訪容器
    bool GetFirst(TValue& _rkValue);
    bool GetNext(TValue& _rkValue);
    // 刪除元素
    void RemoveAt(TKey _kKey);
    void RemoveAll();
};

注意在所有取值的 Method 中，並不直接以 return 傳回所要求的元素。主要有兩個原因，其一是檢查 Boolean 回傳值判斷取值是否成功比較直觀易懂；其次則是如果在容器中找不到要求的元素時，並不容易指定要傳回什麼樣的預設值或是空值，所以使用 Pass By Reference 取得所要求的元素，得以避免空值設定的問題。

接下來看看實做部分的程式碼，插入與取得容器內存元素的操作很簡單：

// @file Dictionary.inl

template< class TKey, class TValue >
inline void Dictionary< TKey, TValue >::SetAt(TKey _kKey, TValue _kValue)
{
    m_kMap.insert(MapValueType(_kKey, _kValue));
}

template< class TKey, class TValue >
inline bool Dictionary< TKey, TValue >::GetAt(TKey _kKey, TValue& _rkValue)
{
    m_kIter = m_kMap.find(_kKey);
    if (m_kIter == m_kMap.end()) {
        return FALSE;
    }

    _rkValue = m_kIter->second;
    return TRUE;
}

接著，藉由 Wrapper Class 內存的 Iterator Object 狀態與操作，能夠讓容器的使用者巡訪 map 中的所有元素：

template< class TKey, class TValue >
inline bool Dictionary< TKey, TValue >::GetFirst(TValue& _rkValue)
{
    if (m_kMap.empty()) {
        return FALSE;
    }

    m_kIter = m_kMap.begin();
    _rkValue = m_kIter->second;
    ++ m_kIter;
    return TRUE;
}

template< class TKey, class TValue >
inline bool Dictionary< TKey, TValue >::GetNext(TValue& _rkValue)
{
    if (m_kIter == m_kMap.end()) {
        return FALSE;
    }

    _rkValue = m_kIter->second;
    ++ m_kIter;
    return TRUE;
}

有了插入、取值與巡訪的操作方法之後，最後要處理的就是最為關鍵的刪除行為。以 RemoveAll() 函式為例，如果 map 內存的是一般數值或非 Heap 物件，就可以直接呼叫 map::clear() 函式刪除 map 內存的資料。然而，如果內存的元素是屬於 Heap 物件，就需要使用 C++ 的 operator delete 將 map 中的物件一一巡訪並且解構：

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 容器，內存 Heap 物件，沒問題。
Dictionary< int, CPlayer* > m_kPlayerPool;

// 宣告一個 Dictionary 容器，內存一般型別數值。嗶嗶！編譯錯誤！
Dictionary< int, float > m_kValuePool;

這是因為 delete operator 不能作用在非 Heap 物件的型別上！不論宣告 Dictionary 時，使用的是 Heap 物件或非 Heap 物件，在 RemoveAll() 函式中的每行程式碼，同樣都會經過編譯器的查驗，所以在 TValue 型別不是 Pointer 的情況下就會產生編譯錯誤。

因此，為了應付這個問題，在此需要將存放一般非 Heap 物件型別與存放 Heap 物件型別分開成不同的 Class 實做。於是重新命名原來的 Dictionary 類別，產生出 ValueDictionary 與 AutoPtrDictionary 兩個長相雷同但是用途不同的容器 Wrapper Class。多了新的 Class 定義之後，就能夠順利的處理 RemoveAt() 與 RemoveAll() 函式了：

//@file ValueDictionary.h
template < class TKey, class TValue >
inline void ValueDictionary< TKey, TValue >::RemoveAll()
{
    m_kMap.clear();
}

//@file AutoPtrDictionary.h
template < class TKey, class TValue >
inline void AutoPtrDictionary< TKey, TValue >::RemoveAll()
{
    for (m_kIter = m_kMap.begin(); m_kIter != m_kMap.end(); m_kIter ++) {
        delete m_kIter->second;
    }
    m_kMap.clear();
}

最後在這兩個 Wrapper Class 的解構式中呼叫 RemoveAll()，就能夠達成自動清除 map 內容物並且解構 Heap 物件的目標：

//@file ValueDictionary.h
template< class TKey, class TValue >
ValueDictionary< TKey, TValue >::~AutoPtrDictionary()
{
    RemoveAll();
}

//@file AutoPtrDictionary.h
template< class TKey, class TValue >
AutoPtrDictionary< TKey, TValue >::~AutoPtrDictionary()
{
    RemoveAll();
}

以下是利用這兩個新建的 Class 的使用範例：

// 創建 Container 物件
ValueDictionary< int, float >* pkValueDict = new ValueDictionary< int, float >();
AutoPtrDictionary< int, TestObjectType* >* pkPointerDict = new AutoPtrDictionary< int, TestObjectType* >(true);

// 存放數值資料
pkValueDict->SetAt(1, 1.0f);
pkValueDict->SetAt(2, 2.0f);
pkValueDict->SetAt(3, 3.0f);

// 存放 Heap 物件資料
pkPointerDict->SetAt(123, new TestObjectType());

// 取得對應的 Heap 物件
TestObjectType* pkObject1 = NULL;
if (pkPointerDict->GetAt(123, pkObject1))
{
    std::cout << "TestObjectType object is existing." << std::endl;
}

// 巡訪 Container 物件
float fValue1 = 0.0f;
bool bResult = pkValueDict->GetFirst(fValue1);
while (bResult)
{
    std::cout << fValue1 << std::endl;
    bResult = pkValueDict->GetNext(fValue1);
}

// 毀滅 Container 物件
delete pkPointerDict;
delete pkValueDict;

至此，完成了兩個不同的 Class 用以包裝並且取代原有的 std::map 容器。只是在 ValueDictionary 與 AutoPtrDictionary 這兩個 Class 中，絕大部分的程式碼都是相同而且重複的，除了 RemoveAt() 與 RemoveAll() 函式的實做細節有所分別之外，其餘的部分完全都是維持相同的介面與實做，兩者有著如出一轍的程式碼。有沒有什麼方法能夠處理這種令人有點不舒服的情形呢？

在《Refactoring》書中提到：「重複的程式碼是一切罪惡的淵藪。」所以，為了減輕一點點身為程式設計者的罪惡感，降低因為胸中鬱悶怒火而造成的地球暖化情形，並且能夠達到 Wrapper Class 的有效使用，在次篇文章中，將針對這個議題提出比較進階深入的改善方法。

完整程式碼下載：ContainerWrapperClass_SampleCode.zip (下載次數： 73 )