在刚刚接触数学函数的时候，应该都学过映射的概念。对于函数y = f(x)，就是一个x到y的映射，如图5.4左边的几组数据所示。
不用关心 x 和 y 的关系，这里要说明的是事物之间存在着许多的惟一性，即在定义域内对于 x 的任一取值，都有一个惟一的 y 值与它相对应。类似的情况在生活中更是举不胜举，巴黎对应着法国，纽约对应着美国，华盛顿对应着美国等。在程序中，这种关系也是存在的，比如想用窗口类CWnd来控制线程中的所有窗口，那么，线程中每一个窗口的窗口句柄都应该对应惟一的CWnd指针。在处理窗口发来的消息的时候，要通过窗口函数WndProc传来的窗口句柄的值得到此窗口对应的CWnd指针，然后用这个指针去调用CWnd类的接口成员。
这就要求封装一个类来保存有着映射关系的数据。如果是指针（pointer）到指针映射的话，就为这个类命名为CMapPtrToPtr，如果是指针到双字的映射的话，就为这个类命名为CMapPtrToWord等。它们之间除了类的名称和保存的数据类型不同外没有区别。
本节的目标主要是设计一个保存指针到指针映射的CMapPtrToPtr类。在此基础上。再封装一个管理Windows句柄到C++对象指针之间映射的类CHandleMap。
内存分配方式CMapPtrToPtr类保存的是若干个映射项的集合。每个映射项保存了一对映射关系，一个称为键（key），相当于数学中的 x，另一个称为值（value），相当于 y。为了将这些映射关系连在一起，还要在每个映射项中记录下下一个映射项的地址，所以可以用下面的CAssoc结构表示一对映射关系。
struct CAssoc
{
CAssoc* pNext;
void* key;
void* value;
};
此结构表示给定一个key，仅有一个value与它相对应。如果有多组这样一一对应的数据，就要在内存中分配多个具有CAssoc结构大小的空间来保存各成员的值。其中pNext成员将这些内存块都连在了一起，如图5.4右图所示。
按照这种链表的结构，假设用户要用CMapPtrToPtr类保存成千上万条中文和英文的对应数据，就要在内存中new上万个CAssoc结构，调用这上万个new函数的开销是多大？为了能够正确的销毁，new函数又要向每个CAssoc结构中添加额外的信息，这又会浪费多少内存？如此多大小相同的内存块不断地被分配、释放产生的结果是什么呢？内存碎片。
如果两个CAssoc占用的是不连续的内存空间，而且中间间隔的空间又恰好不足以容纳另一个CAssoc结构，就会有内存碎片产生。通常解决这个问题的比较好的方法是预先为CAssoc结构申请一块比较大的内存，当要为CAssoc结构分配空间的时候，并不真的申请新的空间，而是让它使用上面预留的空间，直到这块空间被使用完再申请新的空间。
写一个分配内存空间的全局函数，每一次调用此函数都可以获得一个指定大小的内存块来容纳多个CAssoc结构。另外，还必须要有一种机制将此函数申请的内存块记录下来，以便当CMapPtrToPtr类的对象销毁的时候释放所有内存空间。在每个内存块头部安排指向下一个内存块首地址的pNext指针就可以将所有内存块链接在一起了，这样做的结果是每一个内存块都由pNext指针和真正的用户数据组成，如图5.5所示。只需要记录下pHead指针就有办法释放所有内存空间了。
在每一块内存的头部增加的数据可以用CPlex结构来表示。当然了，此结构只有一个pNext成员，但是为了方便，把分配内存的全局函数以静态函数的形式封装到CPlex结构中，把释放内存链的函数也封装到其中。
** AFXPLEX.H**
#ifndef __AFXPLEX_H__
#define __AFXPLEX_H__
#include "_afxwin.h"
struct CPlex
{
CPlex* pNext; // 向每个内层块中添加的额外信息，指向下一个内存块首地址的指针
// 这里是真正的数据区，BYTE data[maxNum*elementSize];
void* data() { return this + 1; }
// 用于申请内存的全局函数。申请cbElement大小的空间nMax个
static CPlex* Create(CPlex*& pHead, UINT nMax, UINT cbElement);
// 释放以当前对象为首地址（this指针）的内存链中的所有内存
void FreeDataChain();
};
#endif // __AFXPLEX_H__
Create是最终的分配内存的全局函数，这个函数会将所分配的内存添加到以pHead为首地址的内存链中。参数pHead是用户提供的保存链中第一个内存块的首地址的指针。以后释放此链的内存时，直接使用“pHead->FreeDataChain()”语句即可。下面是这些函数的具体实现，应放在PLEX.CPP文件中。
PLEX.cpp
#include "_afxplex_.h"
CPlex* CPlex::Create(CPlex*& pHead, UINT nMax, UINT cbElement)
{
CPlex* p = (CPlex*)new BYTE[sizeof(CPlex) + nMax*cbElement];
// 将新增加的内存块添加到链中，并将其地址做为首地址
p->pNext = pHead;
pHead = p; // 以相反方向添加数据项的方式大大减化了程序设计
return p;
}
void CPlex::FreeDataChain()
{
// 以当前内存块的地址为首地址
CPlex* p = this;
// 释放链中所有内存块占用的内存
while(p != NULL)
{
BYTE* pBytes = (BYTE*)p;
CPlex* pNext = p->pNext;
delete[] pBytes;
p = pNext;
}
}
这种管理内存的方式很简单，也很实用。使用的时候除了调用CPlex::Create函数为小的结构申请大的内存空间以外，还要定义一个CPlex类型的指针用于记录整个链的首地址。下面的示例程序先用CPlex::Create函数申请了一大块内存，在使用完毕以后又通过CPlex指针将之释放，代码如下。
05CPlexDemo
// CPlexDemo.cpp文件
#include "_afxplex_.h" // 定义了CPlex结构
struct CMyData // 你没有必要去做这个练习，懂得它的工作机制就行了，
{ // CPlex结构的实际应用在后面的类中会被体现出来
int nSomeData;
int nSomeMoreData;
};
void main()
{
CPlex* pBlocks = NULL; // 用于保存链中第一个内存块的首地址，必须被初始化为NULL
CPlex::Create(pBlocks, 10, sizeof(CMyData));
CMyData* pData = (CMyData*)pBlocks->data();
// 现在pData是CPlex::Create函数申请的10个CMyData结构的首地址
//... // 使用pData指向的内存
// 使用完毕，继续申请
CPlex::Create(pBlocks, 10, sizeof(CMyData));
pData = (CMyData*)pBlocks->data();
// 最后释放链中的所有内存块
pBlocks->FreeDataChain();
}
Create函数是CPlex的静态成员，使用起来就相当于全局函数，所以上面的代码直接调用CPlex::Create函数来为CMyData结构申请一块大的空间，空间的首地址返回给pBlocks变量。最后的一条语句会释放掉前面CPlex::Create申请的全部空间。
设计管理方式为映射项分配内存空间
在实现CMapPtrToPtr类的时候就是依靠调用CPlex::Create函数来为CAssoc结构申请空间的。不管用哪一种机制管理内存，都得使CMapPtrToPtr类在添加新的关联的时候方便地得到容纳CAssoc结构的空间，在删除关联的时候方便地释放此CAssoc结构占用的空间，就像使用new和delete操作符一样方便。下面是为管理各个关联（CAssoc结构）占用的内存而设计的代码。
// _AFXCOLL.H文件
#ifndef __AFXCOLL_H__
#define __AFXCOLL_H__
#include "_afxwin.h"
#include "_afxplex_.h"
class CMapPtrToPtr
{
protected:
// 关联（Association）
struct CAssoc
{
CAssoc* pNext; // 指向下一个CAssoc结构
void* key; // 键对象
void* value; // 值对象
};
// 实现（Implementation）
protected:
struct CPlex* m_pBlocks; // 保存用CPlex::Create函数申请的内存块的首地址
int m_nBlockSize; // 指定每个内存块可以容纳多少个CAssoc结构
CAssoc* m_pFreeList; // 预留空间中没有被使用的CAssoc结构组成的链中第一个关联的指针
int m_nCount; // 记录了程序一共使用了多少个CAssoc结构，即关联的个数
// 为一个新的CAssoc结构提供空间，相当于使用new操作符
CAssoc* NewAssoc();
// 释放一个CAssoc结构占用的空间，相当于使用delete操作符
void FreeAssoc(CAssoc* pAssoc);
};
#endif // __AFXCOLL_H__
由于CAssoc结构只会被CMapPtrToPtr类使用，所以把它的定义放在了类中。NewAssoc函数负责在预留的空间中给CAssoc结构分配空间，如果预留的空间已经使用完了，它会调用CPlex::Create函数申请m_nBlockSize*sizeof(CAssoc)大小的内存块，代码如下。
// MAP_PP.CPP文件
CMapPtrToPtr::CAssoc* CMapPtrToPtr::NewAssoc()
{
// 预留的空间已经被使用完
if(m_pFreeList == NULL)
{
// 向m_pBlocks指向的链中添加一个新的内存块。m_nBlockSize的值可以由用户指定
CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CAssoc));
// 将新内存块中各CAssoc结构添加到m_pFreeList指向的链中（空闲链）
CAssoc* pAssoc = (CAssoc*)newBlock->data();
pAssoc += m_nBlockSize -1; // 注意，此时pAssoc指向内存块中最后一个CAssoc结构
for(int i = m_nBlockSize -1; i >= 0; i--, pAssoc--)
{
// 将pAssoc做为链的首地址添加到空闲链中（还是以相反的顺序向链中添加元素）
pAssoc->pNext = m_pFreeList;
m_pFreeList = pAssoc;
}
}
// 从空闲链中取出一个元素pAssoc
CAssoc* pAssoc = m_pFreeList;
m_pFreeList = m_pFreeList->pNext;
m_nCount++; // 又多使用了一个CAssoc结构
// 初始化新关联的值
pAssoc->key = 0;
pAssoc->value = 0;
return pAssoc;
}
void CMapPtrToPtr::FreeAssoc(CAssoc* pAssoc)
{
// 将要释放的关联做为链的首地址添加到空闲链中（以相反的顺序）
pAssoc->pNext = m_pFreeList;
m_pFreeList = pAssoc;
m_nCount--; // 释放了一个CAssoc结构
// 如果全部的关联都没被使用，就释放所有的内存空间，包括CPlex::Create函数申请的内存块
if(m_nCount == 0)
RemoveAll(); // 此函数会释放所有内存空间，待会儿我们再讨论
}
所有没有被使用的CAssoc结构连成了一个空闲链，成员m_pFreeList是这个链的头指针。这是CAssoc结构中pNext成员的一个重要应用。为CAssoc结构分配新的内存（NewAssoc）或释放CAssoc结构占用的内存（FreeAssoc）都是围绕m_pFreeList指向的空闲链进行的。类的构造函数会初始化m_pFreeList的值为NULL，所以在第一次调用NewAssoc函数的时候程序会申请新的内存块，此内存块的头部是一个CPlex结构，紧接着是可以容纳m_nBlockSize个CAssoc结构的空间，m_pBlocks成员保存的是内存块链的头指针，以后还要通过该成员调用FreeDataChain函数释放所有的内存块。申请新的内存块以后就要向空闲链中添加元素了。真正从空闲链中移去元素的过程是很简单的，同FreeAssoc函数向空闲链中添加元素的过程非常相似，都是要改变头指针m_pFreeList。
映射项的内存组织
为各映射项分配内存空间的方法已经讲完了，下面要关心的问题是如何设计各映射项的内存组织形式，以便能够快速的搜索它们。
CMapPtrToPtr类提供的基本功能是允许用户向映射中添加新的项，即一对key——value值，也要允许用户通过一个key值查询此值对应的value。假设用Lookup成员函数来完成查询功能。
// 在映射中查找key所对应的rValue BOOL Lookup(void* key, void*& rValue);
最坏的方法是挨个查找映射中的项。因为如果映射中包含n个项，就必须做将近n次单独的查找。最好的方法是不进行任何查找就能够直接得到用户要求的项，只要合理设置，这完全是可能的。
当映射被创建的时候，申请一个CAssoc指针类型的数组，并用成员函数m_pHashTable保存数组的首地址。
m_pHashTable = new CAssoc*[nHashSize]; // nHashSize的值由用户指定，我们用m_nHashTableSize保存次值
每当一个项被添加到映射中的时候，调用NewAssoc函数为新的CAssoc结构申请空间，并通过新项的key值计算得到一个哈希值（a hash value）nHashValue，新CAssoc结构的地址被拷贝到以nHash为索引的上面的数组成员中。nHash的值是通过下面的式子得到的。
nHash = nHashValue%m_nHashTableSize;
nHashValue是从key值计算得到的哈希值，m_nHashTableSize是m_pHashTable所指向的数组的大小。如果恰巧索引为nHash的元素包含一个CAssoc类型的指针，就创建一个CAssoc结构的链表，表中第一个CAssoc结构的地址被保存在数组中。图5.6显示了添加8个项以后数组可能的样子。在这个例子里，3个项被存储在单一的数组中，其他5个被分成了两个链表，它们的大小分别是2和3。
计算哈希值的原则是尽量使计算出来的值惟一，并且不太大。在CMapPtrToPtr类中安排一个成员函数HashKey来完成这项任务。
inline UINT CMapPtrToPtr::HashKey(void* key) const
{
return ((UINT)(void*)(DWORD)key)>>4;
}
下面是定义CMapPtrToPtr类的完整代码。
class CMapPtrToPtr
{
protected:
// 关联（Association）
struct CAssoc
{
CAssoc* pNext; // 指向下一个CAssoc结构
void* key; // 键对象
void* value; // 值对象
};
public:
// 构造函数（Construction）
CMapPtrToPtr(int nBlockSize = 10);
// 属性成员（Attributes）
// 元素的个数
int GetCount() const;
BOOL IsEmpty() const;
// 在映射中查找key所对应的rValue
BOOL Lookup(void* key, void*& rValue);
// 操作（Operations）
// 查找或者是添加key对应的value
void*& operator[](void* key);
// 添加一个新的（key, vaule）对
void SetAt(void* key, void* newValue);
// 移除一个存在的（key, ?）对
BOOL RemoveKey(void* key);
void RemoveAll();
UINT GetHashTableSize() const;
void InitHashTable(UINT nHashSize, BOOL bAllocNow = TRUE);
UINT HashKey(void* key) const;
// 实现（Implementation）
protected:
CAssoc** m_pHashTable;
int m_nHashTableSize;
struct CPlex* m_pBlocks; // 保存用CPlex::Create函数申请的内存块的首地址
int m_nBlockSize; // 指定每个内存块可以容纳多少个CAssoc结构
CAssoc* m_pFreeList; // 预留空间中没有被使用的CAssoc结构组成的链中第一个关联的指针
int m_nCount; // 记录了程序一共使用了多少个CAssoc结构，即关联的个数
// 为一个新的CAssoc结构提供空间，相当于使用new操作符
CAssoc* NewAssoc();
// 释放一个CAssoc结构占用的空间，相当于使用delete操作符
void FreeAssoc(CAssoc* pAssoc);
// 寻找键key所在的关联
CAssoc* GetAssocAt(void* key, UINT& nHash) const;
public:
~CMapPtrToPtr();
};
inline int CMapPtrToPtr::GetCount() const
{ return m_nCount; }
inline BOOL CMapPtrToPtr::IsEmpty() const
{ return m_nCount == 0; }
inline void CMapPtrToPtr::SetAt(void* key, void* newValue)
{ (*this)[key] = newValue; }
inline UINT CMapPtrToPtr::GetHashTableSize() const
{ return m_nHashTableSize; }
#endif // __AFXCOLL_H__
在向映射中添加任何项之前，要首先初始化哈希表（hash table），这项工作由InitHashTable函数来完成。
void CMapPtrToPtr::InitHashTable(UINT nHashSize, BOOL bAllocNow)
{
if(m_pHashTable != NULL)
{
// 释放计算表
delete[] m_pHashTable;
m_pHashTable = NULL;
}
if(bAllocNow)
{
// 为计算表申请空间
m_pHashTable = new CAssoc*[nHashSize];
memset(m_pHashTable, 0, sizeof(CAssoc*)*nHashSize);
}
m_nHashTableSize = nHashSize;
}
用户可以通过给bAllocNow参数传递FALSE，只改变m_nHashTableSize的值，而不申请空间。m_nHashTableSize的值在构造函数里被初始化为17。
GetAssocAt函数负责在全部存在的项中查找包含键key的项。
CMapPtrToPtr::CAssoc* CMapPtrToPtr::GetAssocAt(void* key, UINT& nHash) const
{
// 计算包含key的项在表中的位置
nHash = HashKey(key)%m_nHashTableSize;
if(m_pHashTable == NULL)
return NULL;
// 在以m_pHashTable[nHash]为头指针的链表中查找
CAssoc* pAssoc;
for(pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
{
if(pAssoc->key == key)
return pAssoc;
}
return NULL;
}
如果调用InitHashTable函数申请的哈希表（hash table）足够大的话，不同的key计算得到的nHash的值很可能就是惟一的，这样不需要查找就可以知道m_pHashTable[nHash]的值就是要查找的项的地址。这就是CMapPtrToPtr类能够实现快速查找的原因。
前面已经提到了Lookup函数，此函数的实现代码相当简单，仅仅是调用了GetAssocAt函数而已。
BOOL CMapPtrToPtr::Lookup(void* key, void*& rValue)
{
UINT nHash;
CAssoc* pAssoc = GetAssocAt(key, nHash);
if(pAssoc == NULL)
return FALSE; // 没有在映射中
rValue = pAssoc->value;
return TRUE;
}
最常用的接口函数是operator [ ]。这个函数重载了[ ]操作符，它的返回值是键key所对应vaule的引用，所以既可以使用这个函数设置键key对应的value，也可以使用这个函数取得键key对应的vaule。当用户传递的key不存在的时候，此函数还会创建新的关联。
void*& CMapPtrToPtr::operator [] (void* key)
{
UINT nHash;
CAssoc* pAssoc;
if((pAssoc = GetAssocAt(key, nHash)) == NULL)
{
if(m_pHashTable == NULL)
InitHashTable(m_nHashTableSize);
// 既然映射中没有用户指定的项，我们就添加一个新的关联
pAssoc = NewAssoc();
pAssoc->key = key;
// 将新的关联放入计算表中（放在表头，不是表尾）
pAssoc->pNext = m_pHashTable[nHash];
m_pHashTable[nHash] = pAssoc;
}
return pAssoc->value; // 返回value的引用
}
现在只剩下从映射中移除项的功能没有实现了。移除指定的项需要先查找，然后从链表中移除，再释放内存。下面是RemoveKey函数的实现代码。
BOOL CMapPtrToPtr::RemoveKey(void* key)
{
if(m_pHashTable == NULL)
return FALSE; // 表中什么也没有
CAssoc** ppAssocPre; // 记录要删除的项的地址的变量的地址（如果存在的话，我们会改变此地址处的值）
ppAssocPre = &m_pHashTable[HashKey(key)%m_nHashTableSize];
CAssoc* pAssoc;
for(pAssoc = *ppAssocPre; pAssoc != NULL; pAssoc = pAssoc->pNext)
{
if(pAssoc->key == key)
{
// 移除pAssoc指向的项
*ppAssocPre = pAssoc->pNext; // 从表中移除
FreeAssoc(pAssoc); // 释放内存
return TRUE;
}
ppAssocPre = &pAssoc->pNext;
}
return FALSE; // 没有找到
}
下面是类的构造函数、析构函数和释放内存的函数使用的代码。
CMapPtrToPtr::CMapPtrToPtr(int nBlockSize)
{
m_pHashTable = NULL;
m_nHashTableSize = 17; // 默认大小
m_pBlocks = NULL;
m_nBlockSize = nBlockSize;
m_pFreeList = NULL;
m_nCount = 0;
}
CMapPtrToPtr::~CMapPtrToPtr()
{
RemoveAll();
}
void CMapPtrToPtr::RemoveAll()
{
if(m_pHashTable != NULL)
{
// 释放计算表
delete[] m_pHashTable;
m_pHashTable = NULL;
}
m_nCount = 0;
m_pFreeList = NULL;
m_pBlocks->FreeDataChain();
m_pBlocks = NULL;
}
CMapPtrToPtr类应用举例
为了示范映射的使用方法，下面用CMapPtrToPtr类建造了一个简单的English-Chinese字典，这个字典里面包含一周内每天的名称。
// MapsDemo.cpp文件 #include#include "_afxcoll.h" // 定义了CPlex结构 using namespace std; void main() // English-Chinese 字典 { CMapPtrToPtr map; char szDay[][16] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" }; // 向映射中添加项 map[szDay[0]] = "星期日"; // 这里主要调用了operator [ ]函数 map[szDay[1]] = "星期一"; map[szDay[2]] = "星期二"; map[szDay[3]] = "星期三"; map[szDay[4]] = "星期四"; map[szDay[5]] = "星期五"; map[szDay[6]] = "星期六"; // 查询 cout << szDay[4] << " : " << (char*)map[szDay[4]] << "n"; }
可以看到，使用CMapPtrToPtr类就像使用数组一样方便。map对象保存了每对字符串的首地址，这里面的键（key）是英文单词的首地址，值（value）是中文单词的首地址。查询的时候，只要给出key，立刻便得出value。运行结果如图5.7所示。
