C++實(shí)際開發(fā)的過程會經(jīng)常使用到map。map是一個key-value值對，key唯一，可以用find進(jìn)行快速的查找。其時間復(fù)雜度為O(logN)，如果采用for循環(huán)進(jìn)行遍歷數(shù)據(jù)時間復(fù)雜度為O(N)。如果map中的數(shù)據(jù)量比較少時，采用find和for循環(huán)遍歷的效率基本沒有太大的區(qū)別，但是在實(shí)際的開發(fā)過程中，存儲在map中的數(shù)據(jù)往往是大量的，這個時候map采用find方式效率比遍歷效率高的多。

確定采用find方式查找數(shù)據(jù)后，我們需要考慮存儲map的空間復(fù)雜度，對于基礎(chǔ)數(shù)據(jù)類型的數(shù)據(jù)（int char等）這里就不做討論。本文討論的是map中存儲的數(shù)據(jù)結(jié)構(gòu)struct情況。
1、如果map中的key為struct此時，需要先對struct進(jìn)行操作符重載，關(guān)于這部分內(nèi)容可以參考C++ 重載操作符示例
2、map中的key只能是對象，而不能是指針。（這一點(diǎn)尤為重要）。

下面給出三個map定義進(jìn)行說明：

std::map<NHSymbolkey, Stru_NHSymbol>*   pmapNHSymbolInfo1
std::map<NHSymbolkey, Stru_NHSymbol*>*  pmapNHSymbolInfo2
std::map<NHSymbolkey*, Stru_NHSymbol*>*  pmapNHSymbolInfo2

其中，pmapNHSymbolInfo1、pmapNHSymbolInfo2中使用find正常，遍歷也正常，pmapNHSymbolInfo3使用find查找不到對應(yīng)的數(shù)據(jù)（數(shù)據(jù)已經(jīng)存在，find不到，遍歷可以找到）

原因：std::map<NHSymbolkey*, Stru_NHSymbol*>*  pmapNHSymbolInfo2在find的時候是根據(jù)指針進(jìn)行查找的。而在數(shù)據(jù)insert時，數(shù)據(jù)都是new的，每次new出的地址是不一樣的，在find數(shù)據(jù)時，根據(jù)地址查找結(jié)果就找不到數(shù)據(jù)。通過遍歷是取出地址中內(nèi)容一一比較，這樣能夠找到數(shù)據(jù)。

pmapNHSymbolInfo1、pmapNHSymbolInfo2兩種方式都可以使用find方式查找數(shù)據(jù)，但是pmapNHSymbolInfo1中Stru_NHSymbol為對象，這樣會使map占用空間比較大，pmapNHSymbolInfo2的Stru_NHSymbol為指針，存儲時地址占用空間小，但是每次都是new處理來的，所有一定要記住使用完成后一定要delete，否則會出現(xiàn)內(nèi)存泄露。

3、map插入數(shù)據(jù)2中方式比較 
std::map<NHSymbolkey, Stru_NHSymbol*>*  pmapNHSymbolInfo
pmapNHSymbolInfo->insert(std::make_pair(pNHSymbolkey, pNHSymbol));該方式的key如果出現(xiàn)重復(fù)，則會插入數(shù)據(jù)失??；

(*pmapNHSymbolInfo)[objNHSymbolkey] = pNHSymbol;該方式的key如果出現(xiàn)重復(fù)則直接覆蓋掉原來的數(shù)據(jù)，永遠(yuǎn)不會出現(xiàn)插入失敗的問題。
結(jié)論：C++ map中key不要使用指針，請直接使用對象。

最新評論