定義

• Iterator Pattern 提供一種方式讓你依序存取物件集合 (Aggregate) 的元素，而且不會公開它物件的底層表示法 (By GoF)
• 資料結構和演算法經常會緊密相連。許多情況，演算法需要訪問 (Access, Traverse) 和操作 (Operate) 資料結構中的元素。然而，暴露資料結構的內部細節可能會導致設計上的問題:
  • 算法和資結的耦合: 降低可維護性
  • 彈性低: 困難於增加或修改資料結構 (例如，Client 使用某一種演算法去迭代物件，當底層物件被更換時，演算法操作物件的實作部分也須要跟著修正)

組成

• Iterator: 負責定義訪問和遍歷元素的接口
• ConcreteIterator: 實現 Iterator 接口
• Aggregate: 定義創建 Iterator 的接口 (註: 在此為一群物件「集合」的概念，亦可稱 Collection)
• ConcreteAggregate: 實現 Aggregate 並返回 ConcreteIterator

範例

// Iterator interface
class Iterator {
public:
    virtual bool hasNext() = 0;
    virtual int next() = 0;
};

// Concrete Iterator (Array)
class ArrayIterator : public Iterator {
private:
    int arr[5] = {1, 2, 3, 4, 5};
    int index = 0;
public:
    bool hasNext() override {
        return index < 5;
    }

    int next() override {
        return arr[index++];
    }
};

// Concrete Iterator (Vector)
class VectorIterator : public Iterator {
private:
    std::vector<int> vec = {6, 7, 8, 9, 10};
    
    // 註: Iterator 是一種設計模式，實作的資料結構內部再度使用程式語言所提供的內建 Iterator 也不少見
    // 這時就更體現出迭代器模式可以隱藏內部實作細節的好處
    std::vector<int>::iterator it; 
public:
    VectorIterator() {
        it = vec.begin();
    }

    bool hasNext() override {
        return it != vec.end();
    }

    int next() override {
        return *(it++);
    }
};

// Aggregate interface
class Aggregate {
public:
    virtual Iterator* createIterator() = 0;
};

// Concrete Aggregate
class ConcreteAggregate : public Aggregate {
public:
    Iterator* createIterator() override {
        /* 可以自行選擇要使用哪一種 iterator 的底層實作 (簡略範例) */
        // 1. Array
        return new ArrayIterator();
        // 2. Vector 
        return new VectorIterator();
    }
};

// Client
int main() {
    Aggregate* aggregate = new ConcreteAggregate();
    Iterator* iterator = aggregate->createIterator();

    while(iterator->hasNext()) {
        std::cout << iterator->next() << std::endl;
    }
}

分析

• 優點:
  • 資料隱藏 (Data Hiding): 尤其當你不希望暴露資料結構的內部結構時
  • 演算法與資料結構解耦 (Decoupling)
  • 實踐單一職責原則(SRP): Iterator 負責遍歷，Aggregate 負責資料儲存
  • 實踐開放封閉原則(OCP): 可以增加實作新型態的 collections(集合) 和 iterators(迭代器)，而不用修改現有程式碼
• 缺點:
  • 增加複雜性: 新增多個類別和接口
  • 效能影響: 可能會稍微影響遍歷 (Iterate, Traverse) 的效能

與其他模式的搭配

Iterator 非常適合與許多設計模式搭配

• 可以使用 Iterator 來遍歷組合模式(Composite)的樹狀結構
• 可以結合使用工廠方法(Factory Method)和迭代器(Iterator)讓集合的子類別返回與集合相容的不同類型的迭代器
• 可以使用備忘錄模式(Memento)和 Iterator 來捕捉(capture)當前迭代狀態，並可在必要時將其撤回(roll back)
• 可以使用訪問者模式(Visitor)和 Iterator 來遍歷複雜的數據結構，並對其元素執行一些操作，即使它們都具有不同的類別

[補充] External vs Internal Iterator (概念)

External Iterator:

• 控制權在用戶手上: 用戶必須明確地呼叫 next() 和 hasNext() 方法來遍歷元素
• 更高靈活性: 因為控制權在用戶手上，所以用戶可以更自由地控制遍歷的過程
• C++ 範例: STL 中的 begin() 和 end() 通常返回一個 external iterator

std::vector<int> vec = {1, 2, 3};
for(auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << std::endl;
}

Internal Iterator:

• 控制權在集合本身: 集合負責遍歷自己的所有元素，只需對用戶提供一個操作每個元素的函數
• 簡潔性和易用性: 用戶不需要親自管理 Iterator 的生命週期
• C++ 範例: 使用 std::for_each 是 internal iterator 的一個例子

std::vector<int> vec = {1, 2, 3};
std::for_each(vec.begin(), vec.end(), [](int n) {
    std::cout << n << std::endl;
});

Reference

1. https://refactoring.guru/design-patterns/iterator
2. https://ithelp.ithome.com.tw/articles/10224707
3. https://www.geeksforgeeks.org/iterator-pattern/