CMap成员变量和成员函数难点详细解释

本文主要是针对CMap中的成员变量：

CAssoc** m_pHashTable;
UINT m_nHashTableSize;
int m_nCount;
CAssoc* m_pFreeList;
struct CPlex* m_pBlocks;
int m_nBlockSize;

进行解释，以及如何存放。

还有就是对成员函数：

CAssoc* NewAssoc();
void FreeAssoc(CAssoc*);

VALUE& operator[](ARG_KEY key);

的实现进行说明。

先看看MFC CMap类路径：

C:/Program Files/Microsoft Visual Studio/VC98/MFC/Include/AFXTEMPL.H

部分源码：

/////////////////////////////////////////////////////////////////////////////
// CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
class CMap : public CObject
{
protected:
	// Association
	struct CAssoc
	{
		CAssoc* pNext;
		UINT nHashValue;  // needed for efficient iteration
		KEY key;
		VALUE value;
	};
public:
// Construction
	CMap(int nBlockSize = 10);

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

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

// 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;
	void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;

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

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

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

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



template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
{
	if (m_pFreeList == NULL)
	{
		// add another block
		CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMap::CAssoc));
		// chain them into free list
		CMap::CAssoc* pAssoc = (CMap::CAssoc*) newBlock->data();
		// free in reverse order to make it easier to debug
		pAssoc += m_nBlockSize - 1;
		for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
		{
			pAssoc->pNext = m_pFreeList;
			m_pFreeList = pAssoc;
		}
	}
	ASSERT(m_pFreeList != NULL);  // we must have something

	CMap::CAssoc* pAssoc = m_pFreeList;
	m_pFreeList = m_pFreeList->pNext;
	m_nCount++;
	ASSERT(m_nCount > 0);  // make sure we don't overflow
	ConstructElements<KEY>(&pAssoc->key, 1);
	ConstructElements<VALUE>(&pAssoc->value, 1);   // special construct values
	return pAssoc;
}

template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CMap::CAssoc* pAssoc)
{
	DestructElements<VALUE>(&pAssoc->value, 1);
	DestructElements<KEY>(&pAssoc->key, 1);
	pAssoc->pNext = m_pFreeList;
	m_pFreeList = pAssoc;
	m_nCount--;
	ASSERT(m_nCount >= 0);  // make sure we don't underflow

	// if no more elements, cleanup completely
	if (m_nCount == 0)
		RemoveAll();
}



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 nHash;
	CAssoc* pAssoc;
	if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
	{
		if (m_pHashTable == NULL)
			InitHashTable(m_nHashTableSize);

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

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

1.当把元素插入到哈希表中的时候，调用SetAt(ARG_KEY key, ARG_VALUE newValue)，然后重载运算符[]，来到：

 if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
 {
  if (m_pHashTable == NULL)
   InitHashTable(m_nHashTableSize);

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

  // put into hash table
  pAssoc->pNext = m_pHashTable[nHash];
  m_pHashTable[nHash] = pAssoc;
 }

pAssoc = NewAssoc()调用后，来到关键的一句：

if (m_pFreeList == NULL)的判断，m_pFreeList 成员变量，在初始化的时候是为空，在分析它之前，先解释一下那3个成员变量：

// m_pFreeList后面再作解释

CAssoc* m_pFreeList;

// 每一个m_pBlocks就是在内存中m_nBlockSize ＝ 10个用来存放数据的内存结构，相当于一个盒子，可以装下10个插入的数据
struct CPlex* m_pBlocks;
int m_nBlockSize;

首先说一下struct CPlex：

struct CPlex     // warning variable length structure
{
	CPlex* pNext;
#if (_AFX_PACKING >= 8)
	DWORD dwReserved[1];    // align on 8 byte boundary
#endif
	// BYTE data[maxNum*elementSize];

	void* data() { return this+1; }

	static CPlex* PASCAL Create(CPlex*& head, UINT nMax, UINT cbElement);
			// like 'calloc' but no zero fill
			// may throw memory exceptions

	void FreeDataChain();       // free this one and links
};

CPlex* PASCAL CPlex::Create(CPlex*& pHead, UINT nMax, UINT cbElement)
{
	ASSERT(nMax > 0 && cbElement > 0);
	CPlex* p = (CPlex*) new BYTE[sizeof(CPlex) + nMax * cbElement];
			// may throw exception
	p->pNext = pHead;
	pHead = p;  // change head (adds in reverse order for simplicity)
	return p;
}

void CPlex::FreeDataChain()     // free this one and links
{
	CPlex* p = this;
	while (p != NULL)
	{
		BYTE* bytes = (BYTE*) p;
		CPlex* pNext = p->pNext;
		delete[] bytes;
		p = pNext;
	}
}

Plex，在中文意思是丛，簇的意思，

它只有一个成员变量指针：CPlex* pNext，

在每次调用Create函数后，内存中就会分配m_nBlockSize ＝10（10为nBlockSize在构造函数中默认分配的大小）个单位的空间大小，每一个m_nBlockSize的大小是cbElement，再加上存放结构CPlex的大小，一共是：

sizeof(CPlex) + nMax * cbElement;

因此，每次一个Create后，内存就会分配10个位置的空间用来存放将要插入的数据，也就是一个“丛”，在插入完10个数据后，也就是第一个“丛”已经装满了，这时，又新建一个“丛”，这时候，第一个“丛”的指针CPlex* pNext就会指向下一个“丛”，从而可以实现每一次动态地分配10个单位数据，用来存放插入的数据（但是这时数据还没有插入，只是开辟一片空间，准备用来存放数据），也就是一个“丛”，这些“丛”都组成又一个链表。

好，这时候就可以说说m_pFreeList，在新建一个“丛”，也就是调用Create后，

CMap::CAssoc* pAssoc = (CMap::CAssoc*) newBlock->data();

新建一个CAssoc对象pAssoc （也就是要插入的那个元素），放到刚刚新建好的那个“丛”的第一个位置去（每个“丛”有m_nBlockSize ＝10个位置嘛，前面说了），newBlock->data() 是返回this+1，为什么是+1？因为this是CPlex对象中存放pNext指针的位置，指针后面就是10个单位，+1后就指向了10个单位的第一个位置。

这时候，

pAssoc += m_nBlockSize - 1;

把刚刚新建的CAssoc对象移动到“丛”的最后一个位后，这时候m_pFreeList从后面指回到第一个位置上。

如图：

0______ ->“丛”的第一个位置存放指针

1______ ->“丛”的第二个开始存放数据1，m_pFreeList指向这里

2______m_pFreeList

3______ ｜

4______ V

5______ 会

6______ 向

7______ 下

8______ 移

9______ 动

10______

随着数据的插入，m_pFreeList会一直向下移动，

在第一个“丛”放满数据后，m_pFreeList会变成NULL，这时候再新建一个“丛”，第一个“丛的指针pNext指向下一个“丛”：

0______ ->“丛”的第一个位置存放指针

1______ ->“丛”的第二个开始存放数据1，m_pFreeList指向这里

2______

3______

4______

5______

6______

7______

8______

9______

10______

这就是数据在插入和存放的过程.

2.在调用FreeAssoc(CMap::CAssoc* pAssoc)进行删除一个数据后，m_pFreeList会指向删除的位置，面删除的位置会指向m_pFreeList原来的位置，这样一来，在删除数据后，所留下的空间会在以后插入数据的时候填充掉，这样可以有效地防止空间的浪费。

pAssoc->pNext = m_pFreeList;
m_pFreeList = pAssoc;

至于数据的Map中的结构，这就不多说了，也就是一个哈希表的结构！

花了2小时，终于完成，小弟第一次100%原创发表，里面可以有很多不足之处，希望大家多多指点！！也希望大家多多支持，学习学习！！！

转帖请注明：n70joey原创于csdn.net！！！！

2010-03-23