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次比较。

Leave a Reply

Your email address will not be published. Required fields are marked *

Scroll to top