multiset 與 multimap 的使用方式

multiset 與 set 的差別

multiset 與 set 唯一的差別就在於 multiset 支援不同的元素有同一個值。也就是說，每一次在 multiset 中插入一個值的時候，multiset 會自動排序好，但並不會刪除重複的值。

multiset 使用方式

標頭檔和 set 一樣使用 <set> 在此只會列出一些不太一樣的地方

初始化

multiset<int> ms; // 這是一個空的 multiset （可以用任意資料型態取代 int）
multiset<int> ms1{1, 2, 3, 2, 1}; // 同 set
multiset<int> ms2 (ms1); // 同 set
multiset<int> ms3 (ms1.begin(), ms1.end()); // 同 set

也可以像 set 一樣使用自定義結構，如下：

struct st {
    int a, b, c;
    bool operator < (const st &y) {
        return a + b + c < y.a + y.b + y.c;
    }
};

int main() {
    multiset<st> ms;
}

數同一個值有多少元素

因為 multiset 有機會有重複的值，multiset 也有定義 count 函式，使用方式如下：

multiset<int> ms{1, 2, 7, 2, 3, 1, 1, 5}
cout << ms.count(1); // 輸出 2

multiset 注意事項

count 時間複雜度

不同於其他函式的 O(log(n)) 時間複雜度，multiset 中的 count 函式的時間複雜度為 O(K + log(n))。

其中 K 代表含有搜尋值的元素個數，而 n 代表 multiset 的元素個數

刪除 multiset 中的元素

如同 set，multiset 也有兩種刪除元素的方式：

multiset<int> ms{1, 1, 2, 2, 2};
ms.erase(ms.find(1)); // 使用迭代器
ms.erase(1); // 刪除所有賦有這個值的元素

這兩種方法所造成的結果不太一樣。

第一個方法會刪除 multiset 之中其中一個 1，而第二個方法會刪除 multiset 裡面所有的 1

multimap 與 map 的差別

multimap 與 map 唯一的差別就在於 multimap 支援不同的元素有同一個鍵值 (key)。 然而，因為同一個鍵值可以對應到不同的元素 / 值，插入與查詢不能使用中括號 []。

multimap 使用方式

標頭檔和 map 一樣使用 <map>

初始化

multimap<int, int> mp; // 這是一個空的 multimap （可以用任意資料型態取代 int）
multimap<int, int> mp{{1, 2}, {1, 3}, {2, 3}, {1, 2}};

插入

此時插入元素的唯一方法就是

mp.insert(pair<int, int> (1, 2));

數同一個值有多少元素

因為 multimap 同一個鍵值可以有多個元素，multimap 也有定義 count 函式，使用方式如下：

multimap<int, int> mp{{1, 2}, {1, 3}, {2, 3}, {1, 2}};
cout << mp.count(1); // 輸出 3

multimap 注意事項

同 multiset，需要注意 count 的複雜度與 erase 的使用方式。