CMap详解

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）,要注意哈西表的大小。

------------------------------------------------------------------(第二部分)--------------------------------------------------------------------------

先看一个简单的实化例子吧：

typdedef CMap<CString, LPCTSTR，CString, CString&>   CStrMap;

显然，向这样的用法，是无可厚非的，就像我们国家的中医，在经过无数次致命的尝试之后，得到了这个不再苦涩的，似乎也可以包治百病的灵丹妙药。可是，这毕竟是个令人心惊胆战的用法，尤其对于那些并不熟悉并试图熟悉CMap的小家伙们。我们还是先来看看CMap类型参数列表吧：

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>

它继承了CArray以及CList的参数风格，将传入类型与返回类型分开，其中带有ARG_前缀的是传入类型，另外一个则是返回类型，这已经是我们不止一次的抱怨为什么要将类型参数分开了，其实实践证明，它们的确可以被合并起来，不过参数传入的灵活性将会受到部分的影响。

我们在《CMap如何使用，用法举例》中，已经比较详细的讨论过为什么CMap的ARG_KEY与KEY可以是不同的参数类型，其实这可以推广到所有类似的模板之中。不得不声明的一点是：在CMap中，实际存储的是KEY以及VALUE。那么，现在我们来看看CStrMap到底是如何实化的。

我们看到在CMap中，类型参数ARG_KEY的引参是LPCTSTR，而与之对应的KEY的引参却又是CString，它们是如此的固执，既然都指代了同样的内容，为什么又偏偏将对方视若不见呢？其实，这与CMap的内部实现存在着密不可分的关系，由于在CMap的内部，建立了一个Hash表，所以，必须将所有的传入参数置换为类似于int类型的整数，这样才可以符合散列函数的参数类型，否则CMap在编译时会报错。那么又是为什么？我们可以将ARG_KEY使用LPCTSTR来实化呢？其实，这又牵扯到了Hash表的实现问题，当然其中也包含了CString的实现问题。我们知道，存储在CStrMap内部的KEY仍然是CString，而我们对Hash表的操作，无非也就是给出一个整型的数，然后根据散列函数来寻找一个存储地址而已，尤其，当我们使用operator[]操作符的时候，如果我们给定的KEY所对应的VALUE并不存在的话，CMap会自动的为我们生成一个相应的元组，而如果你继而对它赋值的话，它会将ARG_KEY直接赋值给KEY，而这里就涉及到KEY的赋值构造函数了（其实，我更想叫它赋值操作符），现在我们使用的KEY是CString，而我们却要将一个LPCTSTR赋值于它，所以，我们就必须重载这个函数，其实也就是这样的一个函数：

CString& operator=(LPCTSTR lpsz);

显然，这立即解决了我们的问题，不过，这仅仅是从逻辑功能层面，如果你传入的KEY是个很长的字符串的话，那么必然会对CStrMap的性能造成影响，其实这样的隐患也同样存在于VALUE身上，乃至其它类似的模板类上，这不得不引起我们的足够重视！

C++，这门完美的近乎没有任何瑕疵的OOP语言，无疑就是闪耀星空的旷世巨献，然而，这似乎并没有引起每个人的共鸣。C++从C中的诞生，似乎就注定了，它永远都不可能像JAVA那样血统纯正，我不得不承认，它并非一个严格意义上的OOP(Oriented-object language，面向对象设计语言)，然而就是这种近乎不合理的缺陷，却又造就了它近乎不合理的适应性，我是向来瞧不起解释性语言的，因为我本人就编写过脚本的解释器，实践证明，它们的效率要远远的落后于编译性语言，虽然它们常常号称自己如何的平台无关，如何的小而强大。但，对于绝大多数的程序员来说，JAVA的确有很多的优势，也许其中之一，便是简单易学，其实这似乎更像一个借口。指针一度是困扰相当一部分程序员的暗物质，而C++更将这种震慑发挥到极致。显然C++的确很难，难到令这个世界上，至少50%以上的程序员，望而却步。然而一个几乎包罗万象的程序设计语言，几乎能容忍一切的全能语言，它到底有着什么样的魔力，却令另外50%的人如此的钟意，如此的着迷？