【C++筆記】Iterator（迭代器）

該筆記僅供個人學習用途，部分用詞、解釋等若有誤方可指正，感謝您的觀看。

簡介

Iterator，名為迭代器，光看名字就是一個非常抽象的東西XD。

Iterator 是一種類指針（pointer-like）的物件，指向 STL container 的元素。像是 vec.begin() 跟 vec.end() 分別指向 vec 容器的第一個元素跟末尾元素的記憶體位址，使用 * 做 Dereference 的動作即可取值。

整理一下：Iterator 的意義是記憶體位址，使用 * Dereference operator 可用來取得目前 iterator 所指向的元素的值。

Why is Iterator?

而迭代器之所以被稱為迭代器，是因為它的設計目的是為了支援容器中元素的「逐一存取」（iteration），類似於指標。

首先要說什麼是迭代 iteration？

「迭代」的核心概念是：重複逐個存取資料結構中的每個元素，直到全部處理完畢。其實就是跑迴圈的意思，如下是一個最基本的迭代行為：

// 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

宣告方式如下：

1	<type>::iterator it;

type：宣告迭代器的容器型態。
it：迭代器的名稱，可自定義，通常取它英文名字的前面兩個當作名稱（it）。

`begin()` 與 `end()`

以下是有關迭代器的小範例：

#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：

1	10 20 30 40 50

若要讓這個程式執行的結果是「倒著走訪」的話，則用到反向迭代器（rbegin(), rend()），反向 reverse，理所當然的在前面加上個 r。

當然，宣告方式也要加上個 reverse_，讓原本的 vector<int>::iterator it; 變成 vector<int>::reverse_iterator it;。

#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：

1	vector<int>::reverse_iterator it;

那還有個東西叫做 cbegin()、cend()、crbegin()、crend()，這些迭代器都加上了 c，表示 const 的意思，也就是這些迭代器不能修改，只能讀取。

然後，宣告時要再加上一個 const_。

範例如下：

#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：

1	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	否

範例：

#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：

總結

Iterator 宣告方式：

1	<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

C++ Iterators | W3Schools

C++ 迭代器 iterator－程式語言教學｜痞客邦

Iterators in C++ STL - GeeksforGeeks

【C++筆記】Iterator（迭代器）

簡介

Why is Iterator?

為什麼不用 pointer 就好？

Iterator

Declaration

begin() 與 end()

表格整理

迭代器的操作

迭代器的種類

迭代器的一些好用函式

總結

參考資料

`begin()` 與 `end()`