---
tags: 設計模式
---

# 迭代器模式(Iterator Pattern)
## 前言
- 在程式中 , 我們時常使用集合去儲存複數的元素(資料) --- 集合只是儲存複數資料的容器.
- 依據集合型態的不同 , 我們可能有不同的走訪/存取方式
- 現行常見的集合型態 Array / List / Stack / Queue 等等
- Iterator Pattern 通常早就被內化到現流行的程式語言中了
#### 問題需求
假設我們需要操作類似 Tree 結構這種複雜的資料. 我們可能會使用 List 去儲存. 再寫一個方法去走訪這個 List. 此時會發現若不使用 Iterator Pattern , 我們可能只能將 HighModuleA 的 IteratorByDFS 複製後 , 貼到 HighModuleB 去. 而這是不推薦的作法...

// 有兩個類別都需要使用 DFS 走訪 Tree 結構的資料
class HighModuleA<T> {
  private List<T> _list = new List<T>();
  //略...
  public IteratorByDFS(){
     // 使用 DFS 走訪 _list
  }
}

class HighModuleB<T> {
  private List<T> _list = new List<T>();
  //略...
  public IteratorByDFS(){
     // 使用 DFS 走訪 _list
  }
}

## Iterator 介紹
### 定義
> Iterator is a behavioral design pattern that lets you traverse elements of a collection without exposing its underlying representation (list, stack, tree, etc.).

> Provide a way to access the elements of an aggregate object sequentially without exposing it underlying representation.
> - Applicability
> - Need to access an aggregate object's contents without exposing its internal representation
> - Need to support multiple traversals of aggregate objects
> - Need to provide a uniform interface for traversing different aggregate structures
> - Consequences
> - Supports variation in the traversal of an aggregate
> - Simplifies the Aggregate interface
> - More than one traversal can be pending on an aggregate

- 提供至少一種方法(通常就一種)走訪集合的每一個成員 , 但又不需要暴露集合的內部實現.
- 抽取走訪的邏輯封裝(抽象化走訪的行為).

### UML
- Iterator : 介面或是抽象類別 , 負責定義完成走訪的動作需要實作哪些方法
- 通常有 MoveNext、CurrentItem、Fisrt、IsDone、Reset 之類的方法或屬性讓子類實作
- Aggregate : 介面或是抽象類別 , 負責定義如何調用實作 Iterator 的物件來負責走訪
- Aggregate **僅負責**將 Iterator 封裝後 , 再提供給外界使用
- Aggregate **僅負責**向外宣告自身是否具有走訪能力
- ConcreteAggregate
- 實作 Aggregate.
- ConcreteIteraror
- 實作 Iterator.

### 實作倒序走訪
- 未來任何需要倒序走訪的需求都可以使用 ConcreteAggregate 類別.
- 外界完全不需要知道倒序走訪的實作邏輯.
##### Iterator

public interface IIterator<out T>
{
    T GetItem();
    bool HasNext();
}

##### Aggregate

public interface IAggregate<out T>
{
    IIterator<T> GetIterator { get; }
}

##### ConcreteAggregate

public class ConcreteAggregate<T> : IAggregate<T>
{
    private readonly List<T> _items = new List<T>();
    public IIterator<T> GetIterator => new ConcreteIteratorDescending<T>(this);

    public T this[int index]
    {
        get => _items[index];
        set => _items[index] = value;
    }

    public int Count => _items.Count;
    public void Add(T item) => _items.Add(item);
}

##### ConcreteIteraror

public class ConcreteIteratorDescending<T> : IIterator<T>
{
    private readonly ConcreteAggregate<T> _collection;
    private int _currentIndex;
    public T GetItem() => _collection[_currentIndex--];
    public bool HasNext() => _currentIndex >= 0;
    public ConcreteIteratorDescending(ConcreteAggregate<T> collection)
    {
        _collection   = collection;
        _currentIndex = _collection.Count - 1;
    }
}

##### Client 端

internal static class Program
{
    private static void Main(string[] args)
    {
        var aggregate = new ConcreteAggregate<string>();
        aggregate.Add("牛魔王");
        aggregate.Add("馬面");
        aggregate.Add("牛頭");
        aggregate.Add("聖誕老人");

        Console.WriteLine("===========倒序走訪================");
        var iteratorDescending = aggregate.GetIterator;
        while (iteratorDescending.HasNext()) // 判斷是否有下一個
        {
            Console.WriteLine(iteratorDescending.GetItem());  // 走訪每一個成員
        }
        Console.WriteLine("===========倒序走訪================");
        var iteratorDescending2 = aggregate.GetIterator;
        while (iteratorDescending2.HasNext()) // 判斷是否有下一個
        {
            Console.WriteLine(iteratorDescending2.GetItem()); // 走訪每一個成員
        }
        Console.ReadKey();
    }
}

##### 結果

===========倒序走訪================
聖誕老人
牛頭
馬面
牛魔王
===========倒序走訪================
聖誕老人
牛頭
馬面
牛魔王

### 實作走訪整數
例如 : 517 , 會依序走訪 5 然後 1 然後 7
##### Iterator

public interface INtegerIterator
{
    object Current { get; }
    bool MoveNext();
    void Reset();
}

##### Aggregate

public interface IAggregate
{
    INtegerIterator GetIterator();
}

##### ConcreteAggregate

public class Integers : IAggregate
{
    private readonly int _integers;
    public Integers(int integers)
    {
        _integers = integers;
    }
    public INtegerIterator GetIterator() => new IntIterator(_integers);
}

##### ConcreteIteraror

public class IntIterator : INtegerIterator
{
    private readonly int _integers;
    private readonly int _maxDigit;
    private int _currentFilter;
    public object Current => (_integers / _currentFilter) % 10;
    public IntIterator(int integers)
    {
        _integers = integers;
        _maxDigit = (int)Math.Log10(integers) + 1;
        Reset();
    }

    public void Reset() => _currentFilter = (int)Math.Pow(10, _maxDigit);

    public bool MoveNext()
    {
        _currentFilter /= 10;
        bool hasNext = _currentFilter > 0;
        if (!hasNext) Reset();
        return hasNext;
    }
}

##### Client

static void Main(string[] args)
{
     Integers integers = new Integers(543838626);
     var iterator = integers.GetIterator();
     while (iterator.MoveNext())
     {
          Console.Write($"{ iterator.Current} ");
     }
     Console.WriteLine();
     while (iterator.MoveNext())
     {
          Console.Write($"{ iterator.Current} ");
     }
     Console.ReadKey();
}

##### 結果

5 4 3 8 3 8 6 2 6
5 4 3 8 3 8 6 2 6

## .Net 的 Iterator 實現
在 System.Collections 命名空間內 , 早就具有 Iterator 模式的實現. 也就是 IEnumerable (Aggregate) 以及 IEnumerator (Iterator) 這兩個介面的存在.

> book - C# 4.0 in Nutshell

根據上圖 , 我們可以知道 C# 常用的集合介面(ICollection、IList、IDictionary)都有繼承 IEnumerable 或是 IEnumerable<T> , 也因此實作這些集合界面的類別 , 也都具備資料走訪能力. 例如 : List<T>

### IEnumerable & IEnumerator & Enumerable & Enumerator
- 實作 IEnumerator 的任何類別概念上稱之為 Enumerator (列舉器)
- 實作 IEnumerable 的任何類別概念上稱之為 Enumerable
- Enumerator : a read-only, forward-only cursor over a sequence of values
* 實作介面
* System.Collections.IEnumerator
* System.Collections.Generic.IEnumerator<T>
* Enumerator 是實作 MoveNext()、Reset() 以及具有屬性 Current 的物件
- Enumerable : the logical representation of a sequence. It is not itself a cursor, but an object that produces cursors over itself
* 實作介面
* IEnumerable
* IEnumerable<T>
* Enumerable 必須實作一個回傳 Enumerator 的 GetEnumerator() 方法

#### IEnumerable & IEnumerator
- IEnumerable

    public interface IEnumerable // 表示具有走訪能力.
    {
        IEnumerator GetEnumerator();
    }

由 IEnumerable 這個介面可以知道 C# 對於資料集合是否可被列舉(走訪)的定義是 , 其是否具備取得 Enumerator(列舉器)的能力 , 換句話說實作介面 IEnumerable 代表此資料集合中的成員可以被列舉.
- IEnumerator

    public interface IEnumerator // 定義如何走訪
    {
        bool MoveNext();
        object Current { get; }
        void Reset();
    }

依據介面 IEnumerator 可以知道 Enumerator 負責將其所屬的資料集合中的成員 , 逐一取出並回傳. 因此其將實作 MoveNext() & Reset() 以及具有屬性 Current. 請參考下圖.
- Current 屬性 : 回傳**目前**走訪到的成員內容值.
- MoveNext() : 走訪到下一個成員 , 並回傳bool值來告知向下移動是否成功.
- Reset : 重置走訪的位置.

### foreach 語法
走訪所有元素的語法方式有兩種
- 採用 foreach
- 採用 GetEnumerator() 的方式

#### 範例

public class FiveElements : IEnumerable
{
     private string[] fiveElements = { "金", "木", "水", "火", "土" };
     public IEnumerator GetEnumerator() => new FiveElementsEnumerator(fiveElements);
}
    
public class FiveElementsEnumerator : IEnumerator
{
     private string[] fiveElements;
     private int index = -1;
     public FiveElementsEnumerator(string[] elements) => fiveElements = elements;
     public bool MoveNext() => ++index < fiveElements.Length;
     public object Current => fiveElements[index];
     public void Reset() => index = -1;
}

##### 測試程式

static void Main(string[] args)
{
     var fiveelements = new FiveElements();
     var enumerator = fiveelements.GetEnumerator();
     while (enumerator.MoveNext())
     {
          Console.Write(enumerator.Current);
     }

     Console.WriteLine();

     foreach (var item in fiveelements)
     {
          Console.Write(item);
     }

     Console.ReadKey();
}

##### 輸出結果

金木水火土       
金木水火土  

由上面範例可知 , foreach 語法其實就是採用 GetEnumerator 的方式實作 . 也就是說 foreach 其實是做了這四個步驟

- 呼叫 fiveelements.GetEnumerator() , 得到一個新的 IEnumerator.
- 呼叫 iterator.MoveNext() 以判斷走訪是否結束
- 如果 iterator.MoveNext() 回傳 false 代表走訪完畢.
- 反之如果回傳 true 則代表尚未走訪完畢 , 且會將 Current 指標移到下一個元素上.
- 回傳 Current 屬性 .
- 重複動作 2 & 3

### 實作走訪整數使用 IEnumerable & IEnumerator

public class Integers : IEnumerable
{
    private readonly int _integers;
    public Integers(int integers)
    {
        _integers = integers;
    }

    public IEnumerator GetEnumerator() => new IntIterator(_integers);
}

public class IntIterator : IEnumerator
{
    private readonly int _integers;
    private readonly int _maxDigit;
    private int _currentFilter;
    public object Current => (_integers / _currentFilter) % 10;
    public IntIterator(int integers)
    {
        _integers = integers;
        _maxDigit = (int)Math.Log10(integers) + 1;
        Reset();
    }

    public void Reset() => _currentFilter = (int)Math.Pow(10, _maxDigit);

    public bool MoveNext()
    {
        _currentFilter /= 10;
        bool hasNext = _currentFilter > 0;
        if (!hasNext) Reset();
        return hasNext;
    }
}

##### 測試程式

static void Main(string[] args)
{
    Integers integers = new Integers(54383862);
    var iterator = integers.GetEnumerator();
    while (iterator.MoveNext())
    {
        Console.Write($"{ iterator.Current} ");
    }
    Console.WriteLine();
    foreach (var item in integers)
    {
        Console.Write($"{ item } ");
    }
    Console.ReadKey();
}  

##### 輸出結果

## Yield
Yield 是 C# 提供的語法糖 --- 用來簡化實作 Iterator 的過程.

### [Iterators](https://docs.microsoft.com/zh-tw/dotnet/csharp/programming-guide/concepts/iterators) & [yield](https://docs.microsoft.com/zh-tw/dotnet/csharp/language-reference/keywords/yield)
> yield 在 .Net 2.0 時提供

> 當編譯器偵測到迭代器時，它會**自動產生**IEnumerator 或 IEnumerator<T> 介面的 Current、MoveNext 和 Dispose 方法。

> 迭代器方法使用 yield return 陳述式，一次傳回一個項目。 當到達 yield return 陳述式時，系統會記住程式碼中的目前位置。下次呼叫迭代器函式時，便會從這個位置重新開始執行。

> 可以使用 yield break 陳述式結束反覆項目

> 每次反覆運算foreach迴圈 (或直接呼叫 IEnumerator.MoveNext)，下一個迭代器程式碼主體都會在上一個 yield return 陳述式之後繼續。 然後繼續執行至下一個 yield return 陳述式，直到達到迭代器主體結尾，或遇到 yield break 陳述式為止。

> 迭代器的宣告必須符合下列需求：傳回型別必須是下列其中一種類型：
> - IAsyncEnumerable<T>
> - IEnumerable<T>
> - IEnumerable
> - IEnumerator<T>
> - IEnumerator
>
> 宣告不能有任何 in、 ref或 out 參數。
> 傳回 yield 或 IEnumerable 的 IEnumerator 類型迭代器為 object。 如果反覆運算器傳回 IEnumerable<T> 或 IEnumerator<T> ，則必須從語句中的運算式類型 yield return 到泛型型別參數進行隱含轉換。您無法在下列項目中包含 yield return 或 yield break 陳述式：Lambda 運算式與匿名方法。包含不安全區塊的方法。 如需詳細資訊，請參閱 unsafe。

- yield 可幫助自動產生走訪器 , 因此我們不必自行定義一個實現 IEnumerator 的類別.
- 當程式執行到 yield return 時 , 程式會記住目前的程式碼位置 , 再回傳結果. 因此當需要走訪下一個成員時 , 就會從此位置繼續執行.
- 當程式執行到 yield break 時 , 會直接結束走訪.

#### 不使用 yield 完成走訪功能

public class DaysOfTheWeek : IEnumerable
{
     private readonly string[] _days = { "Sun", "Mon", "Tue", "Wed", "Thr", "Fri", "Sat"};
     public IEnumerator GetEnumerator() => new DaysOfTheWeekEnumerator(_days);
}

public class DaysOfTheWeekEnumerator : IEnumerator
{
     private int _index = -1;
     private string[] _days;
     public DaysOfTheWeekEnumerator(string[] days) => _days = days;
     public object Current => _days[_index];
     public bool MoveNext() => ++_index < _days.Length;
     public void Reset() => _index = -1;
}

// 測試程式
static void Main(string[] args)
{
     DaysOfTheWeek week = new DaysOfTheWeek();

     foreach (string day in week)
     {
          Console.Write(day + " ");
     }

     Console.WriteLine();

     var emumerator = week.GetEnumerator();
     while (emumerator.MoveNext())
     {
          Console.Write(emumerator.Current + " ");
     }

     Console.ReadKey();
}

##### 輸出結果

#### 使用 yield 完成走訪功能

// yield 可幫助自動產生走訪器 , 因此我們不必自行定義一個實現 IEnumerator 的類別.
public class DaysOfTheWeek : IEnumerable
{
     private readonly string[] _days = { "Sun", "Mon", "Tue", "Wed", "Thr", "Fri", "Sat" };
     public IEnumerator GetEnumerator()
     {
          for (int i = 0; i < m_Days.Length; i++)
          {
               yield return _days[i];
          }
     }
}

// 測試程式
static void Main(string[] args)
{
     DaysOfTheWeek week = new DaysOfTheWeek();

     foreach (string day in week)
     {
          Console.Write(day + " ");
     }

     Console.WriteLine();

     var emumerator = week.GetEnumerator();
     while (emumerator.MoveNext())
     {
          Console.Write(emumerator.Current + " ");
     }

     Console.ReadKey();
}

##### 輸出結果

### yield break
- 結束走訪

#### 不使用 yield break 實作走訪 list 內成員

public class CityManger
{
    public static IEnumerable<T> GetEnumerable<T>(List<T> _numbers)
                => new Enumerable<T>(_numbers);
}

public class Enumerable<T> : IEnumerable<T>
{
    private readonly List<T> _list;
    public Enumerable(List<T> list) => _list = list;
    public IEnumerator<T> GetEnumerator() => new Enumerator<T>(_list);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

public class Enumerator<T> : IEnumerator<T>
{
    private List<T> _list;
    private int _index = -1;
    public Enumerator(List<T> list) => _list = list;
    public T Current => _list[_index];
    object IEnumerator.Current => Current;

    public bool MoveNext()
    {
        if (_index != -1 && _list[_index].Equals(3))
            return false;
        return ++_index < _list.Count;
    }

    public void Reset() => _index = -1;
    public void Dispose() => _list = null;
}


##### 使用 yield break 實作走訪 list 內成員

public class CityManager
{
     public static IEnumerable<int> GetEnumerable(List<int> _numbers)
     {
          foreach (var num in _numbers)
          {
               Console.WriteLine($"執行yield return前, 數值為:{num}");
               if (num == 3)
               {
                    Console.WriteLine("數值為3, 呼叫yield break");
                    yield break;
               }
               yield return num;
               Console.WriteLine($"執行yield return後的下一行, 數值為:{num}");
          }
     }
}

static void Main(string[] args)
{
     var enumerable = CityManger.GetEnumerable(new List<int>(){ 6, 5, 3, 13, 9, 8, 7 });

     Console.WriteLine($"執行了foreach之前");
     foreach (var num in enumerable)
     {
          Console.WriteLine($"foreach - 現在的值是{num}");
          Console.WriteLine($"數字:{num}處理完畢.跳下一個數字");
          Console.WriteLine();
     }

     Console.WriteLine($"------------分隔線----------------");

     var enumerator = enumerable.GetEnumerator();
     Console.WriteLine($"執行了while之前");
     while (enumerator.MoveNext())
     {
          Console.WriteLine($"while - 現在的值是{enumerator.Current}");
          Console.WriteLine($"數字:{enumerator.Current}處理完畢.跳下一個數字");
          Console.WriteLine();
     }

     Console.ReadKey();
}

##### 輸出結果

由上面的範例 我們可以知道執行順序是
1. foreach & in 在執行時會呼叫 MoveNext() , 然後取出 Current 的值
1. 取出 Current 的值後 , 執行 foreach 主體.
1. foreach 要取下一個 Item 時 , 會呼叫 MoveNext() , 此時會從剛剛的 yield return 處下一行開始執行.
1. 上述三個動作會重複執行 , 直到走訪完畢或是碰到 yield break 為止.

## 總結
- 使用 yield return 可以輕鬆建立一個 IEnumerable<T> 的資料集合.
- 執行 yield return 後 , 下一次被呼叫時 , 會繼續從上一次的 yield return 後開始執行.
- 呼叫 yield break 後 , 會離開 foreach 主體.
- 如果一個區塊(block)中有 yield 陳述式，則此區塊就叫做 Iterator Block
- 一個方法的區塊如果是 Iterator Block , 則它的回傳值會是 IEnumerable 或是IEnumerator. 請參考[C# 語言規格-類別](https://docs.microsoft.com/zh-tw/dotnet/csharp/language-reference/language-specification/classes#iterators)
> Iterator 會產生一系列的值，這些都是相同的型別。 這個型別稱為 iterator 的yield 型別。
> - 傳回IEnumerator object或IEnumerable的反覆運算器產生類型為 object。
> - 傳回IEnumerator<T> T或IEnumerable<T>的反覆運算器產生類型為 T。
> - 
- 自定義的資料集合類別要具備**可被列舉**的能力 , 需實作 IEnumerable 或是 IEnumerable<T>
- 實作 IEnumerable 與 IEnumerable<T> 界面 , 需要實作 GetEnumerator() 用來回傳列舉器(Enumerator)物件 - 實作IEnumerator
- 列舉器(Enumerator)是實作走訪各個資料元素的類別的物件
- > 引用91大的blog
- Iterator 模式使得走訪一個資料集合的時候 , 無須暴露它的內部細節.
- Iterator 模式為走訪不同的資料結構提供一個統一的接口. 因此即使資料結構改變 , 走訪行為(呼叫 foreach 的語法) 也不需要更改.
- Iterator 模式在**走訪的時候更改 Iterator 所在的資料會拋出例外** , 所以 foreach 只能用在走訪 , 而**不能在走訪的時候同時修改資料集合內的元素**.
- 為了可以做到不暴露集合內部結構同時又可讓外部使用者走訪集合內部的資料 , Iterator 模式**抽象 Iterator 類來分離集合的走訪行為** ,
- Iterator 模式將複雜的走訪行為邏輯抽離到 Iterator 類專門負責 , 這遵守了單一職責的要求. 另外未來若需要新增新的走訪邏輯 , 只需要再實做新的 Iterator 即可 , 不需要修改現有程式碼 , 這又完成了開放封閉原則的要求.
- 可以平行走訪同一個集合 , 因為每個列舉器(Enumerator)都擁有自己的走訪狀態.
- 可以暫停走訪 , 並在需要時 , 繼續走訪 , 只要擁有同一個列舉器(Enumerator).

## 參考
[Iterator](https://refactoring.guru/design-patterns/iterator)
[Iterators MSDN ](https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/iterators)
[[Design Pattern] Iterator 迭代器模式](https://ithelp.ithome.com.tw/articles/10224707)
[Iterator pattern](https://en.wikipedia.org/wiki/Iterator_pattern)
[走訪(Traverse)](https://www.quora.com/What-is-traversing)
[Iterators](https://docs.microsoft.com/zh-tw/dotnet/csharp/programming-guide/concepts/iterators)
[yield](https://docs.microsoft.com/zh-tw/dotnet/csharp/language-reference/keywords/yield)
[LINQ基礎 - Yield](https://hackmd.io/@CityChen/rJ5tL9uMH)
[LINQ基礎 - IEnumerable & IEnumerator](https://hackmd.io/@CityChen/r13OGAZzB)
[LINQ基礎 - Iterator(疊代器模式)](https://hackmd.io/@CityChen/r1cJBSJGS)
[IEnumerable<T> 介面](https://docs.microsoft.com/zh-tw/dotnet/api/system.collections.generic.ienumerable-1?view=net-6.0)
[Programming Patterns Overview](https://kremer.cpsc.ucalgary.ca/patterns/)

---

###### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep:

<iframe src="https://skilltree.my/c67b0d8a-9b69-47ce-a50d-c3fc60090493/promotion?w=250" width="250" style="border:none"></iframe>