C++ multiset用法詳解（附帶完整範例）

multiset<T> 容器就像 set<T> 容器，但它可以儲存重複的元素。這意味我們總可以插入元素，當然必須是可接受的元素型別。預設用 less<T> 來比較元素，但也可以指定不同的比較函數。在元素等價時，它必須返回 false。例如：

std::multiset<string, std::greater<string>> words{{"dog", "cat", "mouse"}, std::greater<string>()};

這條語句定義了一個以 string 為元素的 multiset，它以 greater<string> 為建構函式的第二個引數。建構函式的第一個引數是一個初始化列表，它為這個容器指定了三個初始元素。和 set 一樣，如果它的兩個元素相等，那麼它們就是匹配的。在一個有比較運算子 comp 的 multiset 中，如果表示式 !(a comp b) && !(b comp a) 為 true，那麼元素 a 和 b 就是相等的。

• multiset 容器和 set 容器有相同的成員函數，但是因為 multiset 可以儲存重複元素，有些函數的表現會有些不同。和 set 容器中的成員函數表現不同的是：
• insert() 總是可以成功執行。當插入單個元素時，返回的疊代器指向插入的元素。當插入一段元素時，返回的疊代器指向插入的最後一個元素。
• emplace() 和 emplace_hint() 總是成功。它們都指向建立的新元素。
• find() 會返回和引數匹配的第一個元素的疊代器，如果都不匹配，則返回容器的結束疊代器。
• equal_range() 返回一個包含疊代器的 pair 物件，它定義了一個和引數匹配的元素段。如果沒有元素匹配的話，pair 的第一個成員是容器的結束疊代器；在這種情況下，第二個成員是比引數大的第一個元素，如果都沒有的話，它也是容器的結束疊代器。
• lower_bound() 返回和引數匹配的第一個元素的疊代器，如果沒有匹配的元素，會返回容器的結束疊代器。返回的疊代器和 range() 返回的 pair 的第一個成員相同。
• upper_bound() 返回的疊代器和 equal_range() 返回的 pair 的第二個成員相同。
• count() 返回和引數匹配的元素的個數。

用 multiset 容器代替 map，實現分析單詞出現次數的程式：

// Determining word frequency
#include <iostream>                               // For standard streams
#include <iomanip>                                // For stream manipulators
#include <string>                                 // For string class
#include <sstream>                                // For istringstream
#include <algorithm>                              // For replace_if() & for_each()
#include <set>                                    // For map container
#include <iterator>                               // For advance()
#include <cctype>                                 // For isalpha()

using std::string;

int main()
{
    std::cout << "Enter some text and enter * to end:n";
    string text_in {};
    std::getline(std::cin, text_in, '*');

    // Replace non-alphabetic characters by a space
    std::replace_if(std::begin(text_in), std::end(text_in), [](const char& ch){ return !isalpha(ch); }, ' ');

    std::istringstream text(text_in);             // Text input string as a stream
    std::istream_iterator<string> begin(text);    // Stream iterator
    std::istream_iterator<string> end;            // End stream iterator

    std::multiset<string> words;                  // Container to store words
    size_t max_len {};                            // Maximum word length

    // Get the words, store in the container, and find maximum length
    std::for_each(begin, end, [&max_len, &words](const string& word){
                words.emplace(word);
                max_len = std::max(max_len, word.length());
    });

    size_t per_line {4},                           // Outputs per line
         count {};                               // No. of words output
 
    for(auto iter = std::begin(words); iter != std::end(words); iter = words.upper_bound(*iter))
    {
        std::cout << std::left << std::setw(max_len + 1) << *iter<< std::setw(3) << std::right << words.count(*iter) << "  ";
        if(++count % per_line == 0)
            std::cout << std::endl;
    }
    std::cout << std::endl;
}

在輸入過程中移除了輸入中的非字母字元。單詞是由 foreach 從 istringstream 物件的文字中提取的，然後把它們傳給了一個 lambda 表示式，這個表示式是 for_each() 的最後一個引數，用來建立 multiset 容器中的元素。

從 text 中獲取的每個單詞都被單獨儲存，因為一般來說，容器中會出現重複的元素。for 迴圈遍歷 multiset 容器 words 中的疊代器，從指向第一個元素的開始疊代器開始。容器中的元素是有序的，因而相等的元素位置是連續的。通過呼叫容器的成員函數 count()，可以獲取和它的引數 iter 所指向元素相等的元素的個數。

每次回圈疊代結束後，iter 被設為 upper_bound() 返回的值，它指向一個不同於當前元素的元素。如果不存在這樣的元素，upper_bound() 會返回容器的結束疊代器，迴圈就此結束。

因為 multiset 中的元素是有序的，所以可以在迴圈中用相等的單詞數量來增加疊代器，例如：

size_t word_count {};   // Number of identical words
for(auto iter = std::begin(words); iter != std::end(words);)
{
    word_count = words.count(*iter);
    std::cout << std::left << std::setw(max_len + 1) << *iter << std::setw(3) << std::right << word_count << " ";
    if(++count % per_line == 0)
        std::cout << std::endl;
    std::advance(iter, word_count);

這種方式比之前的迴圈更好。但這個版本的迴圈結束不是那麼明顯。下面是範例輸出：

Enter some text and enter * to end:
He was saying godnight to his horse.
He was saying goodnight to his horse,
And as he was saying goodnight to his horse,he was saying goodnight to his horse.
"Goodnight horse,goodnight horse",he was saying goodnight to his horse.*
And         1  Goodnight   1  He          2  as          1
godnight    1  goodnight   5  he          3  his         5
horse       7  saying      5  to          5  was         5

儲存派生類物件的指標

我們可能想在 set 或 multiset 容器中儲存派生類物件的指標，可以通過將元素型別指定為基礎類別物件型別的指標來做到這一點。這裡主要擔心的是比較函數，它必須可以比較指向不同型別的派生類物件的基礎類別指標。通常我們會自己定義函數來做這件事，這沒有任何難度。但如何去比較，取決於我們是否對元素順序有任何要求。如果不在乎元素的排序方式，可以使用 owner_less<T> 範例。但需要記住，檢索元素要用指向相同物件的指標，而不是使用相等的物件。讓我們思考一個範例。使用一個 multiset 容器，即使我們沒有重複元素要儲存，但會有一些不同型別的元素。

假設我們想在容器中儲存每個人所擁有的寵物，這裡寵物的型別是由一個派生於基礎類別 Pet 的類定義的。這個類被定義在標頭檔案 Pet_Classes.h 中，程式碼如下：

using std::string;

class Pet
{
protected:
    string name {};

public:
    virtual ~Pet(){}                               // Virtual destructor for base class
    const string& get_name() const { return name;  }

    virtual bool operator<(const Pet& pet) const
    {
        auto result = std::strcmp(typeid(*this).name(), typeid(pet).name());
        return (result < 0) || ((result == 0) && (name < pet.name));
    }
    friend std::ostream& operator<<(std::ostream& out, const Pet& pet);
};

需要注意 Pet 類的成員函數 operator<() 的定義。為了獲得派生類的多型行為，它被指定為虛擬函式。這裡使用了運算子 typeid，它會建立一個 type_info 物件，這個物件封裝了運算元的型別。

使用 typeid 需要包含 typeinfo 標頭檔案。呼叫 type_info 物件的成員函數 name() 會返回一個 C 風格的字串，這是型別名實現定義的一種表示。在此系統上，型別名加上了字首 "class"，因此對於 My_Type 型別的物件，name() 返回的是 "class My_Type"，在你的系統上可能會有所不同。

用定義在 cstring 標頭檔案中的 strcmp() 來比較型別名字串。如果第一個引數小於第二個引數，這個函數會返回一個負數；如果兩個引數相等，返回 0，否則返回一個正數。operator<() 函數會返回兩個表示式或運算後的結果。如果第一個表示式為 true，這個函數總是返回 true。當前物件的型別名小於引數物件的型別名時，會出現這種情況，因而物件主要依靠型別來排序。當第一個表示式是 false 時，這個表示式的結果取決於第二個表示式的結果。當型別名字串相等，且比較運算的左運算元 name 小於右運算元的成員 name 時，第二個表示式才為 true。

返回表示式中對相同型別名的比較非常重要。set 或 map 容器指定的比較運算必須是嚴格弱序的。在其他的條件中，這要求如果 a<b 為 true，那麼 b<a 必須為 false。不比較兩個型別名是否相等。這個返回值的表示式無法滿足這個條件。

當對儲存派生類物件的容器進行排序時，這就可能會導致程式崩潰。你很容易明白這是如何產生的。假設將一個 name 為"Tiddles”的 Cat 物件 cat 和一個 name 為"Rover"的 Dog 物件 dog 比較，因為型別名，表示式 cat < dog 為 true；而表示式 dog < cat 也為 true，因為寵物名。這兩個物件同時小於彼此可能會產生一些問題。

當然可以不使用 strcmp()，可以將 type_info 的成員函數 name() 返回的 null 結尾的字串轉換為 string 檔案型別，然後就可以用 < 運算子比較它們。

Pet_Classes.h 標頭檔案中為輸出流定義的插入運算如下：

inline std::ostream& operator<<(std::ostream& out, const Pet& pet)
{
    return out << "A " <<string {typeid(pet).name()}.erase(0,6) << " called " << pet.name;
}

這段程式碼輸出了型別名和寵物名。型別名字串的表示式首先將 C 風格的字串轉換為 string 型別，然後從 string 移除前 6 個字元 "class”。如果你的系統使用的是不同的型別名，需要對程式碼做一些修改。

為簡單起見，定義三個派生於 Pet 的類：Cat、Dog 和 Mouse。除了型別不同外，它們的定義在本質上是相同的。Dog 類的定義如下：

class Dog : public Pet
{
public:
    Dog() = default;
    Dog(const string& dog_name)
    {
        name = dog_name;
    }
};

在這個建構函式中，初始化了繼承的成員變數。所有派生類的定義都在 Pet 標頭檔案中。

定義容器

用 multiset 容器儲存 shared_ptr<Pet> 物件，可以用兩個 using 指令來為它們指定型別別名：

using Pet_ptr = std::shared_ptr<Pet>; // A smart pointer to a pet
using Pets = std::multiset<Pet_ptr>; //A set of smart pointers to pets

Pet_ptr 別名簡化了 multiset 容器的定義，Pets 別名簡化了 map 容器的定義。這裡會用 map 容器來儲存 multiset 容器，並以人名作為 map 的鍵。Pets 容器可以儲存 Pet 物件的指標，也能儲存 Cat、Dog、Mouse 物件的指標。

需要為 Pet_ptr 物件的 multiset 容器定義一個小於運算子：

inline bool operator< (const Pet_ptr& p1, const Pet_ptr& p2)
{
    return *p1 < *p2;
}

這裡解除參照傳入的指標引數，然後將解除參照得到的物件傳入 Pet 派生類的虛擬函式 operator<()。在這個範例中，multiset 容器預設的函數物件 less<Pet_ptr> 會呼叫上面這個函數。

這裡有兩個更有用的 using 用法：

using std::string;
using Name = string;

Name 的別名可以使 map 容器的鍵型別更加清楚明白。在 main() 中按如下方式定義 map:

std::map<Name, Pets> peoples_pets;

容器中的元素是 pair<Name, Pets> 物件，它的完整形式是 pair<string, multiset<shared_ptr <Pet>>，後面這種表示形式不是那麼直觀。

定義範例的main()函數

用輔助函數從標準輸入流讀取人名和他們的寵物:

// Read in all the pets for a person
Pets get_pets(const Name& person)
{
    Pets pets;
    std::cout << "Enter " << person << "'s pets:n";
    char ch {};
    Name name {};
    while(true)
    {
        std::cin >> ch;
        if(toupper(ch) == 'Q') break;
        std::cin >> name;
        switch(std::toupper(ch))
        {
            case 'C':
                pets.insert(std::make_shared<Cat>(name));
                break;
            case 'D':
                pets.insert(std::make_shared<Dog>(name));
                break;
            case 'M':
                pets.insert(std::make_shared<Mouse>(name));
                break;
            default:
                std::cout << "Invalid pet ID - try again.n";
        }
    }
    return pets;
}

程式碼雖然看起來很多，但都很簡單。首先會建立一個 Pets 型別的區域性 multiset 容器。將人名作為引數傳入函數，作為輸入提示，然後在一個死迴圈中讀入他的寵物。用首字母來定義寵物的型別——'C' 是貓，'D' 是狗，以此類推。在 main() 中會為這種表示方式建立一個提示。型別字元後面是寵物的名字，輸入 'Q' 會結束當前輸入。swich 語句會建立適當型別的 shared_ptr<T> 物件，然後把它儲存到 pets 容器中。當輸入結束時，會以移動運算的方式返回區域性物件 pets。

程式會輸出 Pets 容器中的寵物，因此這裡需要實現一個流插入運算子：

// Stream insertion operator for pointers to pets
inline std::ostream& operator<<(std::ostream& out, const Pet_ptr& pet_ptr)
{
  return out << " " << *pet_ptr;
}

解除參照智慧指標，然後用插入運算子將物件寫入流 out。因此這裡會呼叫 Pet 類的友元函數 operator<<()。為了輸出 map 容器中的元素，在另一個函數的定義中使用它:

// REad all the pets for a given person
void list_pets(const std::pair<Name, Pets>& pr)
{
    std::cout << "n" << pr.first << ":n";
    std::copy(std::begin(pr.second), std::end(pr.second), std::ostream_iterator<Pet_ptr>(std::cout, "n"));
}

元素是 pair 物件，它的第一個成員是人名，第二個成員是一個 multiset 容器，裡面包含了指向寵物的指標。在將 pair 的第一個成員輸出到標準輸出流後，用 copy() 演算法輸出第二個成員的元素。copy() 的前兩個引數都是疊代器，它們定義了拷貝元素的範圍。第三個引數指定了拷貝操作的目的地，是一個 ostream_iterator<Pet_ptr> 物件。然後呼叫 operator<<() 函數，將 Pet_ptr 作為它的第二個引數，這個函數然後會呼叫 Pet 類的友元函數 operator<<0。

main() 函數的完整程式碼為：

// Storing pointers to derived class objects in a multiset container
#include <iostream>                              // For standard streams
#include <string>                                // For string class
#include <algorithm>                             // For copy() algorithm
#include <iterator>                              // For ostream_iterator
#include <map>                                   // For map container
#include <set>                                   // For multiset container
#include <memory>                                // For smart pointers
#include <cctype>                                // For toupper()
#include "Pet_Classes.h"

using std::string;
using Name = string;
using Pet_ptr = std::shared_ptr<Pet>;            // A smart pointer to a pet
using Pets = std::multiset <Pet_ptr>;            // A set of smart pointers to pets

// Compare shared pointers to pets
inline bool operator<(const Pet_ptr& p1, const Pet_ptr& p2)
{
  return *p1 < *p2;
}

// Stream insertion operator for pointers to pets
inline std::ostream& operator<<(std::ostream& out, const Pet_ptr& pet_ptr)
{
  return out << " " << *pet_ptr;
}

// Read in all the pets for a person
Pets get_pets(const Name& person)
{
    Pets pets;
    std::cout << "Enter " << person << "'s pets:n";
    char ch {};
    Name name {};
    while(true)
    {
        std::cin >> ch;
        if(toupper(ch) == 'Q') break;
        std::cin >> name;
        switch(std::toupper(ch))
        {
            case 'C':
                pets.insert(std::make_shared<Cat>(name));
                break;
            case 'D':
                pets.insert(std::make_shared<Dog>(name));
                break;
            case 'M':
                pets.insert(std::make_shared<Mouse>(name));
                break;
            default:
                std::cout << "Invalid pet ID - try again.n";
        }
    }
    return pets;
}

// REad all the pets for a given person
void list_pets(const std::pair<Name, Pets>& pr)
{
    std::cout << "n" << pr.first << ":n";
    std::copy(std::begin(pr.second), std::end(pr.second), std::ostream_iterator<Pet_ptr>(std::cout, "n"));
}

int main()
{
    std::map<Name, Pets> peoples_pets;             // The people and their pets
    char answer {'Y'};
    string name {};
    std::cout << "You'll enter a person's name followed by their pets.n"<< "Pets can be identified by C for cat, D for dog, or M for mouse.n"<< "Enter the character to identify each pet type followed by the pet's name.n"<< "Enter Q to end pet input for a person.n";
    while(std::toupper(answer) == 'Y')
    {
        std::cout << "Enter a name: ";
        std::cin >> name;
        peoples_pets.emplace(name, get_pets(name));
        std::cout << "Another person(Y or N)? ";
        std::cin >> answer;
    }

    // Output the pets for everyone
    std::cout << "nThe people and their pets are:n";
    for(const auto& pr : peoples_pets)
        list_pets(pr);
}

在 main() 中定義了人名和寵物的 map 容器後，會有一個提示來說明輸入過程。while 迴圈控制所有輸入。通過呼叫 people_pets 容器的成員函數 emplace() 來向它新增元素，這個函數會在合適的位置建立元素。name 是它的第一個引數，第二個引數是 get_pets() 返回的 multiset 容器。當輸入結束時，通過疊代存取 map 元素的方式，輸出人名及其寵物。用  map 容器的當前 pair 元素作為輔助函數 list_pets() 的引數，輸出每個人的相關資訊。

由於執行結果篇幅過長，文章中不再列舉，讀者可自行執行此完整程式碼檢視執行結果。通過執行程式碼，寵物是以寵物型別名的字母升序輸出的，這和我們期望的一樣。輸出表明我們成功在容器中儲存了指向派生類的基礎類別型別的智慧指標。