https://baike.baidu.com/item/CMap/2334917?fr=aladdin
CMap Editing
CMap is a function in the computer language, which functions as the key of the mapping.
English Name CMap Function Used as the key of the mapping Includes Classes of KEY Objects Belongs to Data type used by parameter KEY
Table of Contents
1 Parameters
2 Explanation
▪ Constructor
▪ Operators
▪ Status
3 Usage of CMap
Parameter Editing
Classes of KEY objects, used as the key of the mapping. ARG_KEY data type used by parameter KEY, usually a reference of KEY. VALUE classes of objects stored in the mapping. ARG_VALUE data type used by parameter VALUE, usually a reference of VALUE.
Explanation Editing
CMap is a dictionary collection class that maps unique keys to values. Once a key-value pair (element) is inserted into the mapping, these keys can be used to effectively obtain or delete the pairs. Similarly, all elements in the mapping can be reused repeatedly.
The POSITION type variable is used to replace the entries of all mapping variables. POSITION can be used to "remember" the entries and traversal in the mapping. You may think that this traversal is carried out in sequence through key values, but actually it is not. The order of obtaining elements is not determined.
Some member functions of this class call global helper functions, which must be customized to meet more uses of the CMap class. Please refer to the "Macro and Global" part in the "Microsoft Visual C++ MFC Library Reference" for "Collection Class Helpers".
CMap introduces the macro IMPLEMENT_SERIAL, which supports serialization and dumping of its elements. If the mapping is stored in an archive file, each element can be serialized one by one using the loading insertion (<<) operator or the Serialize member function. If you want to understand the diagnostic dumping of individual elements in the mapping, the depth of the dumped content must be 1 or greater. When the CMap object is deleted or its elements are deleted, both the key and the value will be deleted. The derivation of the mapping class is similar to the derivation of the list.
Please refer to the "Collections" part in the online document "Visual C++ Programmer's Guide" to further understand the derivation of special-purpose list classes.
#include <afxtempl.h>
Members of the CMap class
Constructor
CMap constructs a collection where keys are mapped to values.
Operators
Lookup finds the value corresponding to the specified key; SetAt inserts an element into the mapping, but if a matching key is found, the existing element is replaced; operator inserts an element into the mapping, which is an operator instead of SetAt; RemoveKey deletes the element specified by the key; RemoveAll deletes all elements in the mapping; GetStartPosition returns the position of the first element; GetNextAssoc gets the next element in the cycle; GetHashTableSize returns the size of the hash table (number of elements); InitHashTable initializes the hash table and specifies its size.
Status
GetCount returns the number of elements in the mapping; IsEmpty tests whether it is an empty mapping (i.e., has no elements).
Usage of CMap Editing
In the final analysis, CMap stores data with CPair, and the form of CPair is {KEY, VALUE}. Therefore, CMap actually stores KEY, not ARG_KEY. However, if you refer to the code of MFC, you will find that the parameters of almost all CMap member functions are marked with ARG_KEY and ARG_VALUE types. So, using KEY& as the type of ARG_KEY is usually correct, unless:
1. You use atomic data types such as int, char. At this time, there is no difference between value passing and reference passing (even value passing is faster).
2. If you use CString as the key (KEY) type, you should use LPCTSTR as the type of ARG_KEY instead of using CString&. The reason will be explained later.
How do I use CMap for my own class ClassX? As I just mentioned, CMap is a Hash Map. Hash Map requires that each element has a Hash value - a function about KEY. Hash Map uses this value as the index of the hash table. If the Hash values of multiple KEYs are the same, they will be stored in the form of a linked list. So, the first thing you need to do is provide a Hash function.
CMap will call the template function HashKey() to calculate the Hash value.
The default implementation and the specialized implementations for LPCSTR and LPCWSTR are as follows:
// 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 will "assume" that KEY is a pointer and convert it to DWORD type. This is why you will get the "error C2440: ''type cast'': cannot convert from ''ClassXXX'' to ''DWORD_PTR''" error when you do not provide a specialized HashKey() for your ClassX.
At the same time, because MFC only implements the specialization of LPCSTR and LPCWSTR, and does not implement the specialization of CStringA and CStringW, so if you want to use CString as the key type of CMap, you should declare it as CMap<CString, LPCTSTR, ……>.
Okay, now you know how CMap calculates the Hash value. But because there may be multiple keys with the same Hash value, CMap needs to traverse the entire linked list to find the required data, not just in the same Hash value. And when CMap performs matching, it will call CompareElements(), which is another template function.
// 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 for your own class ClassX, you must provide specialized implementations of HashKey() and CompareElements().
Example: CMap used for CString* As an example, the following illustrates what you need to do before using CMap for CString*. Of course, the value of the string is used as the key (KEY), not the address of the pointer.
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;
}
}
The main function is as follows:
int _tmain(int argc, TCHAR* argv, TCHAR* envp)
...{
CMap<CString*, CString*, int, int> map;
CString name1 = "Microsoft";
CString name2 = "Microsoft";
map = 100;
int x = map;
printf("%s = %d ", (LPCTSTR)name1, x);*/
return 0;
}
--------- console output ---------
Microsoft = 100
Note that even if you do not provide specialized implementations of HashKey() and CompareElements(), the compiler will not report an error, but in this case the output is 0, which may not be what you want.
Summary of CMap CMap is a Hash Map and STL::map is a Tree Map. It is meaningless to compare the efficiencies of the two (it is like comparing apples and oranges!). But if you want to obtain keywords in order, you need to use STL::map.
The design of HashKey() is the key to efficiency. You should provide a HashKey() with a low collision rate (i.e., different keywords generate the same Hash value) and easy to calculate (not like MD5). We must pay attention to this - at least for some classes - it is not an easy task.
When using CMap (and STL::hash_map), pay attention to the size of the hash table. Quoting a note from MSDN: "The size of the hash table should be a prime number. To reduce collisions, the size of the hash table should exceed 20% of the maximum expected capacity. By default, the hash table size of CMap is 17, which is suitable for data with about 10 keywords. You can use InitHashTable(UINT nHashSize) to change the size of the hash table, and you can only do this before adding the first element. You may find many prime numbers here. (Do not confuse with CMap(UINT nBlockSize), nBlockSize is used to obtain multiple CAssoc to speed up the creation of new nodes.)
[
Last edited by zzz19760225 on 2017-12-11 at 19:53 ]
