###### tags: `cpp`

# CPP Iterator簡介

iterator是來解決pointer走訪時，容易亂指所導致的問題

像是pointer走訪array，`*(ptr+0)` 到 `*(ptr+n)`多走一個都會導致走訪錯誤，更不用說比array複雜的資料結構走訪了

所以就延伸出iterator，有類似pointer的走訪功能，但能像在走訪前做一些判斷或功能，這樣就能安全、方便的走訪

而他的防呆或判斷方式，就是用[運算子重載](https://www.geeksforgeeks.org/operator-overloading-cpp/)的方式，去定義每個資料結構如何走訪下一步

## 大略原理

先看一段基本使用

int main() {
    vector<int> ar = {1, 2, 3, 4, 5};

    // vector的iterator
    vector<int>::iterator ptr;

    cout << "All elements : ";
    for (ptr = ar.begin(); ptr != ar.end(); ptr++) 
        cout << *ptr << " ";

    // output: 1 2 3 4 5
    return 0;
}

以最常用的走訪來說，首先要知道"從哪開始(begin)"、"怎樣算結束(end)"、"如何找到下一個(next)"

所以vector內部可能就會定義這樣一些iterator需要的東西，然後就會有個走訪的模板去操作iterator，像是for_each、copy、reverse等等

struct Iterator 
{
    pointer m_ptr;
    
    // Prefix increment
    Iterator& operator++() { m_ptr++; return *this; }  

    friend bool operator== (const Iterator& a, const Iterator& b) { return a.m_ptr == b.m_ptr; };
    friend bool operator!= (const Iterator& a, const Iterator& b) { return a.m_ptr != b.m_ptr; };   
    
    Iterator begin() { return Iterator(&m_data[0]); }
    Iterator end()   { return Iterator(&m_data[200]); } // 200 is out of bounds  

};

iterator裡面operator++()這個運算重載，通常不會是單純的`m_ptr++`，只是舉個栗子，通常前面會加一些判斷是否超出範圍，或是一些計算來取得下一個東西的位置

## Iterator的走訪

前面都定義好行為後，應該就更了解這段的運作

vector<int> ar = {1, 2, 3, 4, 5};
cout << "All elements : ";
for (ptr = ar.begin(); ptr != ar.end(); ptr++) 
    cout << *ptr << " ";

## 透過For_each

那上面這個其實還是滿麻煩的對ㄅ，所以就把這串整合成一個通用函示，叫做 [for_each](https://en.cppreference.com/w/cpp/algorithm/for_each)

UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{
    for (; first != last; ++first) {
        f(*first);
    }
    return f; // implicit move since C++11
}

透過for_each操作

void print(int n) { cout << n << " "; }
int main() {
    vector<int> v1 = {1, 2, 3, 4, 5};
    cout << "use for_each : ";
    for_each(v1.begin(), v1.end(), print);
    // output: 1 2 3 4 5
    return 0;
}

把Iterator的for_each簡化，演變成用`for(:)`

int main() {
    vector<int> v1 = {1, 2, 3, 4, 5};
    cout << "use for_each : ";
    for (auto n : v1) cout << n << " ";
    // output: 1 2 3 4 5
    return 0;
}

然你就會發現，越來越簡化，而且邏輯很清晰好懂

所以iterator就是把pointer的走訪功能，把它包裝起來，變得方便易用，又不容易出問題

iterator裡面的operator++()這個運算重載，通常不會是單純的 m_ptr++，只是舉個栗子，通常前面會加一些判斷是否超出範圍，或是一些計算來取得下一個東西的位置

像是map的++，就會去走訪樹，然後找出下一個

這樣，就比單純用指標走訪強很多了，為了因應複雜結構的走訪，所以才搞出這東西

## 應用

最直接的範例就是紅黑樹的資料結構，因為樹的走訪不是循序的，沒辦法向陣列指標一樣，透過`treeNode++`的方式去取得下一個資料節點，但借助Iterator的特性，就能方便的走訪節點

而這個東西就叫做std::map，map的`++`或是`next()`，就會去走訪樹，然後找出下一個

這裡以3->1->5->4->2的順序插入資料，根據map紅黑樹會排序的特性，可以得到遞增的順序輸出

map<int, string> myMap;
myMap[3] = "ttt";
myMap[1] = "www";
myMap[5] = "fff";
myMap[4] = "ggg";
myMap[2] = "rrr";
for (auto it : myMap) {
    cout << it.first << " " << it.second << "\n";
}

output:
1 www
2 rrr
3 ttt
4 ggg
5 fff

以tree這種資料結構，像要按順序輸出，還要寫一個中序走訪

在map這種由節點構成的結構，能把走訪的方式包裝起來，輕鬆使用，這就是Iterator最大的用處

## 總結

雖然正常走訪pointer也做得到，但Iterator的優勢就在於

- 能透過運算子重載的方式，去**指定下一個目標**在哪，讓資料結構不侷限於陣列這種連續空間上
- 將走訪的方式包裝起來，更方便的操作
- 避免指標超出存取範圍的未定義行為

## 參考資料
迭代器（iterator）和指针（pointer）区别在哪？
https://www.zhihu.com/question/54047747
std::for_each
https://en.cppreference.com/w/cpp/algorithm/for_each
能看清底層怎麼寫的 Writing a custom iterator in modern C++
https://www.internalpointers.com/post/writing-custom-iterators-modern-cpp
Introduction to Iterators in C++
https://www.geeksforgeeks.org/introduction-iterators-c/
帶著你拆開vector底層，看iterator怎麼做的
https://www.youtube.com/watch?v=F9eDv-YIOQ0&list=PLlrATfBNZ98dudnM48yfGUldqGD0S4FFb&index=94