|
使用 <multimap> 庫創(chuàng)建重復(fù)鍵關(guān)聯(lián)容器
作者：Danny Kalev
編譯：TT 工作室
原文出處：Use multimap to Create Associative Containers with Duplicate Keys
| 摘要：標(biāo)準(zhǔn)庫的 multimap 容器與 map 關(guān)聯(lián)容器非常類似——但是，multimap 允許重復(fù)鍵。這個(gè)特性使得 multimap 比想象的要有用得多。本文將對之進(jìn)行探討。 |
在“使用 <map> 庫創(chuàng)建關(guān)聯(lián)容器”一文中，我們討論了標(biāo)準(zhǔn)庫中的 map 關(guān)聯(lián)容器。但那只是 map 容器的一部分。標(biāo)準(zhǔn)庫還定義了一個(gè) multimap 容器，它與 map 類似，所不同的是它允許重復(fù)鍵。這個(gè)屬性使得 multimap 比預(yù)想的要更有用：比如在電話簿中相同的人可以有兩個(gè)以上電話號碼，文件系統(tǒng)中可以將多個(gè)符號鏈接映射到相同的物理文件，或DNS服務(wù)器可以將幾個(gè)URLs映射到相同的IP地址。在這些場合，你可以象下面這樣：
// 注: 偽碼
multimap <string, string> phonebook;
phonebook.insert("Harry","8225687"); // 家里電話
phonebook.insert("Harry","555123123"); // 單位電話
phonebook.insert("Harry"," 2532532532"); // 移動電話
在 multimap 中能存儲重復(fù)鍵的能力大大地影響它的接口和使用。那么如何創(chuàng)建非唯一鍵的關(guān)聯(lián)容器呢？答案是使用在 <map> 庫中定義的 multimap 容器。
提出問題
與 map 不同，multimap 可以包含重復(fù)鍵。這就帶來一個(gè)問題：重載下標(biāo)操作符如何返回相同鍵的多個(gè)關(guān)聯(lián)值？以下面的偽碼為例：
string phone=phonebook["Harry];
標(biāo)準(zhǔn)庫設(shè)計(jì)者的解決這個(gè)問題方法是從 multimap 中去掉下標(biāo)操作符。因此，需要用不同的方法來插入和獲取元素以及和進(jìn)行錯(cuò)誤處理。
插入
假設(shè)你需要開發(fā)一個(gè) DNS 后臺程序（也就是 Windows 系統(tǒng)中的服務(wù)程序），該程序?qū)?IP 地址映射匹配的 URL 串。你知道在某些情況下，相同的 IP 地址要被關(guān)聯(lián)到多個(gè) URLs。這些 URLs 全都指向相同的站點(diǎn)。在這種情況下，你應(yīng)該使用 multimap，而不是 map。例如：
#include <map>
#include <string>
multimap <string, string> DNS_daemon;
用 insert() 成員函數(shù)而不是下標(biāo)操作符來插入元素。insert()有一個(gè) pair 類型的參數(shù)。在“使用 <map> 庫創(chuàng)建關(guān)聯(lián)容器”中我們示范了如何使用 make_pair() 輔助函數(shù)來完成此任務(wù)。你也可以象下面這樣使用它：
DNS_daemon.insert(make_pair("213.108.96.7","cppzone.com"));
在上面的 insert()調(diào)用中，串 “213.108.96.7”是鍵，“cppzone.com”是其關(guān)聯(lián)的值。以后插入的是相同的鍵，不同的關(guān)聯(lián)值：
DNS_daemon.insert(make_pair("213.108.96.7","cppluspluszone.com"));
因此，DNS_daemon 包含兩個(gè)用相同鍵值的元素。注意 multimap::insert() 和 map::insert() 返回的值是不同的。
typedef pair <const Key, T> value_type;
iterator
insert(const value_type&); // #1 multimap
pair <iterator, bool>
insert(const value_type&); // #2 map
multimap::insert()成員函數(shù)返回指向新插入元素的迭代指針，也就是 iterator（multimap::insert()總是能執(zhí)行成功）。但是 map::insert() 返回 pair<iterator, bool>，此處 bool 值表示插入操作是否成功。
查找單個(gè)值
與 map 類似，multimap 具備兩個(gè)版本重載的 find()成員函數(shù)：
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
find(k) 返回指向第一個(gè)與鍵 k 匹配的 pair 的迭代指針，這就是說，當(dāng)你想要檢查是否存在至少一個(gè)與該鍵關(guān)聯(lián)的值時(shí)，或者只需第一個(gè)匹配時(shí)，這個(gè)函數(shù)最有用。例如：
typedef multimap <string, string> mmss;
void func(const mmss & dns)
{
mmss::const_iterator cit=dns.find("213.108.96.7");
if (cit != dns.end())
cout <<"213.108.96.7 found" <<endl;
else
cout <<"not found" <<endl;
}
處理多個(gè)關(guān)聯(lián)值
count(k) 成員函數(shù)返回與給定鍵關(guān)聯(lián)的值得數(shù)量。下面的例子報(bào)告了有多少個(gè)與鍵 “213.108.96.7” 關(guān)聯(lián)的值：
cout<<dns.count("213.108.96.7") //output: 2
<<" elements associated"<<endl;
為了存取 multimap 中的多個(gè)值，使用 equal_range()、lower_bound()和 upper_bound()成員函數(shù)：
equal_range(k)：該函數(shù)查找所有與 k 關(guān)聯(lián)的值。返回迭代指針的 pair，它標(biāo)記開始和結(jié)束范圍。下面的例子顯示所有與鍵“213.108.96.7”關(guān)聯(lián)的值：
typedef multimap <string, string>::const_iterator CIT;
typedef pair<CIT, CIT> Range;
Range range=dns.equal_range("213.108.96.7");
for(CIT i=range.first; i!=range.second; ++i)
cout << i->second << endl; //output: cpluspluszone.com
// cppzone.com
lower_bound() 和 upper_bound()：lower_bound(k) 查找第一個(gè)與鍵 k 關(guān)聯(lián)的值，而 upper_bound(k) 是查找第一個(gè)鍵值比 k 大的元素。下面的例子示范用 upper_bound()來定位第一個(gè)其鍵值大于“213.108.96.7”的元素。通常，當(dāng)鍵是一個(gè)字符串時(shí)，會有一個(gè)詞典編纂比較：
dns.insert(make_pair("219.108.96.70", "pythonzone.com"));
CIT cit=dns.upper_bound("213.108.96.7");
if (cit!=dns.end()) //found anything?
cout<<cit->second<<endl; //display: pythonzone.com
如果你想顯示其后所有的值，可以用下面這樣的循環(huán)：
// 插入有相同鍵的多個(gè)值
dns.insert(make_pair("219.108.96.70","pythonzone.com"));
dns.insert(make_pair("219.108.96.70","python-zone.com"));
// 獲得第一個(gè)值的迭代指針
CIT cit=dns.upper_bound("213.108.96.7");
// 輸出: pythonzone.com，python-zone.com
while(cit!=dns.end())
{
cout<<cit->second<<endl;
++cit;
}
結(jié)論
雖然 map 和 multimap 具有相同的接口，其重要差別在于重復(fù)鍵，設(shè)計(jì)和使用要區(qū)別對待。此外，還要注意每個(gè)容器里 insert()成員函數(shù)的細(xì)微差別。
|