使用 庫建立重複鍵關聯容器

使用 <multimap> 庫建立重複鍵關聯容器

作者：Danny Kalev

編譯：TT 工作室

原文出處：Use multimap to Create Associative Containers with Duplicate Keys

摘要： 标準庫的  multimap 容器與 map 關聯容器非常類似——但是，multimap 允許重複鍵。這個特性使得 multimap 比想象的要有用得多。本文将對之進行探讨。

　　在“ 使用 <map> 庫建立關聯容器”一文中，我們讨論了标準庫中的 map 關聯容器。但那隻是 map 容器的一部分。标準庫還定義了一個 multimap 容器，它與 map 類似，所不同的是它允許重複鍵。這個屬性使得 multimap 比預想的要更有用：比如在電話簿中相同的人可以有兩個以上電話号碼，檔案系統中可以将多個 符号連結映射到相同的實體檔案，或DNS伺服器可以将幾個URLs映射到相同的IP位址。在這些場合，你可以象下面這樣：

// 注: 僞碼
multimap <string, string> phonebook;
phonebook.insert("Harry","8225687"); // 家裡電話
phonebook.insert("Harry","555123123"); // 機關電話
phonebook.insert("Harry"," 2532532532"); // 行動電話      

　　在 multimap 中能存儲重複鍵的能力大大地影響它的接口和使用。那麼如何建立非唯一鍵的關聯容器呢？答案是使用在 <map> 庫中定義的 multimap 容器。

提出問題

　　與 map 不同，multimap 可以包含重複鍵。這就帶來一個問題：重載下标操作符如何傳回相同鍵的多個關聯值？以下面的僞碼為例：

string phone=phonebook["Harry];      

　　标準庫設計者的解決這個問題方法是從 multimap 中去掉下标操作符。是以，需要用不同的方法來插入和擷取元素以及和進行錯誤處理。

插入

　　假設你需要開發一個 DNS 背景程式（也就是 Windows 系統中的服務程式），該程式将 IP 位址映射比對的 URL 串。你知道在某些情況下，相同的 IP 位址要被關聯到多個 URLs。這些 URLs 全都指向相同的站點。在這種情況下，你應該使用 multimap，而不是 map。例如：

#include <map>
#include <string>

multimap <string, string> DNS_daemon;      

　　用 insert() 成員函數而不是下标操作符來插入元素。insert()有一個 pair 類型的參數。在“使用 <map> 庫建立關聯容器”中我們示範了如何使用 make_pair() 輔助函數來完成此任務。你也可以象下面這樣使用它：

DNS_daemon.insert(make_pair("213.108.96.7","cppzone.com"));      

　　在上面的 insert()調用中，串 “213.108.96.7”是鍵，“cppzone.com”是其關聯的值。以後插入的是相同的鍵，不同的關聯值：

DNS_daemon.insert(make_pair("213.108.96.7","cppluspluszone.com"));      

　　是以，DNS_daemon 包含兩個用相同鍵值的元素。注意 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()成員函數傳回指向新插入元素的疊代指針，也就是 iterator（multimap::insert()總是能執行成功）。但是 map::insert() 傳回 pair<iterator, bool>，此處 bool 值表示插入操作是否成功。

查找單個值

　　與 map 類似，multimap 具備兩個版本重載的 find()成員函數：

iterator find(const key_type& k);
const_iterator find(const key_type& k) const;      

find(k) 傳回指向第一個與鍵 k 比對的 pair 的疊代指針，這就是說，當你想要檢查是否存在至少一個與該鍵關聯的值時，或者隻需第一個比對時，這個函數最有用。例如：

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; 
}      

處理多個關聯值

　　count(k) 成員函數傳回與給定鍵關聯的值得數量。下面的例子報告了有多少個與鍵 “213.108.96.7” 關聯的值：

cout<<dns.count("213.108.96.7") //output: 2
<<" elements associated"<<endl;      

　　為了存取 multimap 中的多個值，使用 equal_range()、lower_bound()和 upper_bound()成員函數：

equal_range(k)：該函數查找所有與 k 關聯的值。傳回疊代指針的 pair，它标記開始和結束範圍。下面的例子顯示所有與鍵“213.108.96.7”關聯的值：

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) 查找第一個與鍵 k 關聯的值，而 upper_bound(k) 是查找第一個鍵值比 k 大的元素。下面的例子示範用 upper_bound()來定位第一個其鍵值大于“213.108.96.7”的元素。通常，當鍵是一個字元串時，會有一個詞典編纂比較：

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      

如果你想顯示其後所有的值，可以用下面這樣的循環：

// 插入有相同鍵的多個值
dns.insert(make_pair("219.108.96.70","pythonzone.com"));
dns.insert(make_pair("219.108.96.70","python-zone.com"));

// 獲得第一個值的疊代指針
CIT cit=dns.upper_bound("213.108.96.7");

// 輸出: pythonzone.com，python-zone.com
while(cit!=dns.end())
{
　　　cout<<cit->second<<endl; 
　　　++cit;
}      

結論

　　雖然 map 和 multimap 具有相同的接口，其重要差别在于重複鍵，設計和使用要差別對待。此外，還要注意每個容器裡 insert()成員函數的細微差别。