---
# System prepended metadata

title: 【C++】競程筆記（資料結構：map）
tags: [資料結構, 程式設計, C++, 競程, 排序, CP]

---

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

[TOC]

程式碼範例參考：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）

```
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。

```cpp=
#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 apple
2 banana
```

### 存取操作

```cpp=
#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：

```
using [] : apple
using at() : apple
```

### 插入操作

```cpp=
#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 apple
2 banana
3 cherry
4 date
```

### 搜尋操作

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

```cpp=
#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：

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

### 刪除操作

```cpp=
#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：

```
Original Data :
101 -> 王奕翔
102 -> LukeTseng
103 -> 歐金金
104 -> 白冰冰

Delete after :
104 -> 白冰冰
```

### 遍歷方式

1. range-based for loop
2. for loop

```cpp=
#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：

```
apple : 3
banana : 5
orange : 2
---------------
apple : 3
banana : 5
orange : 2
```

multimap
---

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

用法也與 map 一樣。

語法：

```
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);`
:::

```cpp=
#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?

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

```
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 上面。

```cpp=
#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](https://www.geeksforgeeks.org/cpp/multimap-associative-containers-the-c-standard-template-library-stl/)

[Map in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/cpp/map-associative-containers-the-c-standard-template-library-stl/)

[C++ 容器类 <map> | 菜鸟教程](https://www.runoob.com/cplusplus/cpp-libs-map.html)