C/C++教學

C++ std::multimap 用法與範例

本篇將介紹如何使用 C++ std multimap 以及用法，C++ std::multimap 是一個關聯式容器，關聯式容器把鍵值和一個元素連繫起來，並使用該鍵值來尋找元素、插入元素和刪除元素等操作。

multimap 是有排序關聯式容器，即 multimap 容器中所有的元素都會根據鍵值來排序，跟 map 不同的是 multimap 允許鍵值重複，也就是說 multimap 裡同一個鍵值 key 可以對應多個 value，也因為這樣的差異，multimap 跟 map 容器相比下没有提供 [] 運算子與 at() 成員函式。

multimap 的實作方式通常是用紅黑樹(red-black tree)實作的，這樣它可以保證可以在O(log n)時間內完成搜尋、插入、刪除，n為元素的數目。

以下內容將分為這幾部分，

  • multimap 常用功能
  • multimap 初始化
  • multimap 容器插入元素與存取元素
  • multimap 容器的迴圈遍歷
  • 刪除 multimap 指定的元素
  • 清空 multimap 容器
  • 判斷 multimap 容器是否為空
  • 計數 multimap 容器

要使用 multimap 容器的話，需要引入的標頭檔：<map>

multimap 常用功能

C++ multimap 是一種關聯式容器，包含「key鍵值/value資料」成對關係
迭代器
begin()：回傳指向multimap頭部元素的迭代器
end()：回傳指向multimap末尾的迭代器
rbegin()：回傳一個指向multimap尾部的反向迭代器
rend()：回傳一個指向multimap頭部的反向迭代器
容量
empty()：檢查容器是否為空，空則回傳true
size()：回傳元素數量
max_size()：回傳可以容納的最大元素個數
修改器
clear()：刪除所有元素
insert()：插入元素
erase()：刪除一個元素
swap()：交換兩個multimap
查找
count()：回傳指定元素出現的次數
find()：查找一個元素

multimap 初始化

接下來說說怎麼初始化 c++ multimap 容器吧！
先以 int 當 key, int 當 value 的 multimap 為範例，
std::multimap 宣告時要宣告兩個變數類型，
multimap.first：第一個稱為(key)鍵值，在 multimap 裡面，(key)鍵值可以重複
multimap.second：第二個稱為(key)鍵值對應的數值(value)
宣告一個空的 multimap 就這樣寫，

1
std::multimap<int, int> mmap;

multimap 容器初始化的寫法有幾種，如果是先宣告一個 multimap 容器，之後再用 insert() 方式將元素插入的話，寫法如下，

1
2
3
4
std::multimap<int, int> mmap;
mmap.insert(std::pair<int, int>(1, 10));
mmap.insert(std::pair<int, int>(2, 20));
mmap.insert(std::pair<int, int>(3, 30));

或者 std::pair 換成 std::make_pair 就不用寫變數類型，

1
2
3
4
std::multimap<int, int> mmap;
mmap.insert(std::make_pair(1, 10));
mmap.insert(std::make_pair(2, 20));
mmap.insert(std::make_pair(3, 30));

如果更懶都不想寫的話，可以這樣寫，注意使用大括號，

1
2
3
4
std::multimap<int, int> mmap;
mmap.insert({1, 10});
mmap.insert({2, 20});
mmap.insert({3, 30});

如果要宣告 multimap 時順便一起初始化，寫成一行的話可以像這樣寫，

1
2
3
4
5
std::multimap<int, int> mmap = {
    std::pair<int, int>(1, 10),
    std::pair<int, int>(2, 20),
    std::pair<int, int>(3, 30)
};

或者改用 std::make_pair 就不用寫變數類型，

1
2
3
4
5
std::multimap<int, int> mmap = {
    std::make_pair(1, 10),
    std::make_pair(2, 20),
    std::make_pair(3, 30)
};

或者更懶一點的寫法，

1
2
3
4
5
std::multimap<int, int> mmap = {
    {1, 10},
    {2, 20},
    {3, 30}
};

multimap 容器插入元素與存取元素

剛剛在初始化部分已經有示範過了，multimap 容器插入元素是使用 insert() 成員函式來插入元素，

std-map.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// g++ std-multimap.cpp -o a.out -std=c++11
#include <iostream>
#include <map>

int main() {
    std::multimap<int, int> mmap;
    mmap.insert(std::pair<int, int>(1, 10));
    mmap.insert(std::pair<int, int>(2, 20));
    mmap.insert(std::pair<int, int>(3, 30));

    for (const auto& m : mmap) {
        std::cout << m.first << ", " << m.second << "\n";
    }
    return 0;
}

插入完印出來的結果如下，

1
2
3
1, 10
2, 20
3, 30

multimap 容器的迴圈遍歷

迴圈遍歷 multimap 容器的方式有幾種，以下先介紹使用 range-based for loop 來遍歷 multimap 容器，
這邊故意將鍵值不按順序初始化或者插入，先插入 1、3、2、4、2 key 鍵值的元素，
然後我們再來觀察看看是不是 multimap 會將其排序，

std-map2.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// g++ std-multimap2.cpp -o a.out -std=c++11
#include <iostream>
#include <map>

int main() {
    std::multimap<int, int> mmap = {
        std::make_pair(1, 10),
        std::make_pair(3, 30),
        std::make_pair(2, 23),
        std::make_pair(4, 40),
        std::make_pair(2, 20)
    };

    for (const auto& m : mmap) {
        std::cout << m.first << ", " << m.second << "\n";
    }
    return 0;
}

輸出內容如下，從這個輸出結果發現是 key 鍵值由小到大排列，所以 multimap 跟 map 容器一樣是會幫你排序的，
在插入元素的同時會根據鍵值來進行排序，

1
2
3
4
5
1, 10
2, 23
2, 20
3, 30
4, 40

使用前向迭代器，輸出結果跟上列相同，

1
2
3
4
5
for (std::multimap<int, int>::iterator it = mmap.begin(); it != mmap.end(); it++) {
// or
// for (auto it = mmap.begin(); it != mmap.end(); it++) {
    std::cout << (*it).first << ", " << (*it).second << "\n";
}

使用反向迭代器的例子，如果嫌 iterator 迭代器名稱太長的話可以善用 auto 關鍵字讓編譯器去推導該變數類型，

1
2
3
4
5
// for (std::multimap<int, int>::reverse_iterator it = mmap.rbegin(); it != mmap.rend(); it++) {
// or
for (auto it = mmap.rbegin(); it != mmap.rend(); it++) {
    std::cout << (*it).first << ", " << (*it).second << "\n";
}

反向迭代器的輸出結果如下，反著印出來，

1
2
3
4
5
4, 40
3, 30
2, 20
2, 23
1, 10

刪除 multimap 指定的元素

刪除 multimap 指定的元素要使用 erase()，

std-multimap5.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// g++ std-multimap5.cpp -o a.out -std=c++11
#include <iostream>
#include <map>

int main() {
    std::multimap<int, int> mmap;
    mmap.insert(std::pair<int, int>(1, 10));
    mmap.insert(std::pair<int, int>(2, 20));
    mmap.insert(std::pair<int, int>(2, 23));
    mmap.insert(std::pair<int, int>(3, 30));

    mmap.erase(1);
    for (const auto& m : mmap) {
        std::cout << m.first << " " << m.second << "\n";
    }

    std::cout << "---\n";

    mmap.erase(2);
    for (const auto& m : mmap) {
        std::cout << m.first << " " << m.second << "\n";
    }

    return 0;
}

結果如下，

1
2
3
4
5
2 20
2 23
3 30
---
3 30

那如果 multimap 刪除不存在的元素會發生什麼事呢？

std-multimap6.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// g++ std-multimap6.cpp -o a.out -std=c++11
#include <iostream>
#include <string>
#include <map>

int main() {
    std::multimap<int, int> mmap;
    mmap.insert(std::pair<int, int>(1, 10));
    mmap.insert(std::pair<int, int>(2, 20));
    mmap.insert(std::pair<int, int>(2, 23));
    mmap.insert(std::pair<int, int>(3, 30));

    auto ret = mmap.erase(2);
    std::cout << ret << "\n";
    for (const auto& m : mmap) {
        std::cout << m.first << " " << m.second << "\n";
    }

    std::cout << "---\n";

    ret = mmap.erase(4);
    std::cout << ret << "\n";
    for (const auto& m : mmap) {
        std::cout << m.first << " " << m.second << "\n";
    }

    return 0;
}

multimap 刪除不存在的元素並不會造成什麼 crash 這種嚴重問題，他反而會回傳一個數量告訴你它刪除了多少個元素，以這個例子來說 erase(2) 是刪除了 2 個元素，erase(4) 是刪除了 0 個元素，結果如下，

1
2
3
4
5
6
7
2
1 10
3 30
---
0
1 10
3 30

清空 multimap 容器

要清空 multimap 容器的的話，要使用 clear()，

1
2
3
4
5
6
std::multimap<int, int> mmap;
mmap.insert(std::pair<int, int>(1, 10));
mmap.insert(std::pair<int, int>(2, 20));
mmap.insert(std::pair<int, int>(3, 30));

mmap.clear();

判斷 multimap 容器是否為空

要判斷 multimap 是否為空或是裡面有沒有元素的話，可以用 empty()，寫法如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::multimap<int, int> mmap;

if (mmap.empty()) {
    std::cout << "mmap is empty.\n";
} else {
    std::cout << "mmap is not empty, size is " << mmap.size() << ".\n";
}

mmap.insert(std::pair<int, int>(1, 1));

if (mmap.empty()) {
    std::cout << "mmap is empty.\n";
} else {
    std::cout << "mmap is not empty, size is " << mmap.size() << ".\n";
}

輸出結果如下，insert() 一個元素後 size 變成 1，

1
2
mmap is empty.
mmap is not empty, size is 1.

計數 multimap 容器

要計算 multimap 裡某鍵值的數量有幾個的話，可以用 count()，寫法如下，

1
2
3
4
5
std::multimap<int, int> mmap{ {1, 10}, {2, 20}, {2, 23}, {3, 30} };

std::cout << mmap.count(1) << "\n";
std::cout << mmap.count(2) << "\n";
std::cout << mmap.count(3) << "\n";

輸出結果如下，鍵值為 2 的有兩個，

1
2
3
1
2
1

其它參考
std::multimap - cppreference.com
https://en.cppreference.com/w/cpp/container/multimap
multimap - C++ Reference
https://www.cplusplus.com/reference/map/multimap/
multimap 類別 | Microsoft Docs
https://docs.microsoft.com/zh-tw/cpp/standard-library/multimap-class?view=msvc-160

其它相關文章推薦
如果你想學習 C++ 相關技術，可以參考看看下面的文章，
C/C++ 新手入門教學懶人包
std::map 用法與範例
std::unordered_map 用法與範例
std::vector 用法與範例
std::deque 介紹與用法
std::queue 用法與範例