# CPP Lecture4
- __學習++動態序列容器++、++指標++、++記憶體管理++__
- __STL 的 `<vector>` 怎麼使用？與陣列差在哪？__
- __何謂`指標（Pointer）`? 如何宣告/初始化?__
- __記憶體怎麼管理？為何要管理記憶體？__
---
#### 動態序列容器 (`vector`)
> 使用前必須 `#include <vector>` 函式庫
> 這是來自 `STL` (Standard Template Library) 的其中一個常用模板/容器
1. `vector`：可變陣列大小的序列容器。
2. `vector` 可以當作是++陣列的升級版++：
支援動態分配、高效地對記憶體進行管理
3. 底層實現是一個++連續++記憶體空間。
4. 當容量不夠的時候就會重新申請空間，
並把原本資料複製或搬移到新的空間。
---
### ➣ 陣列 v.s. 動態序列容器 (`vector`)
> 在看 `vector` 之前先來跟陣列做個比對，為何++傳統陣列++ ==不好用==
<br/>
- 大小：
- `int[]`：在宣告時固定、無法更動。
- `vector`：可以動態調整，支援自動伸縮。
- 記憶體：
- `int[]`：需自行管理空間 (++`new`/`delete`++)。
- `vector`：不需手動釋放記憶體。
- 安全性：
- `vector`：`at()` 查找方法，避免索引錯誤。
- 內建方法:
- `vector`：`push_back`, `pop_back`, `clear` ...
---
#### 陣列 v.s. 動態序列容器 (`vector`) - 宣告範例
<br/>
- 陣列的宣告：
```cpp[]
int arr1[5]; // 給定大小
int arr2[5] = {1, 2, 3, 4, 5}; // 給定大小
int arr3[] = {1, 2, 3, 4, 5}; // 同樣給定大小 只是由編譯器判定
```
- `vector` 的宣告：
- 語法： `vector<元素型態> 名稱;`
```cpp[]
vector<int> vec1; // 不需給定大小
vector<int> vec2 = {1, 2, 3, 4, 5}; // 大小容器會自動管理
vector<int> vec3; // 後續拿來新增元素
for (int i = 1; i <= 5; ++i) vec3.push_back(i); // 放一個數值到尾端
// 經過 for 迴圈: vec3 也是等於了 {1, 2, 3, 4, 5}
```
---
- `vector` 的初始化：
<br/>
1. 宣告空 `vector` 以 `push_back` 將資料推進去
```cpp[]
vector<int> vec;
v.push_back(1);
v.push_back(2);
v.push_back(3);
```
2. 括弧式初始化：（需要編譯器支援）
```cpp[]
vector<int> v1 = {1, 2, 3}; // 與陣列相同的方式來初始化
vector<int> v2({1, 2, 3}); // 以`建構函數`來傳入參數以初始化
```
3. 容器複製當作初始值：
```cpp[]
vector<int> v1 = {1, 2, 3};
vector<int> v2 = v1;
// 或者
vector<int> v3 = {4, 5, 6};
vector<int> v4(v3);
```
---
- `vector` 的初始化：
<br/>
4. 複製 `vector` 指定範圍，用到 `begin()`,`end()`
```cpp[]
vector<int> v1 = {1, 2, 3, 4, 5};
vector<int> v2(v1.begin() + 2, v1.end() - 1); // {3, 4}
// 指標概念 v1 的起始地址 + 2 是 3 ~ 結束地址 - 1 是 4
```
5. 傳統陣列複製當作初始值：
```cpp[]
int arr[] = {1, 2, 3, 4, 5};
vector<int> vec(arr, arr + 3);
// *指標概念: arr 的起始地址 ~ arr + 3 的地址
for (const auto& n : vec) cout << n << endl; // 輸出: 1 2 3
```
6. 均一化初始（`建構函數`）
```cpp[]
int n = 10;
int val = 0;
int vec(n, val); // (數量, 值)
for (const auto& x : vec) cout << x << endl; // 初始化成 n 個 val
// 輸出: 0 0 0 0 0 0 0 0 0 0
```
---
#### 陣列 v.s. 動態序列容器 (`vector`) - 索引範例
- 陣列索引：
```cpp[]
int arr[] = {1, 2, 3};
cout << arr[0] << " "; // 1
cout << arr[1] << " "; // 2
cout << arr[2] << " "; // 3
cout << arr[3] << " "; // 索引超出預設範圍 => random number
```
- `vector` 索引：
```cpp[]
vector<int> vec = {1, 2, 3};
cout << vec[0] << " "; // 1
cout << vec.at(0) << " "; // 1
vec[1] = 22; // 更新位置上的元素
cout << vec[1] << " "; // 22
cout << vec.at(1) << " "; // 22
cout << vec[2] << " "; // 3
cout << vec.at(2) << " "; // 3
cout << vec.at(3) << " "; // 邊界檢查抓出錯誤
// throwing an instance of 'std::out_of_range'
```
---
### 動態序列容器 (`vector`) - 內建方法
1. `vector.push_back(val)`：把 val 加到尾端
```cpp[]
vector<int> vec;
vec.push_back(7); // vec = {7}
vec.push_back(9); // vec = {7, 9}
```
2. `vector.pop_back()`：移除尾端元素
```cpp[]
vector<int> vec = {5, 7, 9};
vec.pop_back(); // vec = {5, 7}
vec.pop_back(); // vec = {5}
```
3. `vector.begin()`: 回傳一個 iterator 指向開頭
4. `vector.end()`: 回傳一個 iterator 指向結尾
```cpp[]
vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it)
cout << *it << endl; // 輸出: 1 2 3 4 5
```
> `iterator` (迭代器)：++智慧指標++，允許程式以統一方式遍歷容器中的各個元素。
---
#### 動態序列容器 (`vector`) - 內建方法
<br/>
5. `vector.insert(it, val)`：指定位置插入 val
```cpp[]
vector<int> vec = {10, 20, 30};
vec.insert(vec.begin() + 1, 15); // 在起始位址 + 1 的地址插入整數 15
for (const auto& x : vec) cout << x << endl;
// 輸出: 10 `15` 20 30
vec.insert(vec.end() - 1, {21, 24, 27}); // 在尾端位置 - 1 的地址插入多個整數: 21, 24, 27
for (const auto& x : vec) cout << x << endl;
// 輸出: 10 15 20 `21 24 27` 30
```
6. `vector.erase(it)`：指定位置元素移除
```cpp[]
vector<int> vec = {2, 3, 6, 8};
vec.erase(vec.end());
for (const auto& x : vec) cout << x << endl;
// 輸出: 2 3 6
vec.erase(vec.begin());
for (const auto& x : vec) cout << x << endl;
// 輸出: 3 6
```
---
#### 動態序列容器 (`vector`) - 內建方法
<br/>
7. `vector.clear()`：清空整個容器裡所有元素
```cpp[]
vector<int> vec = {10, 20, 30, 40, 50};
vec.clear();
cout << "vec 內容: ";
for (const auto& x : vec) cout << x << " ";
cout << endl;
```
8. `vector.size()`：回傳目前容器長度
```cpp[]
vector<int> vec = {2, 3, 7, 8};
cout << vec.size() << endl; // 輸出: 4
```
9. `vector.empty()`：回傳目前容器是否為空
```cpp[]
vector<int> vec = {2, 3, 7, 8};
cout << vec.empty() << endl; // 輸出: 0
vec.clear(); // 清空 vec
cout << vec.empty() << endl; // 輸出: 1
```
---
#### 🧪 小測驗 A - 串接陣列
- 實作 `merge(v1, v2)` 回傳串接後的 `vector`
- 將兩個 `vector<int>` 合併並排序後返回結果
- 範例:
```cpp[]
merge({1, 2}, {3, 4}) -> return {1, 2, 3, 4}
```
::: spoiler ▼ 詳解
```cpp[]
vector<int> merge(vector<int> v1, vector<int> v2) {
for (const auto& x : v2) v1.push_back(x);
return v1;
}
```
:::
---
#### 🧪 小測驗 B - `vector` 中最長字串
- 設計一個程式，使用 `vector` 儲存字串。
- 找出最長的字串。
- 範例：
```cpp[]
getLongestString({
"ab",
"abc",
"abcd",
"",
}) -> 返回 "abcd"
```
::: spoiler ▼ 詳解
```cpp[]
string getLongestString(vector<string> v) {
int max_index = 0, max_length = 0;
for (int i = 0; i < v.size(); ++i) {
if (max_length < v[i].length()) {
max_length = v[i].length();
max_index = i;
}
} return v[max_index];
}
```
:::
---
### ⌀ 多維動態序列 (`vector`)
- ++多維動態序列++指的是使用 `vector` 作為元素
再把這些 `vector` 組合成一個更高維度的容器。
- 例如，++二維++動態序列可宣告為：
```cpp[]
vector<vector<int>> my_2d_vector;
```
- ++三維++動態序列則是：
```cpp[]
vector<vector<vector<int>>> my_3d_vector;
```
---
#### ⌀ 多維動態序列 - 宣告與初始化
> 可以發現到 `vector` 與 `type[]` 傳統陣列的不同：元素陣列++不需要等長++
1. 直接宣告方法：
```cpp[]
vector<vector<int>> vec = { // 一個長度為 4 的 vector 二維動態序列
{1, 2, 3, 4}, // 每一個一維元素都是 int
{5, 6, 7},
{8, 9},
{10},
}; // 每個二維元素皆為 vector<int>
```
2. 均一化初始化：
```cpp[]
// 宣告一個 3x4 的二維整數 vector，並將所有值初始化為 5
vector<vector<int>> matrix( 3, vector<int>(4, 5) );
```
```cpp[]
// 宣告一個 2x3x4 的三維整數 vector，單維元素初始值都為 5
vector<vector<vector<int>>> cube(2,
vector<vector<int>>(3,
vector<int>(4,
5)
)
);
```
---
#### ⌀ 多維動態序列 - 基本操作
> `[x]` 叫做下標運算子，表示對左值上向量的第 `x` 位取值
- 存取元素：
```cpp[]
vector<vector<int>> matrix(4, vector<int>(4, 0)); // 4 x 4 元素皆初始為 0 的矩陣
int i = 2, j = 3;
matrix[i][j] = 42; // 將第 i 列第 j 行的元素設為 42
cout << matrix[i][j] << endl; // 42
```
- 增加元素：
```cpp[]
// push_back() 函數在一個 vector 的末尾添加一個元素
vector<vector<int>> vec = {
{1, 2, 3},
{4, 5, 6}
};
vec[1].push_back(7);
// vec => {{1, 2, 3}, {4, 5, 6, 7}}
```
- 調整大小：
```cpp[]
// resize() 方法來改變 vector 的大小
vector<vector<int>> matrix(8, vector<int>(6, 4));
matrix.resize(5); // 將 matrix 的列數改為 5，不足或多餘的部分會用預設值初始化
```
---
#### ⌀ 多維動態序列 - 進階操作
<br/>
```cpp[]
vector<vector<char>> vec = { // 以此非矩形資料為例
{'a'},
{'a', 'b'},
{'a', 'b', 'c'},
{'a', 'b', 'c', 'd'},
{'a', 'b', 'c', 'd', 'e'},
};
```
- 巢狀遍歷：
```cpp[]
for (int i = 0; i < vec.size(); ++i) {
for (int j = 0; j < vec[i].size(); ++j)
cout << vec[i][j] << " ";
cout << endl;
}
```
- 巢狀++迭代器++：
```cpp[]
for (const auto& v : vec) {// & => 以 reference 的方式來遍歷
for (const char c : v) // char 可以以 auto 代替，編譯器自行判定
cout << c << " ";
cout << endl;
}
```
---
#### ⌀ 多維動態序列 - 常見錯誤
<br/>
- 存取越界：沒有檢查子 `vector` 的大小
就使用下標會導致未定行為：
```cpp[]
vector<vector<int>> matrix(5, vector<int>(3, 111));
int x = -1;
// x = matrix[5][2]; // 會導致崩潰（因 matrix 只有 5 列）
/* 應該先確認大小 */
if (matrix.size() > 5 && matrix[5].size() > 2) x = matrix[5][2];
```
- 大量重複配置記憶體：使用
`push_back(element)` 太頻繁
```cpp[]
/* 提前使用 reserve() 預分配一定的空間 */
std::vector<int> data;
data.reserve(100000); // 預先分配空間，避免多次重新配置 (增加預留空間)
for (int i = 0; i < 100000; ++i) data.push_back(i);
std::cout << "Size: " << data.size() << ", Capacity: " << data.capacity() << std::endl;
```
---
#### 🧪 小測驗 C - 畫對角線
- 請建立一個二維 `vector` 並且
大小由數入整數 N 決定（++ＮＸＮ 矩陣++）
並在對角線上的位置標示 1，其餘標示 0
- 矩陣的結果： 
::: spoiler ▼ 詳解
```cpp[]
int N; cin >> N;
vector<vector<int>> vec(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) vec[i][i] = 1;
for (int i = 0; i < N; ++i) vec[i][N - 1 - i] = 1;
for (const auto& v : vec) {
for (const auto& x : v) cout << x << " ";
cout << endl;
}
```
:::
---
#### 🧪 小測驗 D - 旋轉矩陣
- 讀取兩個整數 N、M，接下來接著讀取 N 行，
每行皆有 M 個整數，將輸入存到二維 `vector`
最後將矩陣++順時針++ 旋轉 90°，並輸出結果：
- 範例：
::: spoiler ▼ 詳解
```cpp[]
int N, M; cin >> N >> M;
vector<vector<int>> vec1, vec2;
for (int i = 0; i < N; ++i) {
vector<int> temp_vec; int temp;
for (int j = 0; j < M; ++j) { cin >> temp; temp_vec.push_back(temp); }
vec1.push_back(temp_vec);
}
for (int c = 0; c < M; ++c) {
vector<int> temp_vec;
for (int r = N - 1; r >= 0; --r) temp_vec.push_back(vec1[r][c]);
vec2.push_back(temp_vec);
}
for (const auto& v : vec2) {
for (const auto& x : v) cout << x;
cout << endl;
}
```
:::
---
#### 🧪 小測驗 D - 降維打擊
- 請設計一個函式，計算一個非矩形的二維向量
每一列的平均值，並回傳所有列平均值
所形成的一維的 `vector<int>`：
- 範例：
```
{{1}, {2, 3}, {4, 5, 6}} => {1, 2.5, 5}
```
::: spoiler ▼ 詳解
```cpp[]
vector<double> avgVector(vector<vector<int>> vec) {
vector<double> result;
for (const auto& v : vec) {
int sum = 0, num = 0;
for (const auto& x : v) { sum += x; num++; }
result.push_back((double)sum / num);
}
return result;
}
```
:::
---
#### ⌀ 多維動態序列 - 小結
- 多維 `vector` 是處理不規則、多重資料結構的一個強大工具。
- 學習如何正確++宣告++、++初始化++以及++遍歷++多維 `vector` 是進階程式設計中的重要技能。
- 要注意++記憶體管理++和++越界問題++，適時使用 `reserve()` 和 `size()` 函式來保證程式的健壯性。
:::info
- 多維 `vector` 中每個子 `vector` 的元素在記憶體中可能並不連續。
- 因此訪問多維 `vector` 的效能不會像一維的連續陣列那樣高效。
:::
---
### 指標 ☞
在 C++ 中，==指標== 也是一種++變數++，
它是用來儲存另一個變數的記憶體位址，因此
可以利用它間接地++存取或修改++該變數的值
> `指標`指向的變數可以是一個 `int`/`double`/`char`....
> 更可以是一個指標：我們稱之為 __指標的指標__
---
#### 指標 - 範例
<br/>
```cpp[]
int var1 = 10;
int *ptr_var1 = &var1; // & 是用取取地址
// int* ptr_var1 = &var1; // 星號在左在右都可以!
cout << ptr_var1 << endl; // 一串任意的十六進位置的地址
// 輸出例如: 0x7fff49b912ac
cout << *ptr_var1 << endl; // * 是用取值，對應地址上存的值
// 輸出: 10
```
- `int* ptr_var1;`：宣告一個指向++整數++的指標。
- `&var1`：取得變數 `var1` 的位址。
- `*ptr_var1`：解參考（dereference）指標，
++取得++或++修改++ `ptr_var1` 所指向的++值++。
---
#### 指標 - 操作
<br/>
📍取得變數的位址：
```cpp[]
int a = 5; // 任意變數
std::cout << &a; // 輸出 a 的記憶體位址
```
📎解參考指標：
```cpp[]
double a = 6.0; // 任意變數
double* ptr = &a; // 指標 ptr 指向 a 的記憶體位址
// (指標需要指定指向變數的型態)
std::cout << *ptr; // 輸出 6
```
🛠️ 修改指標所指向的值：
```cpp[]
char a = 'b';
char* ptr = &a;
*ptr = (char)69;
std::cout << a; // 輸出 E
```
---
#### 指標 - 常見錯誤⚠️
<br/>
- ❌ 未初始化的指標：
```cpp[]
int* ptr; // 未初始化，ptr 指向未知位置
*ptr = 10; // 未定義行為，可能導致程式崩潰
```
:::success
解法：在使用指標前，務必++初始化++
:::
- ❌ 空指標解參考
```cpp[]
int* ptr = nullptr;
*ptr = 10; // 錯誤：解參考空指標
```
:::success
解法：在++解參考++前，檢查指標是否為 `nullptr`
:::
---
#### 指標 - 陣列指標
> 還記得 ==陣列== 是一個`連續`的++記憶體空間++嗎，儲存`連續資料`
> 所以陣列++第N個元素++的地址 + 1 不就等於 ++第 N+1 個元素++嗎?
> （編譯器很聰明 寫 `+1` 時編譯器會知道那個元素有多大）
所以依據陣列連續性的特性，
++陣列名++可以視為指向其第一個元素的`指標`。
```cpp[]
int arr[3] = {1, 2, 3};
int* ptr = arr; // arr 本身就是一個指標，指向陣列的第零個元素
std::cout << *(arr + 1) << endl; // 輸出 2
std::cout << *(ptr + 1) << endl; // 輸出 2
```
但雖然 `vector` 也是連續序列，一個 `vector` 本身
變數的位址與其管理的序列是不連續的
```cpp[]
vector<int> vec = {2, 4, 6};
vector<int> *ptr = &vec;
cout << *(&vec[0] + 2) << endl; // 輸出: 6
cout << *(&(*ptr)[0] + 2) << endl; // 輸出: 6
// 為何? 相信以下能解答疑惑
cout << "vector 容器位址: " << &vec << ", 容器所管理的頭元素: " << &vec[0] << endl;
cout << &vec[1] << ", " << &vec[2] << endl; // 元素間依然是連續的
```
---
#### 指標 - 迴圈陣列指標
<br/>
> 使用`指標`也是可以++遍歷陣列++
- 由頭至尾：
```cpp[]
int arr[] = {1, 2, 3, 4, 5};
for (int* ptr = arr; ptr < arr + 5; ++ptr) {
std::cout << *ptr << " ";
} cout << endl;
// 或者這樣寫:
for (auto ptr = arr; ptr < arr + sizeof(arr) / sizeof(int); ++ptr) {
std::cout << *ptr << " ";
} cout << endl;
// 輸出：1 2 3 4 5
```
- 由尾至頭：
```cpp[]
char arr[] = {'1', '2', '3', '4', '5'};
for (char* ptr = &arr[4]; ptr >= arr; --ptr) {
std::cout << *ptr << " ";
}
// 輸出：5 4 3 2 1
```
---
#### 指標 - 變態指標
> `指標`也能玩多種++變形++
🔗 ++指向指標的指標++（雙重指標）：
```cpp[]
int a = 5; // 任意變數
int* ptr = &a; // ptr 指向 a 的位址
int** dptr = &ptr; // 雙重指標 dpter 指向 ptr 本身的位址
std::cout << **dptr; // Output: 5
// 第二個星號對 dptr 解參考得到: *dptr = ptr
// 最後的第一個星號對 ptr 解操考得到: *ptr = 5
```
🔒 ++常數指標++ & ++指向常數的指標++：
```cpp[]
int a = 5;
int b = 10;
// 1. const type* (指向常數的指標)
const int* ptr1 = &a; // 不能透過 ptr1 修改 *ptr1
// 2. type* const (常數指標)
int* const ptr2 = &a; // ptr2 不能指向其他位址
// 3. const type* const (指向常數的常數指標)
const int* const ptr3 = &a; // *ptr3 和 ptr3 都不可修改
```
---
### ✅ 指標小技巧
<br/>
- ++指標變數++：指標是一種變數，用來儲存另一個變數的記憶體位址。
- ++初始化指標++：在宣告指標時，最好立即初始化，避免指向未知位址。
- ++使用 `nullptr`++：C++11 引入了 `nullptr`，用來表示空指標，取代傳統的 `NULL`。
- ++避免野指標++：確保指標在使用前已正確指向有效的記憶體位址。
- ++釋放動態記憶體++：正確配置記憶體，避免記憶體洩漏。 ( 詳見後方「==記憶體管理==」 )
<!-- 釋放動態記憶體：使用 new 配置的記憶體，應使用 delete 釋放，避免記憶體洩漏。 -->
---
#### 🧪 小測驗 E - 兩兩變數值交換
- 請設計一個函式，接受參數如下，請交換兩個變數 a, b 的值：
`swap(整數變數 a, 整數變數 b)`
- 使用範例:
```cpp[]
#include <iostream>
using namespace std;
// swap() ...
int main() {
int a = 7, b = 11;
cout << "a = " << a << ", b = " << b << endl; // a = 7, b = 11
// a, b 經過 swap 函式執行
cout << "a = " << a << ", b = " << b << endl; // a = 11, b = 7
return 0;
}
```
::: spoiler ▼ 詳解
```cpp[]
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
```
:::
---
#### 🧪 小測驗 F - 跨步遍歷
- 請設計函式，接受參數如下，依照規則輸出：
`printRange(整數陣列, 起點, 邊界, 跨步)`
- 範例： _(已確保起點經由跨步會靠近邊界值)_
```cpp[]
int arr[] = {1, 2, 3, 4, 5}; // length: 5
printRange(arr, 0, 5, 2) // -> 輸出: 1 3 5
printRange(arr, 4, -1, -2) // -> 輸出: 5 3 1
```
::: spoiler ▼ 詳解
```cpp[]
void printRange(int* arr, int start, int limit, int step) {
if (step > 0)
for (int i = start; i < limit; i+=step) cout << arr[i] << " ";
else
for (int i = start; i > limit; i+=step) cout << arr[i] << " ";
cout << endl;
}
```
:::
---
#### 🧠 補充 - 函數指標（Function Pointer）
<br/>
- `函數指標`是指向函數的指標，允許將++函數作為變數++傳遞或儲存。
- 主要用以實現++更靈活++的程式設計，例如回呼函數、策略模式等。
- 語法:
```cpp[]
// 宣告一個指向接受兩個 int 並返回 int 的函數的指標
int (*funcPtr)(int, int);
```
也可以使用 `typedef` 或 `using` 來簡化語法：
```cpp[]
typedef int (*FuncType)(int, int);
// 或
using FuncType = int(*)(int, int);
```
---
#### 函數指標 - 範例
<br/>
```cpp[]
#include <iostream>
int add(int a, int b) {
return a + b;
}
int main() {
int (*operation)(int, int) = add; // add函數 作為指標的指向位址
std::cout << operation(5, 3) << std::endl; // 輸出 8
return 0;
}
```
⚠️ 常見錯誤
1. ++型別不匹配++：函數指標的++參數++與++返回型別++必須與所指向的函數++完全一致++。
2. ++未初始化指標++：使用未初始化的函數指標會導致未定義行為。
---
#### 函數指標 - 函數陣列
<br/>
```cpp[]
#include <iostream>
#include <vector>
int add(int a, int b, int c) { return a + b + c; }
int sub(int a, int b, int c) { return a - b - c; }
int main() {
int (*operations[])(int, int, int) = { add, sub }; // 差別就差在 []
std::cout << operations[0](10, 5, 1) << std::endl; // 輸出 16
std::cout << operations[1](10, 5, 1) << std::endl; // 輸出 4
return 0;
}
```
- 語法: `type (*funcptr[])(統一的傳入變數)`
- `type` 是函式的回傳型態
- `funcptr` 是函數陣列的名稱
- 傳入變數陣列內的函式++參數必須統一++
---
#### 函數指標 - 回呼函數
<br/>
```cpp[]
#include <iostream>
void performOperation(int a, int b, int (*operation)(int, int)) {
std::cout << operation(a, b) << std::endl;
}
int multiply(int a, int b) { return a * b; }
int main() {
performOperation(4, 5, multiply); // 輸出 20
return 0;
}
```
- 顧名思義，函數的呼叫是由++另一個函式內部來執行的++
- `函數指標`被當成一個變數來傳入回呼函數
- `回呼函數`內部也必須正確地傳入函數參數
---
### 💡智慧指標 - 迭代器（iterator）
<br/>
前面看了指標的觀念：用來儲存地址的變數
那`迭代器`我們可以解釋為一種++抽象的指標++。
1. 用來遍歷容器（如 `vector`、`list`、`map` 等）中的元素，而不需關心容器的內部實現
2. 提供了一種++統一的方式++來存取容器中的資料，使得演算法可以與容器解耦
3. 講白了就是透過「運算子重載」去指定下個目標資料，讓資料結構不侷限只在於陣列這種連續記憶體管理
---
#### 迭代器 - 定義與使用
<br/>
```cpp[]
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec = {2, 4, 6, 8, 10};
vector<int>::iterator it; // 直接宣告一個空的
// 頭與尾的迭代器
vector<int>::iterator begin1 = vec.begin();
vector<int>::iterator end1 = vec.end() - 1; // .end() 是結尾空指針 必須 -1 回到有元素的尾端
// 或是
auto begin2 = vec.begin();
auto end2 = vec.end() - 1;
cout << "頭元素: " << *begin1 << ", 尾元素: " << *end1 << endl;
cout << "第二個元素: " << *(begin2 + 1) << endl;
cout << "倒數第二個元素: " << *(end2 - 1) << endl;
return 0;
}
```
:::info
可以發現`迭代器`語法/用法跟`指標`差不多
那是因為迭代器重載了我們指標會用到的 ++運算子++
∴ 可以以 ++指標操作++ 相似的方法來使用 `iterator`
:::
---
#### 迭代器 - 迴圈 `vector` 迭代器
> 使用`迭代器`也可以++遍歷 `vector`++：
- 由頭至尾：
```cpp[]
std::vector<int> vec = {1, 2, 3, 4, 5};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
} std::cout << std::endl;
// 或是直接寫 auto
for (auto it = vec.begin(); it != vec.end(); ++it) std::cout << *it << " ";
std::cout << std::endl;
// ** 使用 next(iterator) -> 回傳迭代順序的下一個迭代器 **
for (auto it = vec.begin(); it != vec.end(); it = next(it)) std::cout << *it << " ";
std::cout << std::endl;
```
- 由尾至頭：
```cpp[]
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.end() - 1; it >= vec.begin(); --it) std::cout << *it << " ";
std::cout << std::endl;
// ** 使用 prev(iterator) -> 回傳迭代順序的上一個迭代器 **
for (auto it = vec.end() - 1; it >= vec.begin(); it = prev(it)) std::cout << *it << " ";
std::cout << std::endl;
```
---
#### 迭代器 - `for` 迴圈可迭代遍歷
> 這是自 C++11 引入的 ++語法糖++🍬，讓我們可以更簡潔地遍歷容器或陣列中的元素。
<br/>
- 語法：
```cpp[]
for (declaration : range) { /* 注意到冒號 :，可以看做是 python 的 `in` */
/* 迴圈主體 */
}
```
- `declaration`：用於表示每個元素的變數宣告。
- `range`：可迭代的對象/範圍。
- 例如：陣列、`std::vector`、`std::map`
<br/>
:::success
這種語法類似於 Python 的 `for x in obj`，
使得遍歷操作更加直觀。
:::
---
#### 迭代器 - `for` 迴圈可迭代遍歷
- 遍歷陣列：
```cpp[]
#include <iostream>
int main() {
int arr[] = {1, 2, 3, 4, 5};
for (int i : arr) {
std::cout << i << " ";
} std::cout << std::endl;
// 輸出: 1 2 3 4 5
return 0;
}
```
- 遍歷 `std::vector`：
```cpp[]
#include <iostream>
#include <vector>
int main() {
std::vector<std::string> fruits = {"apple", "banana", "cherry"};
for (const std::string& fruit : fruits) {
std::cout << fruit << " ";
} std::cout << std::endl;
// 輸出: apple banana cherry
return 0;
}
```
---
#### 迭代器 - `for` 迴圈可迭代遍歷
- 優點：
- 簡潔易讀：省略了傳統 `for` 迴圈中的索引管理。
- 避免錯誤：減少了因索引錯誤導致的 bug。
- 適用範圍廣：可用於所有支援 `begin()` 和 `end()` 的容器。
- 注意事項：
- 若需要在迴圈中修改元素，應使用參考：
```cpp[]
for (int& i : arr) {
i *= 2; // 對原始陣列的元素進行修改
}
```
- 但若需要同時獲取索引，則需使用傳統的 `for` 迴圈或其他方法。
---
<!--
#### 🔹 迭代器 - 分類
<br/>
根據功能，迭代器可以分為以下幾類：
| Iterator | 作用 |
|-|-|
| `輸出迭代器`（Output） | 只能寫入元素 |
| `輸入迭代器`（Input） | 只能讀取元素 |
| `前向迭代器`（Forward）| 可讀可寫 只向前 |
| `雙向迭代器`（Bidirectional） | 可讀可寫 能向前後 |
| `隨機存取迭代器`（Random Access） | 可讀可寫 並且支持隨機存取 如陣列的索引操作 |
-->
#### ⚔️ 迭代器 v.s. 指標
<br/>
1. `迭代器`在語法上類似於`指標`。
2. `迭代器`提供了更高層次的抽象，使得程式碼更具++可讀性++和++可維護性++。
3. `迭代器`還能夠++處理非連續記憶體++的容器，如 `list` 和 `map`，這是`指標`++無法++直接做到的。
> ==補充==：[Difference between Iterators and Pointers](https://youtu.be/nziB93VpFp8?si=1W9W9EpktvTV2YwW)
<!--  -->
---
#### 🧪 小測驗 G - 刪除相鄰重複元素
- 給定一串整數，請移除所有++相鄰重複++的元素，
請使用 `std::list` 與 `迭代器`操作來完成。
- 範例:
```python
list<int> nums = {1, 2, 2, 3, 3, 3, 4, 5, 5}; // 輸入串列
輸出: 1 2 3 4 5
```
- 提示:
- 謹記 `prev(it)` 或是 `next(it)` 用法
- `list`：no match ‘operator[]’ for std:list
- ∴ 需以 `.erase(iterator)` 刪除操作
::: spoiler ▼ 詳解
```cpp[]
// #include <list>
list<int> nums = {1, 2, 2, 3, 3, 3, 4, 5, 5}; int last = *nums.begin();
for (auto it = nums.begin(); next(it) != nums.end();) {
++it;
if (*it == last) nums.erase(prev(it));
last = *it;
}
```
:::
---
#### 🧪 小測驗 H - 逆序輸出
- 給定 `vector<string>` 請使用++反迭代++方法，
依序輸出每個字串的最後一個字元（尾至頭）。
- 範例:
```cpp[]
vector<string> words = {"airplane", "ballon", "cat", "digging"};
輸出: g t n e
```
::: spoiler ▼ 詳解1
```cpp[]
vector<string> words = {"airplane", "ballon", "cat", "digging"};
for (auto it = words.end() - 1; it >= words.begin(); --it) {
string str = *it;
cout << str[str.length() - 1] << " ";
}
```
:::
::: spoiler ▼ 詳解2 (reverse_iterator 補充用法)
```cpp[]
vector<string> words = {"airplane", "ballon", "cat", "digging"};
for (auto rit = words.rbegin(); rit != words.rend(); ++rit)
cout << rit->back() << " ";
```
:::
---
#### ∑ 迭代器 - 總結
- `迭代器`是 C++ `<STL>` 中的重要組件，提供了一種++統一++且抽象的方式來遍歷容器中的元素。
- 可編寫與容器無關的演算法，提升程式的++靈活性++和++可維護性++。
- 須注意在對容器進行某些操作（如插入或刪除元素）後，原有的迭代器可能會失效，導致未定義的行為：
- 例如，對 `vector` 進行 `push_back()` 操作可能會重新配置記憶體。
- 在進行這類操作後，應重新獲取新的迭代器，避免`迭代器`++失效++。
---
### ⚙️ 基本記憶體管理
<br/>
`C++` 不像 Py、Java 有++自動垃圾回收機制++(GC)，
因此我們需要自己掌控記憶體的`分配`與`釋放`。
💡 _主動管理之目的_：
| | |
|-|-|
| (1) 避免記憶體洩漏（Memory Leak） | 分配記憶體卻沒釋放，導致資源浪費甚至系統崩潰 |
| (2) 提升執行效能 | 動態記憶體分配可更靈活掌握執行效率 |
| (3) 節省佔用記憶體 | 只在需要時分配記憶體，使用完立即釋放 |
| | |
---
#### 🧩 動態記憶體分配方式
<br/>
| 方法 | 使用語法 | 說明 |
|-|-|-|
| C Style 作法 | `malloc()` / `free()` 函式 | 需要 `<cstdlib>`，不會呼叫建構/解構函式。以 `malloc()` 分配記憶體，使用完畢後必須手動 `free()` 以釋放所占用記憶體空間 |
| C++ Style 作法 | `new` / `delete` 保留字 | 自動配合建構/解構，語法更簡潔（建議使用） |
<br/>
> 1. `建構函式`是當物件被建立時自動呼叫的特殊函式，用來++初始化物件++；
> 2. `解構函式`則是在物件被銷毀時自動執行，用來++釋放資源++或++執行清理動作。
---
#### ① `new` / `delete` 基本語法
<br/>
```cpp[]
int* ptr = new int; // 配置一塊 int 空間，並未有初始內容
*ptr = 10; // 修改記憶體位置上的資料
cout << "地址: " << ptr << " => 資料: " << *ptr << endl;
delete ptr; // 釋放 ptr 指向的空間
```
```cpp[]
int* arr = new int[10]; // 配置 10 個 int 空間（陣列）
arr[0] = 42; // 修改連續記憶體位置上位置 0 的資料
arr[1] = 73; // 修改連續記憶體位置上位置 1 的資料
for (int i = 0; i < 10; ++i) cout << arr[i] << endl;
delete[] arr; // 使用後釋放（陣列需要使用 delete[]）
```
- 每個 `new` 都應有對應的 `delete`
- 配置陣列要使用 `delete[]`！
- 若不釋放會造成 ==記憶體洩漏 (Memory Leak)==
---
#### ② `malloc()` / `free()` 基本語法
<br/>
```cpp[]
#include <iostream>
#include <cstdlib> // 記得要導入此函式庫
#include <vector>
using namespace std;
int main() {
int* ptr = (int*)malloc(sizeof(int));
*ptr = 100; // 分配單一個 int 大小的記憶體
cout << "地址: " << ptr << " => 資料: " << *ptr << endl;
free(ptr); // 釋放空間
return 0;
}
```
```cpp[]
int n = 5; // 分配 n 個 int 大小的空間
int* arr = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) arr[i] = i * 10;
for (int i = 0; i < n; ++i) cout << "arr[" << i << "] = " << arr[i] << endl;
free(arr); // 釋放記憶體空間
```
- `malloc` 回傳型別為 `void*`，需強制轉型
- `malloc(n*sizeof(type))`: 分配`n`個指定空間
- `free()` 釋放記憶體 否則可能會 ==Memory leak==
---
#### ⭐ 記憶體分配方式 - 比較
<br/>
||||
| Difference | `new` / `delete` | `malloc()` / `free()` |
|-|-|-|
||||
| 語法風格 | C++（較新）| C（較舊）|
| 迴傳型別 | 自動推斷 | `void*` 需轉型 |
| 呼叫建構子 | ✅ 會呼叫 | ❌ 不會 |
| 使用方便性 | 較高（建議） | 較低 |
---
#### 🛠 記憶體管理 - 常見錯誤
<br/>
❌ 沒有釋放記憶體（Memory Leak）
```cpp[]
複製程式碼
int* leak = new int(123);
// 沒有 delete
```
<br/>
❌ 重複釋放（Double Free）
```cpp[]
int* p = new int(5);
delete p;
delete p; // ❌ 再次釋放會造成未定行為
```
✅ 用 `nullptr`（空指標）來防呆
```cpp[]
int* p = new int(5);
delete p;
p = nullptr; // 避免再次 delete
```
---
### 📱 智慧指標（補充）
<br/>
C++11 引入 ++Smart Pointers++ 能夠自動管理記憶體
- `std::unique_ptr<T>`
- `std::shared_ptr<T>`
<br/>
👉 這些不需要手動呼叫 delete 非常適合
管理動態記憶體（詳見往後課程）。
---
#### 📊 記憶體管理 - 小結
1. C++ ++不會++ 自動幫你管理記憶體代碼需要主動分配與釋放。
2. 建議使用 `new`/`delete`，除非在寫需要與 C 語言相容的部分。
3. 配合 `nullptr` 與良好習慣，避免++記憶體洩漏++與++錯誤釋放++。
4. 將來的進階應用，建議以智慧指標（smart pointers）來自動管理。
---
### 📝 習題 - 動態字串陣列
<br/>
請設計一個動態「字串陣列」，
用來動態存放多個人的名字字串。
> 🛇 限制：禁止使用 `vector` 或 `string` (以 `new char[]` 來配置)
- 範例輸入：
```cpp[]
請輸入人數: 3
請輸入第 1 個名字: Alice
請輸入第 2 個名字: Bob
請輸入第 3 個名字: Charlie
```
- 範例輸出：
```cpp[]
名單：
1. Alice
2. Bob
3. Charlie
```
---
### 📝 習題 - 動態字串陣列
<br/>
:::spoiler ▼ ✅Tips
1. 需要 `char**`（指標陣列）
2. 別忘了字串結尾 '\0'： new char[長度+1]
3. 結束後，逐項 `delete[]` 每個名字，再 `delete[]` 整個陣列。
:::
<br/>
:::spoiler ▼ 詳解
```cpp[]
#include <iostream>
#define MAX_LEN 100
using namespace std;
int stringLength(char *str) {
int i = 0;
while (str[i] != '\0') ++i;
return i;
}
int main() {
int n; cin >> n;
char** names = new char*[n];
for (int i = 0; i < n; ++i) {
char temp[MAX_LEN]; cin >> temp;
int len = stringLength(temp);
names[i] = new char[len + 1];
for (int j = 0; j < len; ++j) names[i][j] = temp[j];
names[i][len] = '\0'; // 結尾字元
}
for (int i = 0; i < n; ++i) cout << i + 1 << ". " << names[i] << endl;
for (int i = 0; i < n; ++i) delete[] names[i];
delete[] names;
return 0;
}
```
:::
---
### 📋 LeetCode 題 - [Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array)
> 請以 C++ 來實作，考驗 STL `<vector>` 的熟練度
<br/>
- 題目說明:
- 實作合併兩個 Sorted Array 的操作
- `m`, `n` 分別代表被合併的前幾個元素
- `nums1`[0 到 m] + `nums2`[0 到 n] = `result_arr`
- 程式輸出:
- 無實際輸出
- 僅需要把更新後的結果存在 `nums1`
- 合併後的陣列也必續保持為已排序(小到大)
- 參閱解答：{%preview https://leetcode.com/submissions/detail/1619517099/ %}
{"title":"CPP Lecture4","description":"CPP Lecture4.","image":"https://hackmd.io/_uploads/rJJd49wayg.png","contributors":"[{\"id\":\"08ecf684-cada-47c1-ad99-984ab62fb65e\",\"add\":29420,\"del\":3303}]"}