【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)
Sign in with Wallet
Connect another wallet