CMap 操作指南

• 下载源文件 - 5.9 KB

引言

像我这样，在学习CMap之前就学习了STL::map的程序员，总是觉得CMap很难用，并且总是试图像使用STL::map一样使用CMap。在这篇文章中，我将解释CMap以及如何使用它来处理你自定义的类。文章最后，我将展示一个如何正确使用CMap并配合CString*（注意，我指的是CString指针而不是CString :>）的例子。

CMap 内部结构

首先需要注意的是，CMap实际上是一个哈希表（hash map），而不是像STL::map那样的树形图（tree map）（通常是红黑树）。下面是CMap的内部结构图。

如何声明 CMap

很多人对CMap的声明CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>感到困惑，为什么不直接是CMap<KEY, VALUE>呢？

事实上，CMap的最终数据容器是CPair，而CPair的内部是{KEY, VALUE}。因此，CMap实际上存储的是KEY，而不是ARG_KEY。但是，如果你查看MFC的源代码，你会发现几乎所有CMap内部的参数传递都是使用ARG_KEY和ARG_VALUE。因此，将KEY&用作ARG_KEY似乎总是正确的，除非在以下情况：

1. 你使用的是基本数据类型，如int、char，在这种情况下，值传递（pass-by-value）与引用传递（pass-by-reference）没有区别（甚至可能更快）。
2. 如果你使用CString作为KEY，你应该使用LPCTSTR作为ARG_KEY，而不是CString&，我们稍后会详细讨论这个问题。

那么，我该如何让 CMap 与我的 ClassX 一起工作？

嗯，正如我之前提到的，CMap是一个哈希表。哈希表会尝试从键（key）中获取“哈希值”——一个UINT——并使用该哈希值作为哈希表中的索引（实际上是哈希值 % 哈希表大小）。如果多个键具有相同的哈希值，它们将被链接在一个链表中。因此，你首先需要做的是提供一个哈希函数。

CMap将调用一个模板函数HashKey()来进行哈希计算。默认实现以及针对LPCSTR和LPCWSTR的专门化版本如下所示：

// inside <afxtemp.h>
template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
    // default identity hash - works for most primitive values
    return (DWORD)(((DWORD_PTR)key)>>4);
}

// inside <strcore.cpp>
// specialized implementation for LPCWSTR
#if _MSC_VER >= 1100
template<> UINT AFXAPI HashKey<LPCWSTR> (LPCWSTR key)
#else
UINT AFXAPI HashKey(LPCWSTR key)
#endif
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

// specialized implementation for LPCSTR
#if _MSC_VER >= 1100
template<> UINT AFXAPI HashKey<LPCSTR> (LPCSTR key)
#else
UINT AFXAPI HashKey(LPCSTR key)
#endif
{
    UINT nHash = 0;
    while (*key)
        nHash = (nHash<<5) + nHash + *key++;
    return nHash;
}

正如你所见，默认行为是“假设”键是一个指针，并将其转换为DWORD。这就是为什么如果你不为你的ClassX提供专门化的HashKey()，你会得到“error C2440: 'type cast': cannot convert from 'ClassXXX' to 'DWORD_PTR'”这样的错误。

而且，由于MFC只为LPCSTR和LPCWSTR提供了专门化实现，而没有为CStringA或CStringW提供，所以如果你想在CMap中使用CString，你必须声明CMap<CString, LPCTSTR....>。

好的，现在你知道了CMap是如何计算哈希值的，但由于多个键可能具有相同的哈希值，CMap需要遍历整个链表来查找具有完全相同的键“内容”的那个，而不仅仅是具有相同的“哈希值”。当CMap进行匹配时，它将调用另一个模板函数CompareElements()。

// inside <afxtemp.h>
// noted: when called from CMap,
//        TYPE=KEY, ARG_TYPE=ARG_TYPE
// and note pElement1 is TYPE*, not TYPE
template<class TYPE, class ARG_TYPE>
BOOL AFXAPI CompareElements(const TYPE* pElement1, 
                            const ARG_TYPE* pElement2)
{
    ASSERT(AfxIsValidAddress(pElement1, 
           sizeof(TYPE), FALSE));
    ASSERT(AfxIsValidAddress(pElement2, 
           sizeof(ARG_TYPE), FALSE));

    // for CMap<CString, LPCTSTR...>
    // we are comparing CString == LPCTSTR
    return *pElement1 == *pElement2;
}

因此，如果你想在CMap中使用你自己自定义的ClassX，你必须为HashKey()和CompareElements()提供专门化的实现。

示例：CMap 与 CString*

作为示例，下面是你需要做的事情，以便CMap能够与CString*配合使用，当然，是使用string的内容作为键，而不是指针的地址。

template<> 
UINT AFXAPI HashKey<CString*> (CString* key)
{
    return (NULL == key) ? 0 : HashKey((LPCTSTR)(*key));
}

// I don't know why, but CompareElements can't work with CString*
// have to define this
typedef CString* LPCString;

template<>
BOOL AFXAPI CompareElements<LPCString, LPCString> 
     (const LPCString* pElement1, const LPCString* pElement2)
{
    if ( *pElement1 == *pElement2 ) {
        // true even if pE1==pE2==NULL
        return true;
    } else if ( NULL != *pElement1 && NULL != *pElement2 ) {
        // both are not NULL
        return **pElement1 == **pElement2;
    } else {
        // either one is NULL
        return false;
    }
}

主程序非常简单：

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
    CMap<CString*, CString*, int, int> map;
    CString name1 = "Microsoft";
    CString name2 = "Microsoft";
    map[&name1] = 100;
    int x = map[&name2];

    printf("%s = %d\n", (LPCTSTR)name1, x);*/
    return 0;
}

--------- console output ---------
Microsoft = 100

请注意，即使没有专门化的HashKey()和CompareElements()，程序也能编译通过，但输出结果将是0，这可能不是你想要的。

我关于 CMap 的最后说明

1. CMap是一个哈希表，而STL::map是一个树形图，比较两者在性能上的优劣没有意义（这就像比较苹果和橘子！）。但是，如果你需要按排序顺序检索键，那么你必须使用STL::map。
2. HashKey()的设计对整体性能至关重要。你应该提供一个哈希函数，它具有较低的冲突率（不同的键通常会有不同的哈希值）并且易于计算（而不是对string进行MD5计算等）。我们必须注意到——至少对于某些类来说——这并不容易。
3. 在使用CMap（以及STL::hash_map）时，请务必注意哈希表的大小。正如MSDN所引用的，“哈希表的大小应该是一个素数。为了最大程度地减少冲突，大小应该比预期的最大数据集大20%左右。”默认情况下，CMap的哈希表大小是17，这对于大约10个键来说应该足够了。你可以使用InitHashTable(UINT nHashSize)来更改哈希表大小，但只能在向映射中添加第一个元素之前进行。你可以在这里找到更多素数。（并且不要将其与CMap(UINT nBlockSize)混淆，nBlockSize是为了获取多个CAssoc以加速新节点的创建。）

参考文献

• [MSDN] Collection Class Helper（集合类助手）
• [MSDN] CMap::InitHashTable
• [NIST DADS] Red Black Tree（红黑树）

历史

• 2006年3月17日：上传初始版本

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。