關(guān)系數(shù)據(jù)庫,科學(xué)計(jì)算應(yīng)用以及基于Web的系統(tǒng)常常需要類似 vector 的容器,其索引可以是如何數(shù)據(jù)類型,不一定是整數(shù)。這樣的容器叫關(guān)聯(lián)容器,或者 map。例如,目錄服務(wù)應(yīng)用可以將私人姓名作為索引來存儲(chǔ),電話號(hào)碼作為其關(guān)聯(lián)的值:
directory["Harry"]=8225687;// 插入 "Harry" 并與他的電話號(hào)碼關(guān)聯(lián)
iterator it=directory.find("Harry");// 獲取 Harry 的電話號(hào)碼
其它關(guān)聯(lián)容器的應(yīng)用還包括將 URLs 映射到 IP 的 DNS 服務(wù)器,字典,庫存清單,工資表等等。那么如何突破整型索引的局限,實(shí)現(xiàn)用其它數(shù)據(jù)類型作為索引的關(guān)聯(lián)容器呢?答案是:使用 <map> 庫創(chuàng)建和處理關(guān)聯(lián)容器。
Pair 和 Map
最近的一篇文章中,我介紹了 tuple 的概念,它是不同類型元素的集合。在這篇文章中,有一個(gè)內(nèi)容沒有提到,那就是 C++98 標(biāo)準(zhǔn)庫已經(jīng)具備一個(gè)特殊的 tuple 類型——pair。它將鍵值(也就是第一個(gè)元素)與某個(gè)值(第二個(gè)值)關(guān)聯(lián)。例如:
#include <utility> //definition of pair
#include <string>
pair <string, string> prof_and_course("Jones", "Syntax");
pair <int, string> symbolic_const (0, "false");
標(biāo)準(zhǔn)庫還定義了一個(gè)輔助函數(shù),方便 pair 類型的創(chuàng)建:
string prof;
string course;
make_pair(prof,course);//returns pair <string,string>
第一步:構(gòu)造和初始化一個(gè) map 對(duì)象
假設(shè)你正在開發(fā)一個(gè)地址簿程序,地址簿包含姓名和 e-mail 地址。類模板 map 在 <map> 中定義i,它是一個(gè)使用類型對(duì)的關(guān)聯(lián)容器,第一個(gè)元素是索引,第二個(gè)元素是關(guān)聯(lián)的值。使用方法如下:
#include <map>
map <string, string> addresses;
為了添加元素,使用下標(biāo)算符:
addresses["Paul W."]="paul@mail.com";
這里,串“Paul W.”是索引或鍵值,“paul@mail.com”是其關(guān)聯(lián)的值。如果該 map 已經(jīng)包含了此鍵值,那么當(dāng)前所關(guān)聯(lián)的值不會(huì)改變:
addresses["Paul W."]= "newaddr@com.net"; // 不起作用???我測(cè)試起作用
第二步:搜索
在不插入元素的情況下,如果你想檢查某個(gè)元素是否存在,可以使用 find()成員函數(shù)。find()有兩個(gè)重載的版本:
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
通常,用 typedef 可以使代碼更可讀一些:
typedef map <string, string>::const_iterator CIT;
CIT cit=addresses.find("Paul W.");
if (cit==addresses.end())
cout << "sorry, no such key" << endl;
else
cout << cit->first << ''\t'' << cit->second << endl;
表達(dá)式中 cit->first 和 cit->second 分別返回鍵值及其關(guān)聯(lián)的值。
第三步:元素遍歷
現(xiàn)在讓我們看一個(gè)更現(xiàn)實(shí)的情況。假設(shè)你正在經(jīng)營一家旅行社,每一個(gè)代理做一單業(yè)務(wù)都可以獲得獎(jiǎng)金。這些代理的信息存儲(chǔ)在某個(gè)文件中,其格式如下:
Bob 35
Bob 90
Jane 80.25
Sue 100
Jane 65.5
你的應(yīng)用程序必須匯總所有代理的獎(jiǎng)金并將每個(gè)代理的獎(jiǎng)金總數(shù)顯示出來.首先,創(chuàng)建一個(gè) map,然后讀取該數(shù)據(jù)文件:
map <string, double> bonuses;
string agent;
double bonus=0;
ifstream bonusfile("bonuses.dat");
if(!bonusfile)
{
// 報(bào)告出錯(cuò)信息并終止程序
}
while (bonusfile >> agent >> bonus)
{
bonuses[agent]+=bonus;// 累加每個(gè)代理的獎(jiǎng)金
}
不管理相不相信,就這么簡(jiǎn)單!且讓我們來分析一下該循環(huán)。打開數(shù)據(jù)文件之后,while 循環(huán)讀取每個(gè)值對(duì),并將其存入 agent 和 bouns 對(duì)象。接著,它將 agent 和 bouns 插入到該 map。此處的關(guān)鍵技巧是:如果鍵值(agent)已經(jīng)存在,那么 += 操作符便將最新讀取的 bouns 累加到存儲(chǔ)在 map 中當(dāng)前的 bouns 中。因?yàn)楸磉_(dá)式:
map[key]
返回與鍵值關(guān)聯(lián)的值。當(dāng)重載的 += 操作符被調(diào)用時(shí),該值便被累加到新讀取的 bouns 中。最后累加的和覆蓋 map 中舊的關(guān)聯(lián)值。記?。寒?dāng)你使用下標(biāo)算符機(jī)制時(shí),純粹的賦值操作并不會(huì)改寫現(xiàn)有的值,只有重載的 += 才這么做。
幸運(yùn)的是,map 并不包含一個(gè)必須要初始化的鍵值,表達(dá)式:
map[key]
返回默認(rèn)的初始化 T,而 T 在上述例子中是 double 類型。默認(rèn)的初始值為 0。至此,map 包含代理及其獎(jiǎng)金匯總值對(duì)。下面的循環(huán)用來顯示這些值對(duì),輸出如圖一所示:
for(CIT p=bonuses.begin(); p!=bonuses.end(); ++p)
{
cout << p->first <<''\t'' << p->second <<endl;
}
散列的關(guān)聯(lián)容器
標(biāo)準(zhǔn)庫目前還不提供散列關(guān)聯(lián)容器。這種容器可以大大改進(jìn)性能,因?yàn)樗鼈兪褂蒙⒘兴惴◤脑瓉淼淖址饕缮替I值。但是,許多 IDEs 提供非標(biāo)準(zhǔn)散列容器擴(kuò)展。值得慶幸的是,新的 C++0X 標(biāo)準(zhǔn)彌補(bǔ)了這一點(diǎn),在 C++ 中添加了一組散列容器和與之相關(guān)的算法。
//定義
pair<int, string> ming(1,"ming1");
map<int ,string> authors;
//插入
authors.insert(ming);
authors.insert(map<int, string>::value_type(2,"ming2"));
authors.insert(make_pair(3,"ming3"));
//修改
cout << "before changed " << authors[3] << endl;
authors[3] = "ming4";
cout <<" after changed " << authors[3] << endl;
//刪除
cout <<" before erase " << authors[2] << endl;
map<int, string>::iterator iter = authors.find(2);
if(iter != authors.end())
{
authors.erase(iter);
}
cout <<" after changed " << authors[2] << endl;
輸出:
before changed ming3
after changed ming4
before erase ming2
after changed
//刪除指針
map<string, test4*> pointerMap;
pointerMap.insert(make_pair("1", new test4()));
std::map<string, test4*>::iterator iter1;
for (iter1 = pointerMap.begin(); iter1 != pointerMap.end();++iter1)
{
delete iter1->second;
}