Click here to Skip to main content
15,867,686 members
Articles / Web Development / HTML

CMap How-to

Rate me:
Please Sign up or sign in to vote.
4.57/5 (35 votes)
16 Mar 20064 min read 212.8K   1.3K   55   18
How to use a CMap

Introduction

Programmers like me, who learnt STL::map before CMap, always think CMap is difficult to use, and always try to use CMap in the way as a STL::map. In this article, I will explain about CMap and what you should do to use it for your own custom classes. And at the end of this article, I will show an example of how to use CMap correctly with CString* (note, I mean CString pointer and not CString :>)

CMap Internal

The first thing to be noted is that CMap is actually a hash map, and not a tree map (and usually a Red-black tree) as STL::map. Shown below is the internal structure of a CMap.

How to Declare a CMap

Many people get confused about CMap's declaration CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>, why not just CMap<KEY, VALUE>?

In fact, the ultimate data container in CMap is CPair, and the internal of CPair is {KEY, VALUE}. Therefore, CMap will really store a KEY, and not ARG_KEY. However, if you check with the MFC source code, almost all the internal parameters passing within CMap itself is called with ARG_KEY and ARG_VALUE, therefore, using KEY& as ARG_KEY seems always a correct thing, except when:

  1. You are using primitive date types like int, char, where pass-by-value makes no difference (may be even faster) with pass-by-reference.
  2. If you use CString as KEY, you should use LPCTSTR as ARG_KEY and not CString&, we will talk more about this later.

So What Should I Do to Make CMap Work With My ClassX

Well, as I mentioned earlier, CMap is a hash map, a hash map will try to get the "hash value" -- a UINT -- from the key, and use that hash value as the index in the hash table (well, actually it is hash value % hash table size). If more then one key have the same hash value, they will be linked in a linked list. Therefore, the first thing you have to do is to provide a hash function.

CMap will call a templated function HashKey() to do the hashing. The default implementation and specialized version for LPCSTR and LPCWSTR are listed as follows:

C++
// 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;
}

As you can see, the default behavior is to "assume" that the key is a pointer, and convert it to DWORD, and that's why you will get "error C2440: 'type cast': cannot convert from 'ClassXXX' to 'DWORD_PTR'" if you don't provide a specialized HashKey() for your ClassX.

And because MFC only has specialized implementations for the LPCSTR and LPCWSTR, and not for CStringA nor CStringW, if you want to use CString in CMap, you have to declare CMap<CString, LPCTSTR....>.

OK, now you know how CMap calculates the hash value, but since more than one key may have the same hash value, CMap needs to traverse the whole linked list to find the one with exactly the same key "content", not only with the same "hash value". And when CMap does the matching, it will call CompareElements(), another templated function.

C++
// 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;
}

Therefore, if you want to use CMap with your own custom ClassX, you will have to provide a specialized implementation for HashKey() and CompareElements().

Example: CMap with CString*

Provided as an example, below is what you need to do to make CMap work with CString*, and of course, using the string content as the key, and not the address of the pointer.

C++
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;
    }
}

And the main program is as simple as:

C++
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
    CMap<CString*, CString*, int, int> map;
    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

Please note that the program can compile without error even without the specialized HashKey() and CompareElements(), but of course, the output will then be 0, probably not what you want.

My Final Note About CMap

  1. CMap is a hash map and STL::map is a tree map, there is no meaning comparing the two for performance (it would be like comparing apples and oranges!). But if you will retrieve the keys in sorted order, then you will have to use STL::map.
  2. The design of HashKey() is critical to the overall performance. You should provide a HashKey() that has a low collision rate (different keys generally would have different hash values) and is easy to calculate (not a MD5 of the string, etc..). And we have to note that -- at least for some of the classes -- this is not easy.
  3. When using CMap (as well as STL::hash_map), always beware of the hash table size. As quoted in MSDN, "the hash table size should be a prime number. To minimize collisions, the size should be roughly 20 percent larger than the largest anticipated data set". By default, CMap hash table size is 17, which should be okay for around 10 keys. You can change the hash table size with InitHashTable(UINT nHashSize), and can only do so before the first element is added to the map. You can find more prime numbers here. (And don't mix-up with CMap(UINT nBlockSize), nBlockSize is to acquire more than one CAssoc to speed up the creation of a new node.)

References

History

  • 17th March 2006: Initial version uploaded

License

This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below.

A list of licenses authors might use can be found here.


Written By
Hong Kong Hong Kong
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionAt least in your sample code, HashKey() and CompareElements() are not really necessary. Pin
Zhenyu Yang22-Apr-20 9:41
Zhenyu Yang22-Apr-20 9:41 
GeneralMy vote of 5 Pin
unugy29-May-15 15:01
unugy29-May-15 15:01 
GeneralWrapper Pin
ParaRic25-Oct-07 20:23
ParaRic25-Oct-07 20:23 
GeneralTrying to get it working with multiple classes including CMap Pin
gsuchy20-Feb-07 2:11
gsuchy20-Feb-07 2:11 
GeneralTrying to get CMap working [modified] Pin
devvvy28-Dec-06 19:08
devvvy28-Dec-06 19:08 
Generalhash_map Pin
Aza17-Mar-06 2:30
Aza17-Mar-06 2:30 
GeneralRe: hash_map Pin
Nemanja Trifunovic17-Mar-06 2:47
Nemanja Trifunovic17-Mar-06 2:47 
GeneralRe: hash_map Pin
Aza17-Mar-06 2:55
Aza17-Mar-06 2:55 
GeneralRe: hash_map Pin
Nemanja Trifunovic17-Mar-06 6:27
Nemanja Trifunovic17-Mar-06 6:27 
GeneralRe: hash_map Pin
Aza17-Mar-06 7:01
Aza17-Mar-06 7:01 
GeneralRe: hash_map Pin
Nemanja Trifunovic17-Mar-06 8:43
Nemanja Trifunovic17-Mar-06 8:43 
Aza wrote:
But STLPort is cross plattform so my original statement still stands (as compared to CMap, not the standard ).


I am not saying hash_map is worse than CMap - all I am saying is that it may give the false impression of being a Standard supported container, which is not. Especially that some of this implementations put it inside of std namespace, which is not alowed.


Aza wrote:
So you are saying that one should not use the parts of boost not included in the tr1?


God forbid Smile | :) Boost is good. Besides, one cannot constraint himself on using only the Standard C++ Library - it simply doesn't cover enough enough funcionality for most real-world applications.



My programming blahblahblah blog. If you ever find anything useful here, please let me know to remove it.
GeneralRe: CRBMap and CRBMultiMap Pin
Sam NG19-Mar-06 14:53
Sam NG19-Mar-06 14:53 
GeneralRe: hash_map Pin
David Pritchard25-Jun-07 4:02
David Pritchard25-Jun-07 4:02 
GeneralShort CMap how-to Pin
Anders Dalvander17-Mar-06 1:28
Anders Dalvander17-Mar-06 1:28 
GeneralRe: Short CMap how-to Pin
Ștefan-Mihai MOGA17-Mar-06 3:07
professionalȘtefan-Mihai MOGA17-Mar-06 3:07 
GeneralRe: Short CMap how-to Pin
flyingxu16-Apr-06 15:13
flyingxu16-Apr-06 15:13 
GeneralRe: Short CMap how-to Pin
Anders Dalvander17-Apr-06 20:23
Anders Dalvander17-Apr-06 20:23 
GeneralRe: Short CMap how-to Pin
David Pritchard25-Jun-07 4:00
David Pritchard25-Jun-07 4:00 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.