CMap

映射关键码的函数

CMap，计算机语言函数，作用是映射的关键码。支持元素查找、插入、删除等操作，并提供散列表初始化和大小获取等功能。

参数

KEY对象的类，用作映射的关键码。ARG_KEY参数KEY使用的数据类型，通常为KEY的参考。VALUE存储在映射中对象的类。ARG_VALUE参数VALUE使用的数据类型，通常为VALUE的参考。

说明

CMap是把唯一关键码映射到值的字典收集类。一旦在映射中插入了一个关键码值对（元素），就可以使用这些关键码，有效地获取或删除对。同样，也可以反复使用映射中的所有元素。

POSITION类型变量用于替换所有映射变量的入口。可以使用POSITION来“记忆”入口和映射中的遍历。可能认为这种遍历是通过关键码值来依次进行的，但其实不是。获取元素的次序没有确定。

该类的某些成员函数调用了全局的帮助函数，它们必须定制，以满足CMap类的更多用途。请参阅“Microsoft Visual C++ MFC库参考”中的“宏和全局”部分中的“收集类帮助程序”。

CMap引入了宏IMPLEMENT_SERIAL，支持其元素的串行化和转储。如果映射存储到档案文件中，那么每一元素都可利用加载插入（<<）操作符或Serialize成员函数来依次进行串行化。如果要了解有关在映射中进行个别元素的诊断转储，那么转储内容的深度必须为1或更大。当CMap对象删除或其元素被删除，那么关键码和值都将被删除。映射类的派生与列表的派生相似。

请参阅联机文档“Visual C++程序员指南”中的“收集”部分，以进一步了解特殊用途的列表类的派生。

#include

CMap类的成员

构造函数

CMap构造一个映射关键码为值的收集

操作符

Lookup查找与指定关键码对应的值；SetAt在映射中插入一个元素，但假如发现了相匹配的关键码，则替换已经存在的元素；operator []在映射中插入一个元素，它是代替SetAt的操作符；RemoveKey删除关键码指定的元素；RemoveAll删除映射中所有的元素；GetStartPosition返回第一个元素的位置；GetNextAssoc获取循环中下一个元素；GetHashTableSize返回散列表的大小（元素的个数）；InitHashTable初始化散列表，并指定其大小。

状态

GetCount返回映射中元素的个数；IsEmpty测试是否为空映射（即没有元素）。

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

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 (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 key)

#else

UINT 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 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<CString, LPCTSTR...>

// we are comparing CString == LPCTSTR

return *pElement1 == *pElement2;

}

因此，如果你想让CMap用于你自己的类ClassX，就必须提供HashKey()和CompareElements()的专门化实现。

示例：CMap用于CString*作为一个例子，以下说明了要将CMap用于CString*前你需要做的。当然了，是使用字符串的值作为键（KEY），而不是用指针的地址。

template<>

UINT AFXAPI HashKey (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

(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*, CString*, int, int> map;

map[&name1] = 100;

int x = map[&name2];

printf 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来加速创建新结点。）

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省