MFC - 什麼是 CMap?
Microsoft的公司在MFC中提供的類別CList，在資列結構中就是串列，如果以手工製造串列，加入、刪除，存取，動態配置記憶體加上指標，會有點複雜，學生時代也曾被搞得昏天暗地，一不小心還會產生Memory Leak，電腦怎麼死的都還覺得莫名奇妙。在MFC中提供這個類別，可大大提升效率。還是要提醒，如果你是初入門本科系學生，別投機取巧，還是腳踏實地的「昏天暗地」，這樣才能了解其中的訣竅，那天希望效能更高的時候，要手工打造的時候，才不會手足無措。
有雜湊函數都有如下一個基本特性：如果兩個雜湊值是不相同的（根據同一函式），那麼這兩個雜湊值的原始輸入也是不相同的。這個特性是雜湊函數具有確定性的結果。但另一方面，雜湊函數的輸入和輸出不是唯一對應關係的，如果兩個雜湊值相同，兩個輸入值很可能是相同的。但也可能不同，這種情況稱為「雜湊碰撞」，這通常是兩個不同長度的雜湊值，刻意計算出相同的輸出值。輸入一些資料計算出雜湊值，然後部分改變輸入值，一個具有強混淆特性的雜湊函數會產生一個完全不同的雜湊值。
典型的雜湊函數都有無限定義域，比如任意長度的位元組字串，和有限的值域，比如固定長度的位元串。在某些情況下，雜湊函數可以設計成具有相同大小的定義域和值域間的一一對應。一一對應的雜湊函數也稱為排列。可逆性可以透過使用一系列的對於輸入值的可逆「混合」運算而得到。
引用字afxtempl.h部份程式
template<class TYPE, class ARG_TYPE>
BOOL AFXAPI CompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2)
{
ENSURE(pElement1 != NULL && pElement2 != NULL);
ASSERT(AfxIsValidAddress(pElement1, sizeof(TYPE), FALSE));
ASSERT(AfxIsValidAddress(pElement2, sizeof(ARG_TYPE), FALSE));
return *pElement1 == *pElement2;
}
template<class ARG_KEY>
AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
{
// (algorithm copied from STL hash in xfunctional)
ldiv_t HashVal = ldiv((long)(ARG_KEY)key, 127773);
//覆蓋掉原來的餘數
//HashVal.rem=16807*原來的餘數-2836*原來的商
HashVal.rem = 16807 * HashVal.rem - 2836 * HashVal.quot;
//如果計算結果小於0
if (HashVal.rem < 0)
//再一次覆蓋掉餘數
//HashVal.rem=第一次覆蓋的餘數+2147483647
HashVal.rem += 2147483647;
//返回餘數
return ((UINT)HashVal.rem);
}
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)));
}
雜湊表雜湊函數的幾乎不可能/不切實際的理想是把每個關鍵字對映到唯一的索引上（參考完美雜湊），因為這樣能夠保證直接存取表中的每一個資料。
一個好的雜湊函數（包括大多數加密雜湊函數）具有均勻的真正隨機輸出，因而平均只需要一兩次探測（依賴於裝填因子）就能找到標的。同樣重要的是，隨機雜湊函數不太會出現非常高的衝突率。但是，少量的可以估計的衝突在實際狀況下是不可避免的（參考生日悖論或鴿洞原理）。
CMap是一種類似字典Collection的類別，利用單一鍵值來映射儲存的變數值，說明如下：
Template < classKEY,class ARG_KEY,class VALUE ,class ARG_VALUE >Class CMap:Public CObject
前面的部份是類別樣板(class template)，透過這個功能達到型態的變化，中間的部份則是型態引數，最後則是說明繼承(inherit)那個類別，CMap是繼承CObject。
參數說明：
KEY：這物件類別試用當做鍵值映射用。
ARG_KEY：鍵值資料型，參考KEY資料型態。
VALUE：儲存在Map的物件類別。
ARG_MAP：儲存參數的資料型態，參考VALUE的資料型態。
補充說明：
你已經插入一組(key,value)到Map中，你可以很有效率的依據鍵值(key)來擷取、刪除這組資料，你也可以透過指標(iterate)來巡視(指向)在儲存Map中的所有元素。
你可以使用POSITION型態的變數，來指向Map中資料位置，也可以記錄資料位置，並且可以利用這個紀錄的資料，指向Map中的該筆資料。或許你會認為指向這筆資料是透過鍵值來排序達成，事實上不是的，擷取資料的排序是沒有固定的順序的。
CMap變更CObject::Serialize的函式，支援序列化及元素的大量資料存取(dumping)，如果Map儲存的模式是採用Serialize，Map中的每一個元素依序列化(Serialized in turn )排序，SerializeElements是預設的執行方式，透過該函式資料會以位元(Bit)長度模式寫入(目前僅依字面意義翻譯，須查證實際情況來印證想像)。
如果你需要檢視Map中個別元素資料內容(key,value)，你必須設定檢視資料的長度，檢視資料長度至少為1或更多。
當一個CMap的物件被刪除時，或是元素被移除，則key及value整組資料都會被移除。
CMap Members：
建構子
|
CMap |
建構一個Collection，可以讓鍵值去映射到儲存值 |
Operations：
|
GetHashTableSize |
返回雜湊表(Hash Table，元素的個數)大小。 |
|
GetNextAssoc |
取得目前指標的下一個元素。 |
|
PGetNextAssoc |
取得目前指標的下一個元素指標(address)。 |
|
GetStartPosition |
取得第一個元素的位置(POSITION)。 |
|
PGetFirstAssoc |
取得第一個元素的指標(address)。 |
|
InitHashTable |
初始化雜湊表(Hash Table)，並指定大小。 |
|
Lookup |
尋找儲存值對應的鍵值 |
|
PLookup |
指向儲存值吻合指定值的鍵值的指標。 |
|
Operator[] |
插入元素到Map-這個操作子可以替代SetAt的功能函式。 |
|
RemoveAll |
移除Map中的所有元素。 |
|
RemoveKey |
移除指定鍵值的元素。 |
|
SetAt |
插入元素至Map；如果有發現相同的鍵值，則會取代原來的元素。 |
Status：
|
GetCount |
返回串列元素的個數。 |
|
GetSize |
返回串列元素的個數。 |
|
IsEmpty |
測試串列是否為無任何元素狀態。 |
Data Members：
|
CMap::CPair |
巢狀結構包含鍵值(Key)和相關物件的儲存值。 |
標頭檔：
afxtempl.h
範例：
// MFC_CMap.cpp : 定義主控台應用程式的進入點。
//
#include "stdafx.h"
#include <iostream>
#include <afxtempl.h>
//-----------------------------------------------------------
//要使用CList一定要將afxtempl.h包含進來，
//並且專案屬性中的「MFC的使用」也要設定
#include <afxtempl.h>
//-----------------------------------------------------------
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
CList<int,int&> CL_Int_Data;
int Int_Temp,Int_Loop1;
POSITION Pos_Temp;
//-----------------------------------------------------------
cout<<"驗證 IsEmpty、GetCount、GetSize"<<endl;
//IsEmpty：檢測是否為空串列
Int_Temp=CL_Int_Data.IsEmpty();
if(Int_Temp==1)
{
cout<<"目前是空的串列"<<endl;
}
//-----------------------------------------------------------
//GetCount：檢測目前串列大小
Int_Temp=CL_Int_Data.GetCount();
cout<<"目前串列所含元素數目(GetCount)："<<Int_Temp<<endl;
//GetSize：檢測目前串列大小
Int_Temp=CL_Int_Data.GetSize();
cout<<"目前串列所含元素數目(GetSize)："<<Int_Temp<<endl;
cout<<endl<<endl;
//-----------------------------------------------------------
cout<<"驗證 AddHead、AddTail"<<endl;
//AddHead：往頭的方向加入新元素
Int_Temp=1;
CL_Int_Data.AddHead(Int_Temp);
Int_Temp=2;
CL_Int_Data.AddHead(Int_Temp);
//AddTail：往尾的方向加入新元素
Int_Temp=-1;
CL_Int_Data.AddTail(Int_Temp);
Int_Temp=-2;
CL_Int_Data.AddTail(Int_Temp);
//GetHead：取出開頭位置的內容
Int_Temp=CL_Int_Data.GetHead();
cout<<"目前頭的位置內容值(GetHead)(2,1.-1,-2)： "<<Int_Temp<<endl;
//GetTail：取出結尾位置的內容
Int_Temp=CL_Int_Data.GetTail();
cout<<"目前頭的位置內容值(GetHead)(2,1.-1,-2)： "<<Int_Temp<<endl;
//IsEmpty：檢測是否為空串列
Int_Temp=CL_Int_Data.IsEmpty();
if(Int_Temp==1)
{
cout<<"目前是空的串列"<<endl;
}
else
{
cout<<"目前不是空串列"<<endl;
}
//GetCount：檢測目前串列大小
Int_Temp=CL_Int_Data.GetCount();
cout<<"目前串列所含元素數目(GetCount)："<<Int_Temp<<endl;
//GetSize：檢測目前串列大小
Int_Temp=CL_Int_Data.GetSize();
cout<<"目前串列所含元素數目(GetSize)："<<Int_Temp<<endl;
cout<<endl<<endl;
//-----------------------------------------------------------
cout<<"驗證 GetHeadPosition、GetNext、GetPrev、GetTailPosition"<<endl;
cout<<"驗證 GetAt、RemoveAt、SetAt"<<endl;
//GetHeadPosition：取出串列開頭位置(POSITION)
Pos_Temp=CL_Int_Data.GetHeadPosition ();
cout<<"目前開頭位置(POSITION)的內容(GetHeadPosition、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
//GetNext(POSTION)：以現在位置(括號內的POSITION變數)往下一個位置移動
CL_Int_Data.GetNext(Pos_Temp);
cout<<"目前開頭位置(POSITION)移動到下一個位置的元素內容(GetNext、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
CL_Int_Data.GetNext(Pos_Temp);
cout<<"目前位置(POSITION)移動到下一個位置的元素內容(GetNext、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
//GetPrev(POSITION)：以現在位置(括號內的POSITION變數)往前一個位置移動
CL_Int_Data.GetPrev (Pos_Temp);
cout<<"目前位置(POSITION)移動到前一個位置的元素內容(GetPrev、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
//GetTailPosition：取出串列結尾位置(POSITION)
Pos_Temp=CL_Int_Data.GetTailPosition ();
cout<<"目前結尾位置(POSITION)的內容(GetTailPosition、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
//RemoveAt(POSITION)：移除本位置元素
CL_Int_Data.RemoveAt (Pos_Temp);
Pos_Temp=CL_Int_Data.GetTailPosition ();
cout<<"移除原結尾元素，目前結尾位置(POSITION)的內容(RemoveAt、GetTailPosition、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
//SetAt(POSITION)：設定本位置元素
Int_Temp=100;
CL_Int_Data.SetAt (Pos_Temp,Int_Temp);
cout<<"設定目前位置(POSITION)的內容(SetAt、GetAt)："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
cout<<endl<<endl;
//-----------------------------------------------------------
cout<<"驗證 RemoveHead、RemoveTail"<<endl;
//RemoveHead：移除開頭位置元素
CL_Int_Data.RemoveHead();
//GetHead：取出開頭位置的內容
Int_Temp=CL_Int_Data.GetHead();
cout<<"目前頭的位置內容值(RemoveHead,GetHead)(1.100)： "<<Int_Temp<<endl;
//RemoveTail：移除結尾位置元素
CL_Int_Data.RemoveTail();
//GetTail：取出結尾位置的內容
Int_Temp=CL_Int_Data.GetTail();
cout<<"目前結尾的位置內容值(RemoveTail,GetTail)(1)： "<<Int_Temp<<endl;
//IsEmpty：檢測是否為空串列
Int_Temp=CL_Int_Data.IsEmpty();
if(Int_Temp==1)
{
cout<<"目前是空的串列"<<endl;
}
else
{
cout<<"目前不是空串列"<<endl;
}
//GetCount：檢測目前串列大小
Int_Temp=CL_Int_Data.GetCount();
cout<<"目前串列所含元素數目(GetCount)："<<Int_Temp<<endl;
//GetSize：檢測目前串列大小
Int_Temp=CL_Int_Data.GetSize();
cout<<"目前串列所含元素數目(GetSize)："<<Int_Temp<<endl;
cout<<endl<<endl;
//-----------------------------------------------------------
cout<<"驗證 InsertAfter、InsertBefore"<<endl;
//InsertAfter：插入一個元素至目前位置的下一個位置
Pos_Temp=CL_Int_Data.GetHeadPosition ();
Int_Temp=-3;
CL_Int_Data.InsertAfter (Pos_Temp,Int_Temp);
cout<<"串列(InsertAfter)(1,-3)"<<endl;
Int_Temp=-2;
CL_Int_Data.InsertAfter (Pos_Temp,Int_Temp);
cout<<"串列(InsertAfter)(1,-2,-3)"<<endl;
Int_Temp=-1;
CL_Int_Data.InsertAfter (Pos_Temp,Int_Temp);
cout<<"串列(InsertAfter)(1,-1.-2,-3)"<<endl;
//InsertBefore：插入一個元素至目前位置的前一個位置
Int_Temp=100;
CL_Int_Data.InsertBefore (Pos_Temp,Int_Temp);
cout<<"串列(InsertBefore)(100,1,-1.-2,-3)"<<endl;
Int_Temp=120;
CL_Int_Data.InsertBefore (Pos_Temp,Int_Temp);
cout<<"串列(InsertBefore)(100,120,1,-1.-2,-3)"<<endl;
//使用回圈將資料讀出
Pos_Temp=CL_Int_Data.GetHeadPosition ();
for(Int_Loop1=0;Int_Loop1<6;Int_Loop1++)
{
cout<<"串列資料["<<Int_Loop1<<"]="<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
CL_Int_Data.GetNext (Pos_Temp);
}
cout<<endl<<endl;
//-----------------------------------------------------------
cout<<"驗證 Find、FindIndex"<<endl;
//Find：尋找特定 POSITION
cout<<"請輸入搜尋資料：";
cin>>Int_Temp;
Pos_Temp=CL_Int_Data.Find(Int_Temp);
if(Pos_Temp==NULL)
{
cout<<"未在串列中搜尋到資料"<<endl;
}
else
{
cout<<"串列資料存在搜尋資料："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
}
//FindIndex：尋找特定索引值內容
cout<<"請輸入尋找索引值位置：";
cin>>Int_Temp;
Pos_Temp=CL_Int_Data.FindIndex (Int_Temp);
cout<<"第"<<Int_Temp<<"位置內容值："<<CL_Int_Data.GetAt (Pos_Temp)<<endl;
system("Pause");
return 0;
}
執行結果 - 省略
參考資料：
- MSDN，CMap Class，http://msdn.microsoft.com/zh-tw/library/s897094z(v=VS.100).aspx
- MSDN，CMap Members，http://msdn.microsoft.com/zh-tw/library/tw6s6xay.aspx
- 維基百科，雜湊函式(Hash Function)，http://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8
留言列表
