在資料結構的章節中，我們常常的使用到各種資料結構的 Iterator。現在就讓我們更詳細的介紹 Iterator 的概念吧！
根據 C++ Reference 的敘述，一個迭代器（Iterator）是任何一種可以指向一個「容器」裡面的元素，並且有能力「迭代」該容器的區間。具體來說是什麼意思呢？「容器」在這裡指的是「任何一種按照順序排好的元素組合」，這個順序可能是按照元素大小的順序（set、map 等），也可能是放進資料結構中的順序（陣列、stack、queue），又或是看似沒有規則的東西，其實 C++ 也會幫它排一個順序（像是 unordered_set、unordered_map）等。因此，「迭代」故名思義就是去按照這個順序去存取容器裡的元素。那麼迭代器是如何存取資訊，並且移動到不同元素的呢？
不同的資料結構會有不同的迭代器種類，而理解這些種類的差別可以讓我們更清楚了解每個資料結構的實作方式和複雜度差異。
迭代器被分成五個類別：Input, Output, Forward, Bidirectional, Random Access。每一個類別都有那個類別支援的功能，而這些類別其實有一個互相包含的關係，詳細可以看下圖：
Input 和 Output 算是 Iterator 的基本構成要件。Input Iterator 讓我們可以取得該元素的值，Output Iterator 讓我們可以把數值存入其他的地方（像是變數），而這兩種 Iterator 都在看完一個元素之後改成下一個。他們可以被用在像是輸入和輸出的串流型態中，但是對於我們常見的資料結構來講，我們可以看一個 Iterator 的值，也可以改變 Iterator 位置裡代表的元素的值，所以這些資料結構的 Iterator 都支援 Input, Output 的功能。
Forward Iterator 的概念就和一個單向的 Linked List 十分相似。他支援 Input 跟 Output Iterator 的功能（可以查值也可以改值），而且每一個元素都可以查/改任意多次。而 Iterator 可以透過 ++ 這個運算子，來看到下一個元素。
以此類推，Bidirectional Iterator 就是「雙向的」迭代器！他除了 Forward Iterator 的功能外，還額外支援「回到前一項的功能」，這個功能透過 -- 這個運算子實現。這個迭代器是大部分 STL 資料結構中會支援的功能。
Iterator 其實沒有辦法直接轉型成數字，因此這裡的 ++ 和 -- 其實不是一般整數的 +=1 或 -=1 的意思，而是在容器裡面變成下一個或前一個元素。同樣的符號在不同的型態中可以代表不同的意思喔！
有興趣的讀者可以做個小實驗：宣告一個空的 std::set ，然後隨意把幾個數字加進去，接著設定變數 auto it = set_name.begin()，如果要列印該 Iterator 在記憶體中的實際位置，我們可以用 &(*it) 的方式。觀察一下 it 還有 ++it 的記憶體位置。接下來換一組數字加進 set 裡面，再做一樣的實驗。it 和 ++it 的相對記憶體位置是不是改變了呢？
最後要介紹的是最強大的 Random Access Iterator。他除了前面所有的功能之外，可以跟陣列一樣隨意的隨意取用任何一個元素。也就是說，我們可以隨意的看到那個容器的某一項有誰，也可以看任何一個 Iterator 往前或往後任意多項的結果，甚至可以將兩個 Iterator 相減看到差距，可以說是最沒有限制的迭代器。這個 Iterator 還有一個額外的功能：是可以瞬間比較兩個 Iterator 的大小。
Random Access Iterator 在記憶體的位置也不一定是連續的！可以看看 deque 的實作。
STL 中，不同的資料結構會支援不同的 Iterator，而最常見的就是 Bidirectional 跟 Random Access 兩種，因此接下來我們主要會比較他們的差別。
當我們看到一種資料結構有 Random Access Iterator 時，就代表他可以在 $O(1)$ 時間得到任何一項的值*，例如 vector 或者是 deque。如果這個資料結構內部的架構就是無法在 $O(1)$ 時間查詢的話，那麼他就會退而求其次的使用 Bidirectional，像是 set 和 map。
如果他根本是一個不需要順序的資料結構，那他甚至不需要兩個方向的遍歷（因為前後順序在這個資料結構沒有意義）。所以可想而知，unordered_set 和 unordered_map 支援的是 Forward Iterator （只需要寫一個迴圈遍歷所有元素）。
總結來說，根據一個資料結構的功能和複雜度，可以推論得知他使用哪一種 Iterator，因此平常在使用的時候也要清楚知道那個 Iterator 支援的功能。
* 其實 C++ 規定中並沒有說 Random Access Iterator 的實作要可以在 $O(1)$ 內找到數值，但是實作這個 Iterator 的容器會做這樣的複雜度保證，而無法作到這件事的容器就不會使用 Random Access Iterator。
Iterator 有一些之前沒有提到的功能，在這裡補充一些有用的內容（以下用 it 來表示某 iterator）：
next(it)：取得it的下一項。其中next(it, n)可以取得從it開始往後第 $n$ 項。prev(it)：取得it的上一項。其中prev(it, n)可以取得從it開始往前第 $n$ 項。