Iterator

January 2, 2022

你想寫個資料結構程式庫,其中有 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;
    }
}

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

探索內部的物件

問題在於,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());
    }
}

例如,顯示 ArrayListHashSet 收集的元素,就可以這麼寫:

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 方法,然而傳回的物件必須具有 valuedone 特性,donefor 用來判斷是否有下個物件的依據。

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 模式可能名稱不同,然而看來實現形式很像是正常的,你應該看看它們面對的問題是什麼,而不是只看實現後的長相!