【C++筆記】Iterator（迭代器）
===
目錄：
[TOC]
該筆記僅供個人學習用途，部分用詞、解釋等若有誤方可指正，感謝您的觀看。
簡介
---
Iterator，名為迭代器，光看名字就是一個非常抽象的東西XD。
Iterator 是一種類指針（pointer-like）的物件，指向 STL container 的元素。像是 `vec.begin()` 跟 `vec.end()` 分別指向 vec 容器的第一個元素跟末尾元素的記憶體位址，使用 `*` 做 Dereference 的動作即可取值。
整理一下：Iterator 的意義是記憶體位址，使用 `*` Dereference operator 可用來取得目前 iterator 所指向的元素的值。
### Why is Iterator?
而迭代器之所以被稱為迭代器，是因為它的設計目的是為了支援容器中元素的「逐一存取」（iteration），類似於指標。
首先要說什麼是迭代 iteration？
「迭代」的核心概念是：重複逐個存取資料結構中的每個元素，直到全部處理完畢。其實就是跑迴圈的意思，如下是一個最基本的迭代行為：
```cpp=
// use for loop to do iteration.
int a[] = {1, 2, 3, 4};
for (int i = 0; i < 4; i++) {
cout << a[i] << endl;
}
```
迭代器（iterator）就是封裝了「位置 + 移動 + 解參考」的物件。
以 C++ 標準為基礎，一個迭代器應支援以下幾種操作：
| 操作 | 說明 |
| ------------ | --------------- |
| `*it` | 取出目前位置的元素。 |
| `++it` | 移動到下一個元素。 |
| `it1 == it2` | 比較兩個迭代器是否指向同一位置。 |
迭代器也是是一種抽象化（Abstraction）的「存取工具」，你不用去知道底層容器的資料結構，就可以逐一存取裡面的資料。
例子就是 STL 裡面大多容器都採用 iterator 的方式去存取，如 vector, set, map 等等。
在寫 iterator 的時候，時常會寫成這樣：`auto it = vec.begin();`，auto 儲存類別可以自動判斷這是哪一個容器類型或資料型態，再加上 iterator 對於 STL 大多容器都可適配，因此才會說 iterator 是一種抽象化的工具。
### 為什麼不用 pointer 就好？
指標僅受限於「連續記憶體」，對於 `std::list, std::map, std::unordered_set` 等非連續容器，就無法用 pointer 表示位置。
所以 C++ 引入了泛型程式設計（generic programming）的概念，用迭代器統一存取方式，能用相同的語法處理不同型態的容器。
Iterator
---
### Declaration
宣告方式如下：
```
<type>::iterator it;
```
- type：宣告迭代器的容器型態。
- it：迭代器的名稱，可自定義，通常取它英文名字的前面兩個當作名稱（it）。
### `begin()` 與 `end()`
以下是有關迭代器的小範例：
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {10, 20, 30, 40, 50};
vector<int>::iterator it;
// 用 iterator 逐一走訪 vector
for (it = numbers.begin(); it != numbers.end(); ++it) {
// ++it 表示向容器右方走一個單位
cout << *it << " ";
}
cout << endl;
return 0;
}
```
Output：
```
10 20 30 40 50
```
若要讓這個程式執行的結果是「倒著走訪」的話，則用到反向迭代器（`rbegin(), rend()`），反向 reverse，理所當然的在前面加上個 r。
當然，宣告方式也要加上個 reverse_，讓原本的 `vector<int>::iterator it;` 變成 `vector<int>::reverse_iterator it;`。
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {10, 20, 30, 40, 50};
vector<int>::reverse_iterator it;
// 用 iterator 逐一走訪 vector
for (it = numbers.rbegin(); it != numbers.rend(); ++it) {
cout << *it << " ";
}
cout << endl;
return 0;
}
```
Output：
```
vector<int>::reverse_iterator it;
```
那還有個東西叫做 `cbegin()`、`cend()`、`crbegin()`、`crend()`，這些迭代器都加上了 c，表示 const 的意思，也就是這些迭代器不能修改，只能讀取。
然後，宣告時要再加上一個 const_。
範例如下：
```cpp=
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> numbers = {10, 20, 30, 40, 50};
vector<int>::const_reverse_iterator it;
// 用 iterator 逐一走訪 vector
for (it = numbers.crbegin(); it != numbers.crend(); ++it) {
cout << *it << " ";
// *it = 500; 會錯誤，因為已宣告了 const
}
cout << endl;
return 0;
}
```
Output：
```
50 40 30 20 10
```
#### 表格整理
| 迭代器函式 | 回傳值說明 |
|--------------|----------------------------------------------------------------------------|
| `begin()` | 回傳一個指向容器開頭的迭代器。 |
| `end()` | 回傳一個指向容器最後一個元素之後的理論元素的迭代器。 |
| `cbegin()` | 回傳一個指向容器開頭的**常數迭代器**。常數迭代器無法修改其所指向的元素值。 |
| `cend()` | 回傳一個指向容器最後一個元素之後的**常數迭代器**。 |
| `rbegin()` | 回傳一個指向容器開頭的**反向迭代器**（實際上是尾端的元素）。 |
| `rend()` | 回傳一個指向容器最前面元素之前的理論元素的**反向迭代器**。 |
| `crbegin()` | 回傳一個指向容器開頭的**常數反向迭代器**。 |
| `crend()` | 回傳一個指向容器最前面元素之前的理論元素的**常數反向迭代器**。 |
表格來源：https://www.geeksforgeeks.org/cpp/iterators-c-stl/
理論元素：容器實際元素以外的一個元素（如 `end()` 並不是指最後一個元素，而是最後一個元素的下一個元素）。
### 迭代器的操作
可以做：
- 加減操作
- 解參考操作（`*`）
- 比較操作（`==`, `!=`, `>=`, `<=`, `>`, `<`）
### 迭代器的種類
Image Source：https://www.geeksforgeeks.org/cpp/introduction-iterators-c/
Image Source：https://www.geeksforgeeks.org/cpp/random-access-iterators-in-cpp/
分五種：
- Input Iterator（輸入迭代器）
- Output Iterator（輸出迭代器）
- Forward Iterators（前向迭代器）
- Bidirectional Iterators（雙向迭代器）
- Random Access Iterators（隨機存取迭代器）
Input/Output Iterator 是最基本的，分別只能讀或寫，且只能一次性通過資料。支援的容器就是「輸出輸入流」（Input/Output Stream）了。
Forward Iterator 是輸入輸出迭代器的升級版，可多次遍歷，類似於 Singly Linked-List。支援的容器有 unordered_map, unordered_set。
Bidirectional Iterator 在 Forward 的基礎上增加了反向移動（--）能力。支援的容器有 list（double linked list）, map, set, multimap, multiset。
Random Access Iterator 可支援像陣列一樣的隨機存取，操作與指標最為相似，效率最高。支援的容器有 vector, deque, array, string。
### 迭代器的一些好用函式
| function name | description | return type | type of iterator | 是否會改變原迭代器 |
| ------------- | ------------------------------------------------------------------------ | -------------- | --------------------------- | ------------------ |
| advance() | 將迭代器向前（或向後）移動指定的距離 | void | all | 是 |
| next() | 回傳新的迭代器，該迭代器是原始迭代器向前（或向後）移動指定距離之後的位置 | 與原迭代器相同 | all | 否 |
| prev() | 回傳新的迭代器，該迭代器是原始迭代器向後移動指定距離之後的位置 | 與原迭代器相同 | Bidirectional Iterator 以上 | 否 |
| distance() | 計算兩個迭代器之間的距離（元素數） | int | all | 否 |
範例：
```cpp=
#include <iostream>
#include <vector>
#include <iterator> // 引入 iterator 函式
using namespace std;
int main() {
vector<int> vec = {10, 20, 30, 40, 50};
auto it = vec.begin();
advance(it, 2); // it 目前指向 30
cout << *it << endl; // 30
auto next_it = next(vec.begin(), 3); // 指向 40，不影響 vec.begin()
cout << *next_it << endl; // 40
auto prev_it = prev(vec.end(), 2); // 指向 40
cout << *prev_it << endl; // 40
cout << distance(vec.begin(), vec.end()) << endl; // 5
}
```
Output：
```
30
40
40
5
```
總結
---
Iterator 宣告方式：
```
<type>::iterator it;
```
- type：宣告迭代器的容器型態。
- it：迭代器的名稱，可自定義，通常取它英文名字的前面兩個當作名稱（it）。
常用函式：
`begin()` / `end()`：回傳指向容器開頭或結尾的迭代器。
`rbegin()` / `rend()`：回傳反向迭代器，用於反序遍歷。
`cbegin()` / `cend()`、`crbegin()` / `crend()`：回傳常數迭代器，唯讀，無法修改。
迭代器操作：
- 加減操作（如 `++it`, `--it`）。
- 解參考（`*`）。
- 比較操作（如 `==`, `!=`, `>`, `<=` 等）。
迭代器種類：
- 輸入迭代器（Input Iterator）：僅支援單向讀取，適用於輸入流。
- 輸出迭代器（Output Iterator）：僅支援單向寫入，適用於輸出流。
- 前向迭代器（Forward Iterator）：支援單向多次遍歷，適用於 unordered_map、unordered_set。
- 雙向迭代器（Bidirectional Iterator）：支援雙向移動，適用於 list、map、set。
- 隨機存取迭代器（Random Access Iterator）：支援隨機存取，效率最高，適用於 vector、deque、array、string。
迭代器實用函數：
- `advance(it, n)`：將迭代器移動指定距離，改變原迭代器。
- `next(it, n)`：回傳移動後的新迭代器，不影響原迭代器。
- `prev(it, n)`：回傳向前移動後的新迭代器，限雙向迭代器以上。
- `distance(it1, it2)`：計算兩個迭代器間的元素數。
參考資料
---
[CPP Iterator簡介 - HackMD](https://hackmd.io/@beadx6ggwp/ryoNnqdl5)
[C++ Iterators | W3Schools](https://www.w3schools.com/cpp/cpp_iterators.asp)
[C++ 迭代器 iterator－程式語言教學｜痞客邦](https://crmne0707.pixnet.net/blog/post/318479072)
[Iterators in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/cpp/iterators-c-stl/)
Sign in with Wallet
Connect another wallet