偶看新闻the rusty bolt:CMap How-to
来源：百度文库 编辑：偶看新闻 时间：2024/04/28 12:12:40
英文原文：http://www.codeproject.com/KB/architecture/cmap_howto.aspx?print=true
简介
一些像我一样的程序员，先学STL::map再学CMap，常常认为CMap很难用，而且总是使用STL::map的方式去使用CMap。在本文中，我会详细讲解CMap以及如何将你自己的类用于CMap。末尾，我将通过一个例子来演示如何正确地将CString*用于CMap（注意，我指的是一个指向CString的指针类型而不是CString本身）。
CMap内部机制
首先要注意的是CMap实际上是一种Hash Map，而不是像STL::map一样为树型（Tree，通常为红黑树）Map。下图是CMap的内部结构：
如何声明CMap
许多人搞不清CMap的声明形式CMap
事实上，归根到底，CMap是用CPair来存放数据的，CPair的形式是{KEY, VALUE}。因此CMap实际存放的是KEY，而不是ARG_KEY。但是，如果你查阅MFC的代码，你会发现几乎所有的CMap成员函数的参数都标有ARG_KEY和ARG_VALUE类型，所以，用KEY&来作为ARG_KEY的类型通常是正确的，除非：
1. 你使用原子类型数据类型如int, char，此时值传递和引用传递并没有什么差别（甚至值传递更快）。
2. 如果你用CString作为键（KEY）类型，你应使用LPCTSTR作为ARG_KEY的类型，而不是用CString&，原因我稍后说明。
我如何将CMap用于我自己的类ClassX
正如我刚才提到的，CMap是一种Hash Map，Hash Map要求每个元素都要有一个Hash值——一个关于KEY的函数，Hash Map用这个值作为Hash表的索引。如果有多个KEY的Hash值相同，它们将以链表的方式存储。所以，你要做的第一件事就是提供一个Hash函数。
CMap会调用模板函数HashKey()来计算Hash值。默认的实现以及对于LPCSTR和LPCWSTR的专门实现如下：
// inside templateAFX_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 >= 1100template<> UINT AFXAPI HashKey#elseUINT AFXAPI HashKey(LPCWSTR key)#endif{ UINT nHash = 0; while (*key) nHash = (nHash<<5) + nHash + *key++; return nHash;}// specialized implementation for LPCSTR#if _MSC_VER >= 1100template<> UINT AFXAPI HashKey#elseUINT AFXAPI HashKey(LPCSTR key)#endif{ UINT nHash = 0; while (*key) nHash = (nHash<<5) + nHash + *key++; return nHash;}
如你所见，缺省行为会“假定”KEY是一个指针，并将它转换为DWORD类型，这就是为什么当你没有为你的ClassX提供一个专门的HashKey()时你会得到“error C2440: 'type cast': cannot convert from 'ClassXXX' to 'DWORD_PTR'”错误的原因。
同时，因为MFC只是实际了LPCSTR和LPCWSTR的专门化，并没有实现CStringA和CStringW的专门化，因此如果你想使用CString作为CMap的键类型，你要声明为CMap
好了，现在你知道CMap如何计算Hash值了，但是由于可能会有多个键的Hash值相同，CMap需要遍历整个链表来找到要求的数据，而不只是在相同的Hash值中。并且当CMap进行匹配时，会调用CompareElements()，这是另一个模板函数。
// inside // noted: when called from CMap,// TYPE=KEY, ARG_TYPE=ARG_TYPE// and note pElement1 is TYPE*, not TYPEtemplateBOOL 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;}因此，如果你想让CMap用于你自己的类ClassX，就必须提供HashKey()和CompareElements()的专门化实现。
示例：CMap用于CString*
作为一个例子，以下说明了要将CMap用于CString*前你需要做的。当然了，是使用字符串的值作为键（KEY），而不是用指针的地址。
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 thistypedef 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;
}}Main函数如下：
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 ", (LPCTSTR)name1, x);*/ return 0;}--------- console output ---------Microsoft = 100注意即使你没有提供HashKey()和CompareElements()的专门化编译器也不会报错，但这样的话输出为0，或许不是你想要的。
关于CMap的总结
CMap是一种Hash Map而STL::map是Tree Map，比较两者的效率是没有意义的（如同比较苹果和桔子！）。但是如果你要按顺序取得关键字，你需要使用STL::map。
HashKey()的设计是效率的关键。你应该提供一个低碰撞（即不同的关键字产生相同的Hash值）率、容易计算（而不是像MD5那样）的HashKey()。我们必须注意这点——至少对于某些类来说——并不是件容易的事。
当使用CMap（以及STL::hash_map）时，注意Hash表的大小。引用一段MSDN的说明：“Hash表的大小应该是一个质数。为了减少碰撞，Hash表的大小应该超出最大预计容量的20%。默认情况下，CMap的Hash表大小为17，这对于10个关键字左右的数据很合适。你可以用InitHashTable(UINT nHashSize)来改变Hash表的大小，并且只能在加入第一个元素之前这样做。你可能在这里找到很多质数。（不要与CMap(UINT nBlockSize)弄混了，nBlockSize用于获得多个CAssoc来加速创建新结点。）