C++ multimap(STL multimap)的使用詳解

2020-07-16 10:04:29
multimap 容器儲存的是有序的鍵/值對,但它可以儲存重複的元素。multimap 中會出現具有相同鍵的元素序列,它們會被新增到容器中。multimap 和 map 有相同範圍的建構函式,預設的比較鍵的函數是 less<K>()。

multimap 大部分成員函數的使用方式和 map 相同。因為重複鍵的原因,multimap 有一些函數的使用方式和 map 有一些區別。接下來介紹 multimap 和 map 容器不同的那些成員函數的用法。

multimap 容器的成員函數 insert() 可以插入一個或多個元素,而且插入總是成功。這個函數有很多的版本都可以插入單個元素,它們都會返回一個指向插入元素的疊代器。下面有一個範例,假設我們已經使用了宣告 using std::string:
std::multimap<string, string〉 pets; // Element is pair{pet_type, pet_name}
auto iter = pets.insert (std::pair<string, string>{string{"dog"}, string{"Fang"}});
iter = pets.insert(iter, std::make_pair("dog", "Spot")); // Insert Spot before Fang
pets.insert(std::make_pair("dog", "Rover"));// Inserts Rover after Fang
pets.insert (std::make_pair ("cat", "Korky"));// Inserts Korky before all dogs
pets.insert ({{ "rat", "Roland"}, {"pig", "Pinky" }, {"pig", "Perky"}});//Inserts list elements
第三條語句的第一個引數是一個作為提示符的疊代器,它說明了元素應該被插入的位置。元素會被立即插入到 iter 所指向元素的前面,因此,這使我們可以覆蓋預設的插入位置。對於預設的插入位置來說,元素會被插入到先前插入的鍵為 "dog" 的元素的後面。元素預設是按照鍵的升序插入的。如果沒有用提示符改變插入位置,有相同鍵的元素的位置和插入位置相同。最後一條語句插入了一些初始化列表中的元素。有高階版本的 insert(),它可以接收兩個疊代器引數,用來指定插入元素的範圍。

和 map —樣,multimap 的成員函數 emplace() 可以在容器的適當位置構造元素。在插入具有相同鍵的元素時,可以使用 multimap 的成員函數 emplace_hint(),可以通過為這個函數提供一個疊代器形式的提示符來控制元素的生成位置:
auto iter = pets.emplace("rabbit”,"Flopsy");
iter = pets.emplace_hint (iter, "rabbit", "Mopsy");// Create preceding Flopsy
這兩個函數都返回一個指向插入元素的疊代器。emplace_hint() 函數盡可能近地在第一個引數所指向位置的前面生成一個新元素。如果只使用 emplace() 來插入 "Mopsy",它可能會被插入到當前所有鍵為 "rabbit" 的元素的後面。

multimap 不支援下標運算子,因為鍵並不能確定一個唯一元素。和 map 相似,multimap 也不能使用 at() 函數。multimap 的成員函數 fmd() 可以返回一個鍵和引數匹配的元素的疊代器。例如:
std::multimap<std::string, size_t> people {{"Ann",25},{"Bill", 46}, {"Jack", 77}, {"Jack", 32},{"Jill", 32}, {"Ann", 35} };
std::string name {"Bill"};
auto iter = people.find(name);
if (iter ! = std::end (people))
    std::cout << name << " is " << iter->second << std::endl;
iter = people.find ("Ann");
if (iter != std::end(people))
    std::cout << iter->first << " is " << iter->second <<std::endl;
如果沒有找到鍵,會返回一個結束疊代器,所以我們應該總是對返回值進行檢查。第一個 find() 呼叫的引數是一個鍵物件,因為這個鍵是存在的,所以輸出語句可以執行。第二個 find() 呼叫的引數是一個字串常數,它說明引數不需要和鍵是相同的型別。對容器來說,可以用任何值或物件作為引數,只要可以用函數物件將它們和鍵進行比較。最後一條輸出語句也可以執行,因為有等於 "Ann" 的鍵。事實上,這裡有兩個等於 "Ann" 的鍵,你可能也會得到不同的執行結果。

如果使用 multimap 容器,幾乎可以肯定它會包含鍵重複的元素;否則,就應該使用 map。一般來說,我們想存取給定鍵對應的所有元素。成員函數 equal_range() 就可以做到這一點。它會返回一個封裝了兩個疊代器的 pair 物件,這兩個疊代器所確定範圍內的元素的鍵和引數值相等。例如:
auto pr = people.equal_range("Ann");
if(pr.first != std::end(people))
{
    for (auto iter = pr.first ; iter != pr.second; ++iter)
        std:cout << iter->first << " is " << iter->second << std::endl;
}
equal_range() 的引數可以是和鍵同型別的物件,或是不同型別的但可以和鍵比較的物件。返回的 pair 物件的成員變數 first 是一個疊代器,它指向第一個大於等於引數的元素;如果鍵和引數相等的元素存在的話,它是第一個鍵和引數相同的元素。如果鍵不存在,pair 的成員變數 first 就是容器的結束疊代器,所以應該總是對它們進行撿查。

pair 的成員變數 second 也是一個疊代器,它指向鍵值大於引數的第一個引數;如果沒有這樣的元素,它會是一個結束疊代器。這段程式碼會輸出容器中鍵值為”Ann”的元素的一些資訊。

multimap 的成員函數 lower_bound() 會返回一個疊代器,它指向鍵值和引數相等或大於引數的第一個元素,或者指向結束疊代器。upper_bound() 也返回一個疊代器,它指向鍵值大於函數引數的第一個元素,如果這樣的元素不出現的話,它就是一個結束疊代器。所以,當存在一個或多個相等鍵時,這些函數會返回一個開始疊代器和一個結束疊代器,它們指定了和引數匹配的元素的範圍,這和 equal_range() 返回的疊代器是相同的。因而前面的程式碼段可以這樣重寫:
auto iter1 = people.lower_bound("Ann");
auto iter2 = people.lower_bound("Ann");
if(iter1 != std::end(people))
{
    for(auto iter = iterl ; iter != iter2; ++iter)
        std::cout << iter->first << " is " << iter->second << std::endl;
}
它和前一個程式碼段的輸出結果是相同的。通過呼叫 multimap 的成員函數 count() 可以知道有多少個元素的鍵和給定的鍵相同。
auto n = people.count("Jack"); // Returns 2
可以用不同的方式使用這些函數。可以選擇 find() 或 equal_range() 來存取元素。如果以班級為鍵,在 mutilmap 中儲存學生資訊,可以用成員函數 count() 來獲取班級的大小。當然,通過將在前面章節介紹的 distance() 函數模板運用到成員函數 equal_range() 返回的疊代器或者 lower_bound() 和 upper_bound() 返回的疊代器上,也可以獲取鍵和給定鍵相等的元素 的個數:
std::string key{"Jack"};
auto n = std::distance( people.lower_bound(key),people.upper_bound(key)); // No. of elements matching key
注意,全域性的 equal_range()、lower_bound()、upper_bound() 函數模板的使用方式和關聯容器中同名成員函數的使用方式略有不同。在教學後面的部分你會了解到這些。

multimap 的成員函數 erase() 有 3 個版本:
  1. 以待刪除兀素的疊代器作為引數,這個函數沒有返回值;
  2. 以一個鍵作為引數,它會刪除容器中所有含這個鍵的元素,返回容器中被移除元素的個數;
  3. 接受兩個疊代器引數,它們指定了容器中的一段元素,這個範圍內的所有元素都會被刪除,這個函數返回的疊代器指向最後一個被刪除元素的後一個位置。

下面在範例中嘗試一些multimap操作:
// Using a multimap
#include <iostream>                                        // For standard streams
#include <string>                                          // For string class
#include <map>                                             // For multimap container
#include <cctype>                                          // For toupper()

using std::string;
using Pet_type = string;
using Pet_name = string;

int main()
{
    std::multimap<Pet_type, Pet_name> pets;
    Pet_type type {};
    Pet_name name {};
    char more {'Y'};
    while(std::toupper(more) == 'Y')
    {
        std::cout << "Enter the type of your pet and its name: ";
        std::cin >> std::ws >> type >> name;

        // Add element - duplicates will be LIFO
        auto iter = pets.lower_bound(type);
        if(iter != std::end(pets))
            pets.emplace_hint(iter, type, name);
        else
            pets.emplace(type, name);
        std::cout << "Do you want to enter another(Y or N)? ";
        std::cin >> more;
    }

    // Output all the pets
    std::cout << "nPet list by type:n";
    auto iter = std::begin(pets);
    while(iter != std::end(pets))
    {
        auto pr = pets.equal_range(iter->first);
        std::cout << "nPets of type " << iter->first << " are:n";
        for(auto p = pr.first; p != pr.second; ++p)
            std::cout << "  " << p->second;
        std::cout << std::endl;
        iter = pr.second;
    }
}
我們在程式碼中使用一些型別別名將型別及其表示的事物關聯了起來。pets 容器儲存的是 pair<string,string> 型別的物件,這個 pair 物件以 pet 型別作為鍵,以 pet 的名稱為物件。

程式碼中的第一個迴圈,將給定鍵的第二個以及隨後的元素插入到這個鍵序列的前面。這裡使用 emplace_hint() 來插入元素。如果它是給定型別的第一個元素,就呼叫 emplace() 在適當的位置建立元素。

在第二個 while 迴圈中,按照 pet 的型別分組輸出元素。首先找到 iter 指向的 pet 的第一個型別,然後用 equal_range() 返回的疊代器列出這種 pet 型別的全部序列。最後將 iter 設為這個序列的結束疊代器,它也是一個指向下一個 pet 型別的疊代器,或是容器的結束疊代器。後者會結束回圈。下面是一些範例輸出:

Enter the type of your pet and its name: rabbit Flopsy
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: rabbit Mopsy
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: rabbit Cottontail
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: dog Rover
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: dog Spot
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: snake Slither
Do you want to enter another(Y or N)? y
Enter the type of your pet and its name: snake Sammy
Do you want to enter another(Y or N)? n

Pet list by type:

Pets of type dog are:
  Spot  Rover

Pets of type rabbit are:
  Cottontail  Mopsy  Flopsy

Pets of type snake are:
  Sammy  Slither

輸出表明元素是按鍵的升序排列的,鍵相同的元素的順序和它們輸入的順序相反。