Iterator

你想寫個資料結構程式庫，其中有 ArrayList，內部使用陣列實現：

import java.util.Arrays;

public class ArrayList {
    private Object[] elems;
    private int next;
   
    public ArrayList(int capacity) {
        elems = new Object[capacity];
    }

    public ArrayList() {
        this(16);
    }

    public void add(Object o) {
        if(next == elems.length) {
            elems = Arrays.copyOf(elems, elems.length * 2);
        }
        elems[next++] = o;
    }
    
    public Object get(int index) {
        return elems[index];
    }
    
    public int size() {
        return next;
    }
}

後來你又寫了 LinkedList、HashSet、TreeSet 等，如果現在有個需求，是逐一顯示這些資料結構收集的元素，你要怎麼寫呢？根據 ArrayList、LinkedList、HashSet、TreeSet 等型態，重載出多個方法嗎？有沒有可能定義一個方法就能解決呢？

探索內部的物件

問題在於，ArrayList 等的特性各不相同，因此各自定義了外觀上不同的行為，像是 ArrayList 具索引，HashSet 就不具索引相關方法；ArrayList 等內部各自實現了不同的資料結構，該如何逐一走訪元素，只有 ArrayList 等各自內部才知道。

能不能為 ArrayList 等提供一致的走訪行為呢？例如，都有取得下個元素的 next 方法？以 ArrayList 為例：

public class ArrayList {
    ...

    public Object next() {
        return elems[next];
    }
}

這麼一來，就可以統一呼叫各資料結構物件的 next 方法，來逐一取得元素了不是嗎？是可以！不過，在呼叫過 next 後，因為是逐一走訪，是不是要有個內部特性，記錄現在走訪到哪了？如果有多次走訪的需求呢？走訪的記錄要不要重置呢？如果同時被走訪呢？難道你要在一個物件裡，安排多個走訪記錄嗎？

若要將方才的東西，都實現在各自資料結構物件中，那會令程式過於複雜，不如設計一個物件來專門負責這件事，這個物件可以查詢有沒有下個物件可走訪，如果才能傳回，如果你能取得這個物件，就可以走訪資料結構。

那麼來設計一個 Iterator：

interface Iterator {
    boolean hasNext();
    Object next();
}

因為只有各自資料結構物件，才知道怎麼逐一走訪各自資料結構，因此實現 Iterator 的，基本上會是內部類別：

import java.util.Arrays;

public class ArrayList {
    private Object[] elems;
    ...

    private class IteratorImpl implements Iterator {
        private int index;
        public boolean hasNext() {
            return index < elems.length;
        }

        public Object next() {
            return elems[index++];
        }
    }

    public Iterator iterator() {
        return new IteratorImpl();
    }
}

每個資料結構類別，都可以提供一個 iterator 方法，傳回內部的 Iterator 實作物件，這麼一來，只要一個方法就能逐一顯示各資料結構收集的元素了：

static void printAll(Iterator iterator) {
    while(iterator.hashNext()) {
        out.println(iterator.next());
    }
}

例如，顯示 ArrayList、HashSet 收集的元素，就可以這麼寫：

var names = new ArrayList();
names.add("Justin");
names.add("Monica");
names.add("Irene");
printAll(names.iterator());

var colors = new HashSet();
colors.add("Red");
colors.add("White");
colors.add("Red");
printAll(colors.iterator());

語言常見協定

在 Gof 中，稱這樣的模式為 Iterator，因為逐一走訪的需求太常見，許多語言都會規範如何傳回 iterator，並提供對應的語法支援，例如 Java 規範了 Iterable，若物件實現了該介面，就可以搭配 for 來走訪元素，例如 List 本身就是 Iterable 的子介面：

var names = Arrays.asList("Justin", "Monica", "Irene");
for(var name : names) {
    out.println(name));
}

Java 的編譯器會將以上程式碼展開：

String name;
for(Iterator i$ = names.iterator();
    i$.hasNext(); 
    out.println(name)) {
        name = i$.next();
}

不同的語言，實現 for 與 iterator 的合作方式只是略有不同，例如，JavaScript 規範了可搭配 for 的物件，必須實現 Symbol.iterator 協定，例如陣列：

> let arr = [1, 2, 3];
undefined
> let iterator = arr[Symbol.iterator]();
undefined
> iterator.next();
{ value: 1, done: false }
> iterator.next();
{ value: 2, done: false }
> iterator.next();
{ value: 3, done: false }
> iterator.next();
{ value: undefined, done: true }
>

JavaScript 的 iterator 只要實現 next 方法，然而傳回的物件必須具有 value 與 done 特性，done 是 for 用來判斷是否有下個物件的依據。

Python 規範 __iter__ 特殊方法來傳回 iterator：

>>> names = ['Justin', 'Monica', 'Irene']
>>> it = iter(names) # 會呼叫 names.__iter__()
>>> next(it)         # 會呼叫 it.__next__()
'Justin'
>>> next(it)
'Monica'
>>> next(it)
'Irene'
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

Python 的 iterator 只需具有 __next__ 方法，若無法進一步迭代，要引發StopIteration，這是 for 語法停止迭代的依據。

無論實現形式為何，iterator 的精神在於，隱藏物件的內部實作，又能用一致的方式來取得物件想提供的訊息，其實這種概念也可用在非迭代的場合，只不過依情境而定，不會叫做 Iterator 罷了。

記得，Gof 的模式名稱，包含了它想解決的問題情境，OO 模式與 XX 模式可能名稱不同，然而看來實現形式很像是正常的，你應該看看它們面對的問題是什麼，而不是只看實現後的長相！