3D游戏引擎底层数据结构的封装之Dictionary

时间：2022-01-15 04:33:47

笔者介绍：姜雪伟，IT公司技术合伙人，IT高级讲师，CSDN社区专家，特邀编辑，畅销书作者，国家专利发明人;已出版书籍：《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。

本章主要给读者介绍Dictionary的封装，Dictionary在游戏开发中使用的非常多，开发者通常的做法是直接使用系统提供的Dictionary去做操作，不知道大家在使用Dictionary时，自己想没想过，它内部是如何实现的？换句话说，如果自己写应该怎样写出来，还有Dictionary都有哪些特性？在使用的过程中应该注意哪些问题？以前做端游的时候面试时，我也会经常提问一些关于Dictionary的用法，很多人对此掌握的并不是特别好。Dictionary在游戏开发中功能主要处理的是游戏数据信息。下面给读者分析一下商业引擎中是如何封装的？Dictionary它本身也是Key／Value值对。所以我们首先定义的是封装一个Key／Value类，因为它可以使用任何对象，封装也是用模版的方式，完整代码详情见下文：

template<class KEYTYPE, class VALUETYPE> class KeyValuePair
{
public:
    /// default constructor
    KeyValuePair();
    /// constructor with key and value
    KeyValuePair(const KEYTYPE& k, const VALUETYPE& v);
    /// constructor with key and undefined value
    KeyValuePair(const KEYTYPE& k);
    /// copy constructor
    KeyValuePair(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs);
    /// assignment operator
    void operator=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs);
    /// equality operator
    bool operator==(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// inequality operator
    bool operator!=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// greater operator
    bool operator>(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// greater-or-equal operator
    bool operator>=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// lesser operator
    bool operator<(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// lesser-or-equal operator
    bool operator<=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const;
    /// read/write access to value
    VALUETYPE& Value();
    /// read access to key
    const KEYTYPE& Key() const;
    /// read access to key
    const VALUETYPE& Value() const;

protected:
    KEYTYPE keyData;
    VALUETYPE valueData;
};

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
KeyValuePair<KEYTYPE, VALUETYPE>::KeyValuePair()
{
    // empty
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
KeyValuePair<KEYTYPE, VALUETYPE>::KeyValuePair(const KEYTYPE& k, const VALUETYPE& v) :
    keyData(k),
    valueData(v)
{
    // empty
}

//------------------------------------------------------------------------------
/**
    This strange constructor is useful for search-by-key if
    the key-value-pairs are stored in a Util::Array.
*/
template<class KEYTYPE, class VALUETYPE>
KeyValuePair<KEYTYPE, VALUETYPE>::KeyValuePair(const KEYTYPE& k) :
    keyData(k)
{
    // empty
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
KeyValuePair<KEYTYPE, VALUETYPE>::KeyValuePair(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) :
    keyData(rhs.keyData),
    valueData(rhs.valueData)
{
    // empty
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
void
KeyValuePair<KEYTYPE, VALUETYPE>::operator=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs)
{
    this->keyData = rhs.keyData;
    this->valueData = rhs.valueData;
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator==(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData == rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator!=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData != rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator>(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData > rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator>=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData >= rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator<(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData < rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
bool
KeyValuePair<KEYTYPE, VALUETYPE>::operator<=(const KeyValuePair<KEYTYPE, VALUETYPE>& rhs) const
{
    return (this->keyData <= rhs.keyData);
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
VALUETYPE&
KeyValuePair<KEYTYPE, VALUETYPE>::Value()
{
    return this->valueData;
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
const KEYTYPE&
KeyValuePair<KEYTYPE, VALUETYPE>::Key() const
{
    return this->keyData;
}

//------------------------------------------------------------------------------
/**
*/
template<class KEYTYPE, class VALUETYPE>
const VALUETYPE&
KeyValuePair<KEYTYPE, VALUETYPE>::Value() const
{
    return this->valueData;
}

这个也是封装Dictionary所需要的类，封装一个对象首先要知道封装它用来做什么？我们自己封装就要首先知道它经常使用的方法，比如获取某个值，它的大小，清空Dictionary，向Dictionary增加元素，查找元素，是否存在某个元素等等，下面就把它的真实内容显示出来，它的内部其实按照一个有序列表执行的。封装的代码中会用到Array类，完整代码如下所示： 

template<class KEYTYPE, class VALUETYPE> class Dictionary{public:    /// default constructor    Dictionary();    /// copy constructor    Dictionary(const Dictionary<KEYTYPE, VALUETYPE>& rhs);    /// assignment operator    void operator=(const Dictionary<KEYTYPE, VALUETYPE>& rhs);    /// read/write [] operator    VALUETYPE& operator[](const KEYTYPE& key);    /// read-only [] operator    const VALUETYPE& operator[](const KEYTYPE& key) const;    /// return number of key/value pairs in the dictionary    SizeT Size() const;    /// clear the dictionary    void Clear();    /// return true if empty    bool IsEmpty() const;    /// reserve space (useful if number of elements is known beforehand)    void Reserve(SizeT numElements);    /// begin a bulk insert (array will be sorted at End)    void BeginBulkAdd();    /// add a key/value pair    void Add(const KeyValuePair<KEYTYPE, VALUETYPE>& kvp);    /// add a key and associated value    void Add(const KEYTYPE& key, const VALUETYPE& value);    /// end a bulk insert (this will sort the internal array)    void EndBulkAdd();    /// erase a key and its associated value    void Erase(const KEYTYPE& key);    /// erase a key at index    void EraseAtIndex(IndexT index);    /// find index of key/value pair (InvalidIndex if doesn't exist)    IndexT FindIndex(const KEYTYPE& key) const;    /// return true if key exists in the array    bool Contains(const KEYTYPE& key) const;    /// get a key at given index    const KEYTYPE& KeyAtIndex(IndexT index) const;    /// access to value at given index    VALUETYPE& ValueAtIndex(IndexT index);    /// get a value at given index    const VALUETYPE& ValueAtIndex(IndexT index) const;    /// get key/value pair at index    KeyValuePair<KEYTYPE, VALUETYPE>& KeyValuePairAtIndex(IndexT index) const;    /// get all keys as an Util::Array    Array<KEYTYPE> KeysAsArray() const;    /// get all keys as an Util::Array    Array<VALUETYPE> ValuesAsArray() const;    /// get all keys as (typically) an array    template<class RETURNTYPE> RETURNTYPE KeysAs() const;    /// get all keys as (typically) an array    template<class RETURNTYPE> RETURNTYPE ValuesAs() const;protected:    /// make sure the key value pair array is sorted    void SortIfDirty() const;    Array<KeyValuePair<KEYTYPE, VALUETYPE> > keyValuePairs;    bool inBulkInsert;};//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE>Dictionary<KEYTYPE, VALUETYPE>::Dictionary() :    inBulkInsert(false){    // empty}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE>Dictionary<KEYTYPE, VALUETYPE>::Dictionary(const Dictionary<KEYTYPE, VALUETYPE>& rhs) :    keyValuePairs(rhs.keyValuePairs),    inBulkInsert(false){    #if NEBULA3_BOUNDSCHECKS    n_assert(!rhs.inBulkInsert);    #endif}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::operator=(const Dictionary<KEYTYPE, VALUETYPE>& rhs){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    n_assert(!rhs.inBulkInsert);    #endif    this->keyValuePairs = rhs.keyValuePairs;}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::Clear(){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    this->keyValuePairs.Clear();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> SizeTDictionary<KEYTYPE, VALUETYPE>::Size() const{    return this->keyValuePairs.Size();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> boolDictionary<KEYTYPE, VALUETYPE>::IsEmpty() const{    return (0 == this->keyValuePairs.Size());}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::Add(const KeyValuePair<KEYTYPE, VALUETYPE>& kvp){    if (this->inBulkInsert)    {        this->keyValuePairs.Append(kvp);    }    else    {        this->keyValuePairs.InsertSorted(kvp);    }}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::Reserve(SizeT numElements){    this->keyValuePairs.Reserve(numElements);}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::BeginBulkAdd(){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    this->inBulkInsert = true;}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::EndBulkAdd(){    #if NEBULA3_BOUNDSCHECKS    n_assert(this->inBulkInsert);    #endif    this->keyValuePairs.Sort();    this->inBulkInsert = false;}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::Add(const KEYTYPE& key, const VALUETYPE& value){    //n_assert(!this->Contains(key));    KeyValuePair<KEYTYPE, VALUETYPE> kvp(key, value);    if (this->inBulkInsert)    {        this->keyValuePairs.Append(kvp);    }    else    {        this->keyValuePairs.InsertSorted(kvp);    }}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::Erase(const KEYTYPE& key){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    IndexT eraseIndex = this->keyValuePairs.BinarySearchIndex(key);    #if NEBULA3_BOUNDSCHECKS    n_assert(InvalidIndex != eraseIndex);    #endif    this->keyValuePairs.EraseIndex(eraseIndex);}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> voidDictionary<KEYTYPE, VALUETYPE>::EraseAtIndex(IndexT index){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    this->keyValuePairs.EraseIndex(index);}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> IndexTDictionary<KEYTYPE, VALUETYPE>::FindIndex(const KEYTYPE& key) const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return this->keyValuePairs.BinarySearchIndex(key);}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> boolDictionary<KEYTYPE, VALUETYPE>::Contains(const KEYTYPE& key) const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return (InvalidIndex != this->keyValuePairs.BinarySearchIndex(key));}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> const KEYTYPE&Dictionary<KEYTYPE, VALUETYPE>::KeyAtIndex(IndexT index) const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return this->keyValuePairs[index].Key();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> VALUETYPE&Dictionary<KEYTYPE, VALUETYPE>::ValueAtIndex(IndexT index){    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return this->keyValuePairs[index].Value();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> const VALUETYPE&Dictionary<KEYTYPE, VALUETYPE>::ValueAtIndex(IndexT index) const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return this->keyValuePairs[index].Value();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> KeyValuePair<KEYTYPE, VALUETYPE>&Dictionary<KEYTYPE, VALUETYPE>::KeyValuePairAtIndex(IndexT index) const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    return this->keyValuePairs[index];}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> VALUETYPE&Dictionary<KEYTYPE, VALUETYPE>::operator[](const KEYTYPE& key){    int keyValuePairIndex = this->FindIndex(key);    #if NEBULA3_BOUNDSCHECKS    n_assert(InvalidIndex != keyValuePairIndex);    #endif       return this->keyValuePairs[keyValuePairIndex].Value();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> const VALUETYPE&Dictionary<KEYTYPE, VALUETYPE>::operator[](const KEYTYPE& key) const{    int keyValuePairIndex = this->FindIndex(key);    #if NEBULA3_BOUNDSCHECKS    n_assert(InvalidIndex != keyValuePairIndex);    #endif    return this->keyValuePairs[keyValuePairIndex].Value();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE>template<class RETURNTYPE>RETURNTYPEDictionary<KEYTYPE, VALUETYPE>::ValuesAs() const{    #if NEBULA3_BOUNDSCHECKS    n_assert(!this->inBulkInsert);    #endif    RETURNTYPE result(this->Size(),this->Size());    IndexT i;    for (i = 0; i < this->keyValuePairs.Size(); i++)    {        result.Append(this->keyValuePairs[i].Value());    }    return result;}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE>Array<VALUETYPE>Dictionary<KEYTYPE, VALUETYPE>::ValuesAsArray() const{    return this->ValuesAs<Array<VALUETYPE> >();}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE> template<class RETURNTYPE>RETURNTYPEDictionary<KEYTYPE, VALUETYPE>::KeysAs() const{    #if NEBULA3_BOUNDSCHECKS        n_assert(!this->inBulkInsert);    #endif    RETURNTYPE result(this->Size(),this->Size());    IndexT i;    for (i = 0; i < this->keyValuePairs.Size(); i++)    {        result.Append(this->keyValuePairs[i].Key());    }    return result;}//------------------------------------------------------------------------------/***/template<class KEYTYPE, class VALUETYPE>Array<KEYTYPE>Dictionary<KEYTYPE, VALUETYPE>::KeysAsArray() const{    return this->KeysAs<Array<KEYTYPE> >();}

虽然代码看着很多，但是读者仔细琢磨一下，并不难的，这些代码如果读者看不懂的话，很难能看懂像虚幻4那样的引擎代码，模版在引擎开发中使用的非常广泛，不论是客户端还是服务器端，读者要做的首先要能看懂别人的代码，而且这种写法现在使用的非常多。


标签：

相关文章