容器們,奮起吧!—實做 STL Containers 的包裝介面

做為一個程式設計者,在 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 類別,產生出 ValueDictionaryAutoPtrDictionary 兩個長相雷同但是用途不同的容器 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 容器。只是在 ValueDictionaryAutoPtrDictionary 這兩個 Class 中,絕大部分的程式碼都是相同而且重複的,除了 RemoveAt() 與 RemoveAll() 函式的實做細節有所分別之外,其餘的部分完全都是維持相同的介面與實做,兩者有著如出一轍的程式碼。有沒有什麼方法能夠處理這種令人有點不舒服的情形呢?

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

完整程式碼下載:ContainerWrapperClass_SampleCode.zip (下載次數: 1462 )

12 Replies to “容器們,奮起吧!—實做 STL Containers 的包裝介面”

  1. 不好意思,關於第三點:
    「自動管理 Heap 物件的毀滅」

    直接使用Smart Ptr解決不是更快?還是說在實務上有甚麼考量呢?

    半路:
    這個問題問得很好哩。 ^^

    如果在能夠使用 Smart Pointer 的情境下,使用經由 Smart Pointer 包裝後的物件,的確就能夠免除掉 Heap 物件毀滅行為中大部分的問題。但是在實際的專案中,有些情況不能使用 Smart Pointer,而某些情況下則不合適使用 Smart Pointer。對於具現化數量很多或者使用非常頻繁的輕量 Class 上,使用 Smart Pointer 會造成影響效能的疑慮。而另外某些情況下,如果對舊有或現存的 Class 套用 Smart Pointer,則會造成既存程式碼與新撰寫程式碼兩者使用上的不一致與觀念上的混淆。

    本來需要 delete,現在又不用了?
    如果把 Smart Pointer 物件賦值給一般 Pointer 會發生什麼事?還需不需要刪除?
    某個函式本來是需要傳入物件 Pointer,現在傳入物件的 Smart Pointer 會不會有問題?

    Smart Pointer 是很好用的武器,但並不是百試百靈的萬靈藥。在使用 Smart Pointer 之前,還有很多問題點需要謹慎的評估與測試。

  2. 版大說的方法應該就是smart ptr吧,只是他沒提到這名詞。”更進一步,如果能夠將容器中存放的物件指標解構行為自動化,將能夠免除許多搭配容器操作 Heap 物件上的負擔與潛在問題。…”

    我也想請教一個很基本的問題:Heap在中文是怎麼翻的? :P 我記得Heap這個詞除了在記憶体方面有用到之外,在排序也有一個Heap sort,這兩個的中文應該翻成不一樣的詞嗎?

    半路:
    文中提到的那段不是指 Smart Pointer 喔,那段文字是為了帶出後面「自動管理 Heap 物件毀滅」的實做部分。 XD

    Heap 中文翻做「堆積」,而 Stack 是「堆疊」,很容易搞混的中文名詞。 Orz
    Heap 在記憶體中是指一大堆沒有使用過的記憶體集合群組,在我的理解中,和 Heap Sort 的 Heap 意義上並不相同;Heap Sort 的 Heap 結構應該是指 Binary Heap 的結構型態。我也不確定怎麼翻譯成中文會比較合適,所以在文中就直接拿 Heap 來用啦,省去越解釋可能越模糊的麻煩。 XD

  3. 唔,看來是我表達得不太好,我的意思是直接讓container吃SmartPtr,這樣就不用在container實作free了
    ,而如果其SmartPtr所指向的是非傳統new/delete的資源(像win32的handle那一類)甚至是非heap物件,利用
    多型去修改SmartPtr的行為這樣。

    半路:
    可以讓 Container 存放 Heap 物件的 Smart Pointer 沒錯。
    但是一般來說,Smart Pointer 不應該拿來套用在非 Heap 物件的 Pointer 上喔,這樣的用法沒有太大的實用性,而且還有可能造成誤用的危險。

  4. 你的 Dictionary::SetAt 如果在 m_kMap 的 insert 失敗時會 leak 掉外面傳進來的 pointer, 解決辦法可以參考拙著.

    半路:
    謝謝你的分享,仔細閱讀了一下內容,目前還無法完全理解。 Orz
    看起來是非常 robust 的例外處理程序,不過遊戲專案可能無法承受這樣的 overhead。如果太過於影響系統執行效能,或許真的就讓資源 leak 掉會比較好?(誤) XD

  5. Comment 完去洗澡時想到直接用 auto_ptr 比較恰當, 類似這樣:

    template< class TKey, class TValue >
    inline void AutoPtrDictionary< TKey, TValue >::SetAt(TKey _kKey, std::auto_ptr<TValue> ap)
    {
    m_kMap.insert(MapValueType(_kKey, ap.get()));
    ap.release();
    }

    半路:
    用 std::auto_ptr 包裝 TValue,的確是一個可防止資源 leak 的好方法。不過如果 m_kMap 中已存在相同的鍵值,insert() 動作仍然會掛掉吧?如果是這樣,就沒機會呼叫到 ap.release() 了。

    以遊戲系統的角度來說,我還是會傾向於讓它直接掛掉。因為本來該好好插入的資源,結果沒插好,可能會造成無法預期的結果。其實應該要在 insert() 前先檢查 m_kMap,然後傳回 true/false 表示是否插入成功,讓使用者自行處理失敗的後果,會比較合乎遊戲程式系統中的需求。

    您的部落格內容很殺!有時間會多去拜訪挖寶。感謝分享~ :D

  6. 請問為甚麼變數要宣告成 _XXX 的樣子?

    在看.h檔時也常常會看到類似的宣告

    想請教這是習慣還是有甚麼涵義嗎?

    還是也是匈牙利命名法則之一呢?

  7. @PP:
    你好,

    那是我以前寫程式碼的命名習慣,主要用意在於可區分出 function parameters 與 local variables。不過現在我已經不使用這樣的命名規則囉~

  8. 想順便請問你

    我已經有程式的底子

    也讀完過一本C++的書

    想要比較深入學習Container、STL

    請問你有推薦的書籍嗎?

    先謝謝囉!你的網誌好豐富,繼續加油~

  9. @PP:
    我會建議找一本比較深入的 C++ 經典書籍來讀,例如《C++ Primer》,其中應該會有關於 STL 的進一步解說與應用。當你使用 STL 一段時間,累積了實戰經驗以後,可以去讀一讀《Effective STL》這本書,相信這本書能夠讓你的學習收穫多更多~ ^^

  10. @BrianP:
    你好,

    謝謝你的補充。本文並非指 STL map 使用 hash table 做為基底的資料結構,我的意思是指程式設計者常用的關連式容器,有 map 以及 hash_map 這兩種。

Leave a Reply