映射表類(lèi)（CMap）是MFC集合類(lèi)中的一個(gè)模板類(lèi)，也稱(chēng)作為“字典”，就像一種只有兩列的表格，一列是關(guān)鍵字，一列是數(shù)據(jù)項(xiàng)，它們是一一對(duì)應(yīng)的。關(guān)鍵字是唯一的，給出一個(gè)關(guān)鍵字，映射表類(lèi)會(huì)很快找到對(duì)應(yīng)的數(shù)據(jù)項(xiàng)。映射表的查找是以哈希表的方式進(jìn)行的，因此在映射表中查找數(shù)值項(xiàng)的速度很快。映射類(lèi)最適用于需要根據(jù)關(guān)鍵字進(jìn)行快速檢索的場(chǎng)合，我們的程序中就用映射表來(lái)保存計(jì)時(shí)器標(biāo)志值和類(lèi)實(shí)例指針，用計(jì)時(shí)器的標(biāo)志值作為關(guān)鍵字。
他這個(gè)有點(diǎn)像數(shù)組，比如你要查找a[index]，不必先遍歷前面的index個(gè)元素，只不過(guò)數(shù)組的下標(biāo)是哈希表鍵值，它是以鍵值對(duì)的形式出現(xiàn)的。舉個(gè)例子來(lái)說(shuō)吧，公司的所有職員都有一個(gè)工號(hào)和自己的姓名，工號(hào)就是姓名的關(guān)鍵字，給出一個(gè)工號(hào)，就可以很快的找到相應(yīng)的姓名。
舉例如下：
1、定義一個(gè)CMAP，向這個(gè)CMAP中增加數(shù)據(jù)項(xiàng)（鍵-值對(duì)）。
CMap<CString, LPCTSTR, CString, LPCTSTR>m_ItemMap;
CString strKey = _T(""), str = _T("");
int i;
for(i = 0; i < 5; i++)
{
strKey.Format("%d", i); //這個(gè)是鍵
str.Format("A%d", i); //鍵對(duì)應(yīng)的值
m_ItemMap.SetAt(strKey, str);
}
2、遍歷正個(gè)CMAP的常用方法。
POSITION pos = m_ItemMap.GetStartPosition();
while(pos)
{
m_ItemMap.GetNextAssoc(pos, strKey, str);
cout<< strKey<< ":"<< str<< endl;
}
3、在CMAP中查找相應(yīng)的數(shù)據(jù)項(xiàng)。
CString pReset;
if(m_ItemMap.Lookup("1", pReset))
{
cout<<pReset<<endl;
}
=======================================================================現(xiàn)在，我們來(lái)學(xué)習(xí)MFC中，最常用的數(shù)據(jù)結(jié)構(gòu)中的最后一個(gè)CMap模板。之前，我們已經(jīng)依次學(xué)完了CArray，CList，并且也對(duì)它們進(jìn)行了初步的剖析。
其實(shí)，我一直認(rèn)為CMap是最簡(jiǎn)單的一個(gè)數(shù)據(jù)類(lèi)型，如果說(shuō)，大家對(duì)這個(gè)數(shù)據(jù)類(lèi)型產(chǎn)生不良感覺(jué)的話，大多是因?yàn)閷?duì)Hash表的陌生。
顯然，CMap就是對(duì)Hash表的一種實(shí)現(xiàn)。對(duì)于Hash表來(lái)說(shuō)，我們需要提供成對(duì)的Key與Value進(jìn)行操作，其實(shí)，也就是將我們?nèi)粘Ｊ褂玫臄?shù)組下標(biāo)替換成現(xiàn)在Key，至于MFC是采用了什么樣的散列函數(shù)，我們不必知道。
Hash表可以認(rèn)為是數(shù)組的一種優(yōu)化，或者說(shuō)是對(duì)數(shù)組缺陷的一種彌補(bǔ)，因?yàn)槲覀冎?，?shù)組在具備了高效存取性能的同時(shí)，無(wú)法動(dòng)態(tài)的調(diào)整自身的大小，又嚴(yán)重的影響了它的使用效果。這給了Hash表可乘之機(jī)，Hash表總是使用了某種算法盡可能的來(lái)達(dá)到將成對(duì)的元素存儲(chǔ)到一個(gè)額定的離散的內(nèi)存空間，它既繼承了鏈表對(duì)自身的動(dòng)態(tài)調(diào)整，又盡可能的使讀寫(xiě)維持在高速的水平，當(dāng)然無(wú)論如何還是要比數(shù)組慢的多。
如果你非要讓我告訴你，Hash表是什么樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)的話，很遺憾，我無(wú)法準(zhǔn)確的描述，這就相當(dāng)于你問(wèn)我“鳳凰是什么樣子”，不過(guò)我可以告訴你孔雀的樣子。常用的Hash表非常像一個(gè)十字?jǐn)?shù)組，似乎十字?jǐn)?shù)組又成為了眾多讀者的障礙，如果你暫時(shí)還不能理解的話，請(qǐng)你去翻閱Hash表的詳細(xì)論述，當(dāng)然你也可以在不久之后，在本處看到這些經(jīng)典數(shù)據(jù)結(jié)構(gòu)的精講。
現(xiàn)在，我們來(lái)看一個(gè)CMap的用法，至于它的參數(shù)，你可以看本空間一篇專(zhuān)門(mén)描述CArray，CList以及CMap參數(shù)用法的文章《CArray，CList，CMap如何實(shí)化（實(shí)例化）》。下面是我自己編寫(xiě)的例子：
class Point
{
public:
Point()
{
m_x = 0;
m_y = 0;
}
Point(int x, int y)
{
m_x = x;
m_y = y;
}
public:
int m_x;
int m_y;
};
typedef CMap<const char*, const char*, Point, Point&> CMapPnt; //請(qǐng)?jiān)谑褂弥岸x
int main()
{
Point elem1(1, 100), elem2(2, 200), elem3(3, 300), point;
CMapPnt mp;
// insert 3 elements into map， #1
mp.SetAt("1st", elem1);
mp.SetAt("2nd", elem2);
mp.SetAt("3th", elem3);
// search a point named "2nd" from map #2
mp.Lookup("2nd", point);
printf("2nd: m_x: %d, m_y: %d\n", point.m_x, point.m_y);
// insert a new pair into map #3
Point elem4(4, 400);
mp["4th"] = elem4;
cout<<"count: "<<mp.GetCount()<<endl;
// traverse the entire map #4
size_t index = 0;
const char* pszKey;
POSITION ps = mp.GetStartPosition();
while( ps )
{
mp.GetNextAssoc(ps, pszKey, point);
printf("index: %d, m_x: %d, m_y: %d\n", ++index, point.m_x, point.m_y);
}
return 0;
}
代碼中，我已經(jīng)給出了一些注釋?zhuān)彝瑯咏ㄗh讀者們，用英文在代碼中注釋?zhuān)@樣的好處實(shí)在是太多了。尤其在代碼需要在不同編碼的操作系統(tǒng)上調(diào)試的時(shí)候。
對(duì)于CMap這個(gè)類(lèi)，我不得不著重啰嗦一下的是：遍歷操作以及取下標(biāo)【】操作，當(dāng)然還有那個(gè)令很多人困惑不已的ARG_KEY到底應(yīng)該如何選擇的問(wèn)題。
遍歷，看注釋#4，至于POSITION的含義，請(qǐng)?jiān)诒究臻g，查看其它文章。先使用GetStartPosition()函數(shù)獲得表頭的位置，然后，我們可以使用GetNextAssoc函數(shù)來(lái)遍歷。GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue)函數(shù)的參數(shù)值得說(shuō)明一下，大家看到，3個(gè)參數(shù)都是引用，而第一個(gè)是rNextPosition，顧名思義，在函數(shù)返回之后，它將會(huì)指像下一個(gè)元組，當(dāng)然這是在表還未遍歷完的時(shí)候，否則，它將被置為空（NULL）。
【】，利用下標(biāo)取元素的這個(gè)操作符，在CMap中被重載，用來(lái)返回指定Key值數(shù)據(jù)的引用，不過(guò)在注釋#3處，對(duì)于先取"4th"這個(gè)Point的引用然后賦值的用法，看起來(lái)，似乎有點(diǎn)聰明過(guò)了頭，因?yàn)樵谶@之前，我們還沒(méi)有插入"4th"所對(duì)應(yīng)的元組，但是，程序卻能正常的運(yùn)行！為什么？其實(shí)，這樣的用法是十分正確的，因?yàn)镃Map畢竟不是數(shù)組，它是沒(méi)有邊界的，當(dāng)CMap在獲得一個(gè)它無(wú)法查詢到的Key值的時(shí)候，它會(huì)將這個(gè)Key以及一個(gè)空的數(shù)據(jù)類(lèi)型追加到Hash表中去，從而保證了上面的程序可以無(wú)誤的運(yùn)行。
我們已經(jīng)說(shuō)過(guò)，ARG_KEY是作為類(lèi)型參數(shù)傳入CMap的，但并不是任何類(lèi)型都可以作為ARG_KEY傳入的。為什么？看樣子，這次不得不簡(jiǎn)單的說(shuō)說(shuō)Hash表的散列函數(shù)了。每個(gè)Hash表，總會(huì)使用一些散列函數(shù)，用來(lái)查找Key所對(duì)應(yīng)的Value，理想狀態(tài)下，我們當(dāng)然希望Hash表，就是一個(gè)數(shù)組，雖然這不可能，不過(guò)這樣理解，可以幫助我們更好的理解Hash表的物理結(jié)構(gòu)，就讓我們暫時(shí)把它看成一個(gè)數(shù)組吧。數(shù)組總是使用下標(biāo)來(lái)直接獲取元素的存儲(chǔ)地址，而下標(biāo)，顯然應(yīng)該是個(gè)非負(fù)整數(shù)，從而Hash表，也應(yīng)該具備這樣的特性，至少必須存在某種算法可以使傳入的Key可以直接的轉(zhuǎn)化為一個(gè)非負(fù)的整數(shù)，這也就是ARG_KEY的選擇標(biāo)準(zhǔn)。從而對(duì)象、引用無(wú)論如何都不應(yīng)該作為ARG_KEY成為CMap的類(lèi)型參數(shù)，而int、unsigned int、指針以及地址就成為了ARG_KEY的常用類(lèi)型參數(shù)，其實(shí)也就是那些類(lèi)似于整型的數(shù)據(jù)類(lèi)型。常?？吹揭恍┤嗽谟肅Map的時(shí)候，試圖使用CString作為CMap中ARG_KEY的類(lèi)型參數(shù)，這是應(yīng)該被糾正的方向性錯(cuò)誤，但有些人似乎會(huì)理直氣壯的反駁我，因?yàn)樗麄儼l(fā)現(xiàn)類(lèi)型參數(shù)KEY是可以使用CString的，這很奇怪嗎？我說(shuō)過(guò)KEY不能使用CString嗎？之所以KEY可以使用CString而ARG_KEY卻用的是LPCTSTR，那是因?yàn)镃String重載了operator==(const char*)這個(gè)判等操作符，當(dāng)CMap從Hash表中獲得KEY之后，它會(huì)將ARG_KEY與KEY直接相比較。真正存于CMap內(nèi)部的是KEY，也就是CString。這也就是為什么，我們經(jīng)常會(huì)看到CMap被實(shí)化成CMap<CString, LPCTSTR/*相當(dāng)于const char*，非Unicode情況下*/, CString，CString&>這樣的一個(gè)四不像實(shí)化類(lèi)的原因，至于CMap的效率優(yōu)化問(wèn)題，我們會(huì)在以后的文章中繼續(xù)與大家探討。
CMap的確是個(gè)很不錯(cuò)的數(shù)據(jù)結(jié)構(gòu)，尤其在你建立一個(gè)字典的時(shí)候。比如idealsoft的含義是"曳光科技"，這就是一個(gè)元組，也就是一個(gè)Pair，Key是"idealsoft"，而Value是"曳光科技"。
====================================================================
#include <afxwin.h>
#include <afxtempl.h>
void main()
{
AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0);
CMap <int, int, CString, CString> m_cMap;
m_cMap.SetAt(9923033, "張三 ");
m_cMap.SetAt(9826033, "張A ");
m_cMap.SetAt(9923063, "張B ");
m_cMap.SetAt(9923093, "張C ");
CString strName;
m_cMap.Lookup(9923063, strName);
AfxMessageBox(strName);
}