浪迹天涯

唯有努力...
努力....再努力...

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用值传递与参数传递没有什么不同
2 如果用CString作为KEY,你应该用LPCTSTR   做ARG_KEY而非CString&,接下来我门会讨论原因。

如何让CMap类为自己工作
好的,就象我前面说过的,CMap是一个哈西表,一个哈西表要有“哈西值“——一个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类型,这就是为什么会出现“error C2440:’type cast’:cannot convert from ‘ClassXXX’to ‘DWORD_PTR’”如果你不提供一个特别的HashKey()函数给你的类就会出现上述情况。并且由于MFC仅仅提供了特殊的工具LPCSTR和LPCWSTR,却没有提供CStringA或CStringW,如果你想要在CMap中用CString,就必须声明CMap<CString ,LPCSTR….>,OK,现在你知道怎么计算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,你不得不重写HashKey()和CompareElements()
结束语
1 CMap是一个哈西表,而STL::map是一个树表,对他们做比较是没有意义的。但是,如果你你要重新找到有序的关键字,你就得使用STL::map
2 HashKey()的设计是高效的。你应该提供一个较少冲突的HashKey(),并且容易计算。你要记注,对于有些类来说,这不容易。
3 当用Cmap(或STL::hash_map),要注意哈西表的大小。

附能用于CString的CMap重写的HashKey()和CompareElements()
using namespace std;
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;
 }
}:

posted on 2008-01-24 15:41 浪迹天涯 阅读(3427) 评论(2)  编辑 收藏 引用 所属分类: C++

评论

# re: CMap详解 2008-01-24 15:47 浪迹天涯

以下是实现忽略大小写的HashKey函数以及KeyCompare函数:
// 实现忽略大小写的
template<>
inline bool HS_HashKey<char*>::KeyCompare( char* const&key1, char* const&key2)
{
return stricmp(key1, key2) == 0;
}

template<>
inline unsigned int HS_HashKey<char*>::KeyHash( char* const&lkey)
{
unsigned int nHash = 0;
const char* key = lkey;
while (*key)
{
if(*key >= 'A' && *key <= 'Z')
{
nHash = (nHash<<5) + nHash + *key++;
nHash += ('a' - 'A');
}
else
nHash = (nHash<<5) + nHash + *key++;
}
return nHash;
}
  回复  更多评论   

# re: CMap详解 2008-06-06 17:21 11

不知所云  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年1月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(20)

随笔分类(30)

随笔档案(29)

文章分类

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜