之前用Java 感觉 Map 就很好用,但是到用 MFC 的 CMap 类的时候就感觉很茫然,感觉非常的不好用,具体表现在对于键值的类型指定居然需要四个参数,这是为什么呢?

从我们的感官上而言,也是从 Java 中的使用经历来说,一个 Map 其实上是一个 Hash 表,每个 Hash 表有多个 Hash 链组成。对于一个键,根据一定的方法得到其 Hash 值,然后相同 Hash 值的元素就会放到一个 Hash 链上。

那么 CMap 是不是这样的呢,我们知道 CMap 其实是一个模板类。

CMap

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CMap : public CObject
{
public:
// CPair
struct CPair
{
const KEY key;
VALUE value;
protected:
CPair( ARG_KEY keyval ) : key( keyval ) {}
};
public:
// Construction
explicit CMap(INT_PTR nBlockSize = 10);

// Attributes
// number of elements
INT_PTR GetCount() const;
INT_PTR GetSize() const;
BOOL IsEmpty() const;

// Lookup
BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
const CPair *PLookup(ARG_KEY key) const;
CPair *PLookup(ARG_KEY key);

// Operations
// Lookup and add if not there
VALUE& operator[](ARG_KEY key);

// add a new (key, value) pair
void SetAt(ARG_KEY key, ARG_VALUE newValue);

// removing existing (key, ?) pair
BOOL RemoveKey(ARG_KEY key);
void RemoveAll();

// iterating all (key, value) pairs
POSITION GetStartPosition() const;

const CPair *PGetFirstAssoc() const;
CPair *PGetFirstAssoc();

void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;

const CPair *PGetNextAssoc(const CPair *pAssocRet) const;
CPair *PGetNextAssoc(const CPair *pAssocRet);

// advanced features for derived classes
UINT GetHashTableSize() const;
void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);

// Implementation
protected:
CAssoc** m_pHashTable;
UINT m_nHashTableSize;
INT_PTR m_nCount;
CAssoc* m_pFreeList;
struct CPlex* m_pBlocks;
INT_PTR m_nBlockSize;

CAssoc* NewAssoc(ARG_KEY key);
void FreeAssoc(CAssoc*);
CAssoc* GetAssocAt(ARG_KEY, UINT&, UINT&) const;

public:
~CMap();
void Serialize(CArchive&);
#ifdef _DEBUG
void Dump(CDumpContext&) const;
void AssertValid() const;
#endif
};

其需要四个泛型参数 KEY, ARG_KEY, VALUE, ARG_VALUE,但是这四个参数到底有什么用呢?事实上从上面的定义中我们就可以发现,其用来进行计算的,都是 ARG_KEY,而不是 KEY,在 CPair 内才会存储 KEY

对于其实现来说,其内部是用结构体 CPair 来存储每个元素的,存储的就是我们的 key, valueCAssoc 继承自 CPair,增加了一个 Hash 值字段,已经指向下一个个元素的指针。

// Association
class CAssoc : public CPair
{
friend class CMap<KEY,ARG_KEY,VALUE,ARG_VALUE>;
CAssoc* pNext;
UINT nHashValue; // needed for efficient iteration
public:
CAssoc( ARG_KEY key ) : CPair( key ) {}
};

也就是说, Hash 链中存储的是一个个 CAssoc 元素。

当我们调用 [] 向 CMap 类存入元素的时候经过了什么过程呢。

[] 操作符

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
VALUE& CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
{
ASSERT_VALID(this);

UINT nHashBucket, nHashValue;
CAssoc* pAssoc;
if ((pAssoc = GetAssocAt(key, nHashBucket, nHashValue)) == NULL)
{
if (m_pHashTable == NULL)
InitHashTable(m_nHashTableSize);

ENSURE(m_pHashTable);
// it doesn't exist, add a new Association
pAssoc = NewAssoc(key);
pAssoc->nHashValue = nHashValue;
//'pAssoc->value' is a constructed object, nothing more

// put into hash table
pAssoc->pNext = m_pHashTable[nHashBucket];
m_pHashTable[nHashBucket] = pAssoc;
}
return pAssoc->value; // return new reference
}

其直接了解的在通过 ARG_KEY 在 Hash 表中进行查找出对应的元素,返回 VALUE。

GetAssocAt()

  1. 首先会根据 ARG_KEY 计算出 Hash 值。
  2. 然后得到 Hash 链。
  3. 然后在 Hash 链中遍历比较 key 的地址是否一致。
template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
typename CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHashBucket, UINT& nHashValue) const
// find association (or return NULL)
{
nHashValue = HashKey<ARG_KEY>(key);
nHashBucket = nHashValue % m_nHashTableSize;

if (m_pHashTable == NULL)
return NULL;

// see if it exists
CAssoc* pAssoc;
for (pAssoc = m_pHashTable[nHashBucket]; pAssoc != NULL; pAssoc = pAssoc->pNext)
{
if (pAssoc->nHashValue == nHashValue && CompareElements(&pAssoc->key, &key))
return pAssoc;
}
return NULL;
}

HashKey()

template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
// (algorithm copied from STL hash in xfunctional)
#pragma warning(suppress: 4302) // 'type cast' : truncation
#pragma warning(suppress: 4311) // pointer truncation
ldiv_t HashVal = ldiv((long)(ARG_KEY)key, 127773);
HashVal.rem = 16807 * HashVal.rem - 2836 * HashVal.quot;
if (HashVal.rem < 0)
HashVal.rem += 2147483647;
return ((UINT)HashVal.rem);
}

我们可以到,这个 Hash 值都是 UINT 类型的。可以看到,实现上会强制将 ARG_KEY 转换为一个

其默认有几个实现:

template<> AFX_INLINE UINT AFXAPI HashKey<__int64>(__int64 key)
{
// (algorithm copied from STL hash in xfunctional)
return (HashKey<DWORD>((DWORD)(key & 0xffffffffUL)) ^ HashKey<DWORD>((DWORD)(key >> 32)));
}

template<> UINT AFXAPI HashKey<LPCWSTR> (LPCWSTR key);
template<> UINT AFXAPI HashKey<LPCSTR> (LPCSTR key);
template<> UINT AFXAPI HashKey<CComBSTR> (CComBSTR key);
template<> UINT AFXAPI HashKey<const struct tagVARIANT&> (const struct tagVARIANT& var);

所以说,当我们用要 CMap 的时候,如果不指定的类型不是上面的几种,那么就会找不到对于的 HaskKey 方法,自然就会出错了。

同时由于我们需要用 ARG_KEY进行计算,但存储的是KEY,这个 KEY 与 ARG_KEY 应该是有关系的,比如说就是将 KEY 的一部分作为 ARG_KEY 来进行。因此,当我们用 CString 作为,KEY,而我们只能将 LPCWSTR, LPCSTR 作为ARG_KEY了,当我们进行调用的时候,会自动转换为 ARG_KEY了。

CString 实例

CMap<CString, LPCTSTR, CString, CString> map;
map[_T("a")] = _T("A");
map[_T("b")] = _T("B");
POSITION pos = map.GetStartPosition();
while (pos != NULL)
{
CString key, value;
map.GetNextAssoc(pos, key, value);
_tprintf_s(_T("%s %s\n"), key, value);

}