【C++】競程筆記（資料結構：map）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

簡介

map 是 C++ STL 裡面的一個容器，跟 set 一樣都是關聯式容器（Associative Container），他用鍵值對（Key & Value）的方式來存資料，並自動依 key 的順序進行排序（預設為升序）。

可以想成 Python 的 dictionary，但有點不一樣。

鍵值對就是 key 對應一個 value，如：{1, "apple"}，1 這個 key 會對應到 apple，輸入 1 時就會輸出 apple。

map 的底層結構也是基於紅黑樹的自平衡二元搜尋樹。

特性

  • 唯一性：
    • key 不能重複。
  • 元素型態：
    • pair<const Key, T>，key 為常數。
  • 不支援隨機存取：
    • 只能透過 iterator 遍歷容器。
  • 雙向迭代器：
    • 可向前向後遍歷元素，表示可用 rbegin() 跟 rend() 反向迭代器。

語法（Syntax）

1
map<key_type, value_type, comp> m;

key_type：key 的資料型態。

value_type：value 的資料型態。

comp：比較函式，改降序一樣用 greater<key_T>，key_T 是 key 的資料型態。

m：map 的名稱。

標頭檔

使用前須引入標頭檔 <map>

基本操作

  • 存取操作：

    • [key]：如 m["apple"]。
    • at(key)：與 [key] 用法一樣，只不過這會做邊界檢查，較為安全。

  • 插入操作：

    • insert({key, val})：插入元素（pair）。
    • emplace(k, v)：比 insert 效能更高。
    • emplace_hint(pos, k, v)：pos 放迭代器，效能比 emplace 更高一點。

  • 搜尋操作：

    • find(key)：回傳指向該元素的 iterator，沒找到元素就會回傳 end()。
    • count(key)：回傳該 key 是否存在（0 不存在；1 存在）。
    • lower_bound(key)：回傳第一個 key >= 指定值的 iterator。
    • upper_bound(key)：回傳第一個 key > 指定值的 iterator。

  • 刪除操作：

    • erase(key)：刪除指定 key 的元素。
    • erase(iterator)：刪除指定位置的元素。
    • erase(first, last)：刪除範圍內所有元素。

遍歷操作的時間複雜度為 $O(n)$ ，以上所有操作皆為 $O(log n)$ 。

  • 元素個數：size()。
  • 檢查容器是否為空：empty()。
  • 清除所有元素：clear()。

操作範例

建立 map

以下遍歷方式是用 range-based for loop：

key：p.first，取得 key。

value：p.second，取得 value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

int main(){
    map <int, string> m1;
    
    map <int, string> m2 ={
        {1, "apple"},
        {2, "banana"},
    };
    
    for (auto& p : m2){
        cout << p.first << " " << p.second << "\n";
    }
    return 0;
}

Output：

1
2
1 apple
2 banana

存取操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>

using namespace std;

int main(){
    map <int, string> m = {
        {1, "apple"},
    };
    
    cout << "using [] : " << m[1] << '\n';
    
    cout << "using at() : " << m.at(1);
    
    return 0;
}

Output：

1
2
using [] : apple
using at() : apple

插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;

int main(){
    map <int, string> m = {
        {1, "apple"},
    };
    
    m.insert({2, "banana"});
    
    m.emplace(3, "cherry");
    
    m.emplace_hint(m.end(), 4, "date");
    
    for (auto& p : m){
        cout << p.first << " " << p.second << '\n';
    }
    
    return 0;
}

Output：

1
2
3
4
1 apple
2 banana
3 cherry
4 date

搜尋操作

map <int, string> 的 iterator 是指向 pair <const int, string> 這個指標物件，所以用 it->second or it->first。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

int main() {
    map<int, string> students;
    
    students[101] = "Luke";
    students[103] = "醜男";
    students[105] = "王奕翔";

    int key = 103;

    auto it = students.find(key);
    if (it != students.end()) {
        cout << "find(): Found student ID " << key << " -> " << it->second << endl;
    } else {
        cout << "find(): Student ID " << key << " not found" << endl;
    }

    if (students.count(key)) {
        cout << "count(): Student ID " << key << " exists" << endl;
    } else {
        cout << "count(): Student ID " << key << " does not exist" << endl;
    }

    auto lb = students.lower_bound(102);
    if (lb != students.end()) {
        cout << "lower_bound(102): Found student ID " << lb->first << " -> " << lb->second << endl;
    } else {
        cout << "lower_bound(102): No such student ID >= 102" << endl;
    }

    auto ub = students.upper_bound(103);
    if (ub != students.end()) {
        cout << "upper_bound(103): Found student ID " << ub->first << " -> " << ub->second << endl;
    } else {
        cout << "upper_bound(103): No such student ID > 103" << endl;
    }

    return 0;
}

Output：

1
2
3
4
find(): Found student ID 103 -> 醜男
count(): Student ID 103 exists
lower_bound(102): Found student ID 103 -> 醜男
upper_bound(103): Found student ID 105 -> 王奕翔

刪除操作

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
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

int main() {
    
    map<int, string> students;
    
    students[101] = "王奕翔";
    students[102] = "LukeTseng";
    students[103] = "歐金金";
    students[104] = "白冰冰";

    cout << "Original Data :\n";
    
    for (const auto& pair : students)
        cout << pair.first << " -> " << pair.second << '\n';

    students.erase(102);

    auto it = students.find(103);
    if (it != students.end())
        students.erase(it);

    it = students.begin();
    auto last = students.end();
    --last;
    students.erase(it, last);

    cout << "\nDelete after :\n";
    for (const auto& pair : students)
        cout << pair.first << " -> " << pair.second << '\n';

    return 0;
}

Output：

1
2
3
4
5
6
7
8
Original Data :
101 -> 王奕翔
102 -> LukeTseng
103 -> 歐金金
104 -> 白冰冰

Delete after :
104 -> 白冰冰

遍歷方式

  1. range-based for loop
  2. for loop
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
#include <bits/stdc++.h>

using namespace std;

int main() {
    map<string, int> m;
    
    m["apple"] = 3;
    m["banana"] = 5;
    m["orange"] = 2;

    for (const auto& pair : m) {
        // pair 是一個 key-value 對，pair.first 是 key，pair.second 是 value
        cout << pair.first << " : " << pair.second << endl;
    }
    
    cout << "---------------" << endl;
    
    for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it) {
        // it 是一個指向 pair 的 iterator，要用 -> 取值
        cout << it->first << " : " << it->second << endl;
    }

    return 0;
}

Output：

1
2
3
4
5
6
7
apple : 3
banana : 5
orange : 2
---------------
apple : 3
banana : 5
orange : 2

multimap

就跟 set 有 multiset 一樣，multimap 可以有重複的 key。

用法也與 map 一樣。

語法：

1
multimap <key_type, value_type, comp> mm;

習題練習

Uva 10226 Hardwood Species

Source：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1167

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=d492

單字：

  • botanical (adj.)：植物（學）的；和植物（學）有關的。
  • broad leaves 指的是寬大的葉子。
  • dormant (adj.)：蟄伏的，沉睡的，休眠的。
  • certain：某、某些、某個。
  • oak (n.)：橡木。
  • conifer (n.)：針葉樹。
  • cedar (n.)：雪松。
  • fir (n.)：冷杉、樅。
  • hemlock (n.)：毒參。
  • pine (n.)：松樹。
  • spruce (n.)：雲杉。
  • cypress (n.)：柏樹。
  • lumber (v.)(n.)：緩慢地移動；木材、木料。

cin 不會吃掉 "\n"，然後我懶得用 cin.ignore()，所以用了一個取巧的方式，就是都用 getline(cin, line)，然後第一次就將 n = stoi(line)，強制把 line 的數字轉整數指定給 n。

第二次讀取空行，也沒差。

在 C++ 控制小數位數的話，則用到：

:::info
fixed、setprecision() 皆為 manipulator（操縱器），定義於 <iomanip> 標頭檔中，

fixed 指示 cout 用固定點表示法（fixed-point notation）顯示浮點數，表示會顯示 123.4567，而非科學記號的 1.234567e+02。

用 fixed 將小數點固定後，再由指定小數位數有幾位的 setprecision() 控制。

所以若僅顯示 4 位小數點，則寫成：

cout << fixed << setprecision(4);
:::

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
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n;
    string line;
    getline(cin, line);
    n = stoi(line);
    getline(cin, line);
    
    for (int i = 0; i < n; ++i){
        map <string, int> counts;
        int total = 0;
        
        while (getline(cin, line)){
            if (line.empty()) break;
            counts[line]++;
            total++;
        }
        
        for (auto &p : counts){
            cout << fixed << setprecision(4);
            cout << p.first << " " << (p.second * 100.0 / total) << '\n';
        }
        
        if (i != n - 1){
            cout << '\n';
        }
        
    }
    
    return 0;
}

Playlist

Source：https://cses.fi/problemset/task/1141

單字：

  • successive (adj.)：接連的，連續的。

註：作者第一次看到跟腦袋想得不一樣的單字XD，還以為是成功的意思。

該題用 map 結合雙指標滑動窗口的方式去解。

Why Sliding Window?

核心就在敘述之中！

What is the longest sequence of successive songs where each song is unique?

以下是用範例測資來做滑動窗口的示意：

1
2
8
1 2 1 3 2 7 4 2
  1. 12。
  2. 121 -> 去掉最前面的 1，變成 21。
  3. 2132 -> 去掉最前面的 2，變成 132。
  4. 13274 -> 即為答案

那為了避免還出現在不重複的窗口中，所以索引要 + 1（last_index[song] + 1），如 121 去掉最前面的 1 變成 21，索引要在 2 上面。

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
29
30
31
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> songs(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> songs[i];
    }

    map<int, int> last_index; // 紀錄每首歌最後出現的位置
    int left = 0, max_len = 0; 

    for (int right = 0; right < n; ++right) {
        int song = songs[right];
        if (last_index.count(song)) {
            // 若這首歌出現過，並且位置在目前 left 之後
            left = max(left, last_index[song] + 1);
        }
        last_index[song] = right; // 更新這首歌的最新位置
        max_len = max(max_len, right - left + 1); // 計算最大長度
    }

    cout << max_len;
    return 0;
}

參考資料

Multimap in C++ STL - GeeksforGeeks

Map in C++ STL - GeeksforGeeks

C++ 容器类| 菜鸟教程