VC++ MFC 编程--CMap的使用
本文翻译自: CMap How-to - CodeProject
介绍
像我这样的程序员，在CMap之前学习了STL::map，总是认为CMap很难使用，并且总是尝试以STL::map的方式使用CMap。在本文中，我将解释CMap，以及如何将它用于您自己的自定义类。在本文的最后，我将展示一个如何正确使用CMap与CString*的例子(注意，我的意思是CString指针，而不是CString:>)
CMap 内部
首先要注意的是，CMap实际上是一个散列映射，而不是像STL::map那样的树映射(通常是红黑树)。下面显示的是CMap的内部结构。
CMap 的声明
很多人对CMap的声明CMap
实际上，CMap中的最终数据容器是CPair, CPair的内部是{KEY, VALUE}。因此，CMap将真正存储一个KEY，而不是ARG_KEY。然而，如果你检查MFC源代码，几乎所有在CMap内部传递的内部参数都是用ARG_KEY和ARG_VALUE调用的，因此，使用KEY&作为ARG_KEY似乎总是正确的，除非:
您正在使用int、char等基本类型，其中按值传递与按引用传递没有区别(可能更快)。
如果你使用CString作为KEY，你应该使用LPCTSTR作为ARG_KEY，而不是CString&，我们将在后面讨论更多。
那么我应该怎么做才能使我的CMap正确的工作?
正如我前面提到的，CMap是一个哈希映射，哈希映射将尝试从键中获取“哈希值(hash value)” —— 一个UINT，并使用该哈希值作为哈希表中的索引(实际上它是 哈希值 % 哈希表大小)。如果多个键具有相同的哈希值，它们将被链接到一个链表中。因此，您要做的第一件事就是提供一个 hash 函数。
CMap将调用一个模板函数HashKey()来执行哈希。LPCSTR和LPCWSTR的默认实现和专用版本如下:
// C++
// inside
template
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
// default identity hash - works for most primitive values
return (DWORD)(((DWORD_PTR)key)>>4);
}
// inside
// specialized implementation for LPCWSTR
#if _MSC_VER >= 1100
template<> UINT AFXAPI HashKey
#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
#else
UINT AFXAPI HashKey(LPCSTR key)
#endif
{
UINT nHash = 0;
while (*key)
nHash = (nHash<<5) + nHash + *key++;
return nHash;
}
正如你所看到的，默认行为是“假设”键是一个指针，并将其转换为DWORD，这就是为什么你会得到“错误C2440: '类型转换':不能从'ClassXXX'转换为'DWORD_PTR'”，如果你不为你的ClassX提供一个专门的HashKey()。
而且因为MFC只有专门的实现LPCSTR和LPCWSTR，而不是CStringA和CStringW，如果你想在CMap中使用CString，你必须声明CMap
好了，现在你知道CMap是如何计算哈希值的了，但是由于多个键可能有相同的哈希值，CMap需要遍历整个链表来找到一个键“content”完全相同的键，而不仅仅是相同的“哈希值”。当CMap进行匹配时，它将调用另一个模板化函数CompareElements()。
// inside
// noted: when called from CMap,
// TYPE=KEY, ARG_TYPE=ARG_TYPE
// and note pElement1 is TYPE*, not TYPE
template
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
// we are comparing CString == LPCTSTR
return *pElement1 == *pElement2;
}
因此，如果您想在自己的自定义ClassX中使用CMap，则必须为HashKey()和CompareElements()提供专门的实现。
示例: CMap with CString*
作为一个例子，下面是你需要做的，使CMap与CString*一起工作，当然，使用字符串内容作为键，而不是指针的地址。
template<>
UINT AFXAPI HashKey
{
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
(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 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的最后一点说明
CMap是一个散列映射，而STL::map是一个树状映射，比较两者在性能上没有任何意义(这就像比较苹果和橘子一样!)但是，如果要按排序顺序检索键，则必须使用STL::map。
HashKey()的设计对整体性能至关重要。您应该提供一个HashKey()，它具有低碰撞率(不同的键通常具有不同的哈希值)并且易于计算(不是字符串的MD5等)。这并不容易。
当使用CMap(以及STL::hash_map)时，总是要注意哈希表的大小。正如MSDN引用的那样，“哈希表的大小应该是素数。为了最大限度地减少碰撞，大小应该比最大的预期数据集大大约20%” 。默认情况下，CMap哈希表大小为17，对于大约10个键来说应该是可以的。您可以使用InitHashTable(UINT nashsize)更改哈希表的大小，并且只能在第一个元素添加到映射之前这样做。你可以在这里找到更多质数。(不要混淆CMap(UINT nBlockSize))，nBlockSize是获取多个CAssoc来加速新节点的创建。)
参考文献
[MSDN] Collection Class Helper
[MSDN] CMap::InitHashTable
[NIST DADS] Red Black Tree