C++ STL 容器 multimap

閱讀此篇前若有需要請先參看 C++ STL 容器 map 的介紹。

map 中不允許存在相同的元素，而 multimap 允許。這一設計上改變也帶來一些使用上的不同。

通路 multimap 中的元素

由于 multimap 中允許存在關鍵字值相同的元素。是以我們很難想象通過下标通路會發生什麼，實際上 multimap 并不允許通過下标來通路其中的元素。由于 map 中的元素是依照 index 的遞增順循序排列的，multimap 依然保持了這一特性，是以在 multimap 中具有相同 index 值的元素會相鄰存儲。這裡提供三種解決方案：

**使用 .find 結合 .count **

我們可以先是用 .find 找出第一個比對 index 值的元素的疊代器，再利用 .count 得到該 multimap 中一共有多少個具有該 index 值的元素。

multimap<char, int> mm = {{'a', 1}, {'a', 2}, {'b', 3}};
auto it = mm.find('a');//it = mm.begin()
int size = mm.count('a');//size = 2
while (size > 0) {
    cout << it->second << " ";
    size--;
} // 輸出：1 2
           

使用 .lower_bound 和 .upper_bound

.lower_bound 傳回 multimap 中第一個關鍵字不小于給定值元素的疊代器

.upper_bound 傳回 multimap 中第一個關鍵字大于給定值元素的疊代器

multimap<char, int> mm = {{'a', 1}, {'a', 2}, {'b', 3}};
auto b = mm.lower_bound('a');//it = mm.begin()
auto e = mm.upper_bound('a');//size = 2
for (auto it=b; it!=e; it++) {
    cout << it->second << " ";
}
// 輸出：1 2
           

即 .lower_bound 和 .upper_bound 的傳回的是一個關于查找關鍵字的左閉右開區間

[ .lower_bound, .ipper_bound )

當 .lower_bound 與 .ipper_bound 值相等時，意為 multimap 中不存在具有該關鍵字的元素。

使用 .equal_range 函數

.equal_range 會傳回一個 pair，此 pair 的第一個成員即是 .lower_bound 的傳回值；第二個成員即是 .upper_bound 的傳回值。

multimap<char, int> mm = {{'a', 1}, {'a', 2}, {'b', 3}};
auto p = mm.equal_ragne('a'); // 
for (auto it=p.first; it!=p.second; it++) {
   cout << it->second << " ";
}
// 輸出：1 2