09月24, 2007

MFC中的CMap

MFC Collection Class是MFC提供的集合类。其中CMap中有一处有意思的实现。 MFC中3个常用的类:

// CArray<TYPE, ARG_TYPE>
template<class TYPE, class ARG_TYPE> class CArray : public CObject

// CList<TYPE, ARG_TYPE> template<class TYPE, class ARG_TYPE> class CList : public CObject

// CMap<KEY, ARG_KEY, VALUE, ARG_VALUE> template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE> class CMap : public Cobject

CArray维护了一个数组 TYPE* m_pData

CList维护了一个双向链表

    struct CNode

    {

        CNode* pNext;

        CNode* pPrev;

        TYPE data;

    };

CMap维护了一个单项链表和一张哈希表

这里值得一提的有两点:

一、

在这3个类中都使用了

// global helpers (can be overridden)
ConstructElements, DestructElements, CopyElements, SerializeElements, DumpElements, CompareElements, HashKey 几个函数

以ConstructElements为例:

AFX_INLINE   void AFXAPI   ConstructElements(TYPE* pElements, int nCount) {
    // 初始化所有元素指针为0
    memset((void*)pElements, 0, nCount * sizeof(TYPE));


    //调用构造函数
    for (; nCount--; pElements++)
        ::new((void*)pElements) TYPE;
}

上面最后一句和我们平常见到的new操作符的写法不太一样,这叫做“Placement Operator New

平常的new一般是这样写

    TYPE *pData = new TYPE(…);

而这里的写法是

    TYPE *ptr = new (pointer) TYPE;

这个new是内置的new操作符的一个重载,它等价于

    TYPE *ptr = (TYPE*)pointer;
    if(ptr!=0)ptr->TYPE::TYPE();

这个new操作符将TYPE的构造函数施与pointer指向的内存之上,而不分配新的内存 (Effective C++ 中有详细介绍)

二、

CMap用单向链表和哈希表实现的Map功能。单链表中存储了实质数据,哈希表用于加快对其中元素的查找。

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>

CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const {
    nHash = HashKey<ARG_KEY>(key) % m_nHashTableSize;

    if (m_pHashTable == NULL) return NULL;

    CAssoc* pAssoc;

    for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
    {
        if (CompareElements(&pAssoc->key, &key))
            return pAssoc;
    }
    return NULL;
}

template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key){
    // default identity hash - works for most primitive values
    return ((UINT)(void*)(DWORD)key) >> 4; //关键
}
int nHashSize = 256;
CAssoc* m_pHashTable = new CAssoc* [nHashSize];
for(i=0;i<50;i++)
    printf("%d:%d
",i,i>>4% nHashSize);

输出: 输出: 0:0 1:0 2:0 3:0 4:0 5:0 6:0 7:0 8:0 9:0 10:0 11:0 12:0 13:0 14:0 15:0 16:1 17:1 18:1 19:1 20:1 21:1 22:1 23:1 24:1 25:1 26:1 27:1 28:1 29:1 30:1 31:1 32:2 33:2 34:2 35:2 36:2 37:2 38:2 39:2 40:2 41:2 42:2 43:2 44:2 45:2 46:2 47:2 48:3 49:3

可以看出key在0..15范围内被映射为到0, 16..31被映射到1,即每相邻的16个被映射为一组

这样我们可以得到如下数据结构图:

第一行是指向哈希表的指针m_pHashTable

第二行是哈希表,其中每个元素中保存了链表中的元素的指针

第三行是单向链表

这样的数据结构可以加快单链表的搜索速度,使得得到某个元素时,最坏情况也只需要进行16次比较。

本文链接:http://aztack.wang/post/cmap-in-mfc.html

-- EOF--

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。