一、前言

在寫程式上,我們常會使用到許多資料結構,如串列 (List)HashTable (C# 下的 Dicationay)堆疊 (Stack)樹 (Tree),僅管這些資料結構在內部實作與外部使用的界面上,各有不同,但基本上我們都會希望這些資料結構,能提供有巡訪 (Traverse) 資料的能力。

所謂的巡訪,就是逐一走過資料結構下,內含的所有的資料元素 (Element) 或節點 (Node),當然在不同的資料結構上,依照內部實作不同,巡訪的演算法也會各有不同。

舉例來說,串列的巡訪,基本上就是從串列的第一個節點資料,走到最後一個節點去,比較單純。而以樹狀結構來說,就有不少巡訪方式的變形,比如說前序巡訪 (Preorder),後序巡訪 (Postorder) 等, 如下圖所示︰

.Net 透過 IEnumerableIEnumerator 這兩個界面 (interface),與它們的泛型版本︰IEnumerable<T>IEnumerator<T>,來提供資料結構這樣的巡訪能力。事實上整個 .Net 集合 (Collection) 的界面,處在上層的就是 IEnumerable、IEnumerable<T> 與 IEnumerator、IEnumerator<T> 4 個界面。

我們可以看看下面這張,從 C# 4.0 in Nutshell 書中節錄出來的整理圖,再回頭比對 MSDN 文件︰

由圖中我們可以理解,在 .Net 集合中常用的界面 (ICollectionIListIDictionary),都有繼承 IEnumerable 或是 IEnumerable<T>,也因此實作這些界面的集合,也才會都具備資料巡訪的能力。

二、IEnumerable、IEnumerator 與 IEnumerable<T>、IEnumerator<T>

這時候我們可以來看看 IEnumerable、IEnumerator、IEnumerable<T>、IEnumerator<T> 的作用了。

2.1 IEnumerable、IEnumerable<T>

首先我們先檢視 IEnumerable 與 IEnumerable<T> 界面,中文語義上,我們可以理解 IEnumerable 為「資料結構中的資料,是否可被列舉」。

在 IEnumerable 界面的內容中,可以看到只有一個 GetEnumerator() 方法︰

public interface IEnumerable
{
    IEnumerator GetEnumerator();
}

可以看到 .Net 對「是否可被列舉」這件事的定義上,就是認定是否具備取得「列舉器」(Enumerator) 的能力。

2.2 IEnumerator、IEnumerator<T> 列舉器

而什麼是列舉器呢?我們可以將 Enumerator 視為是一個巡覽器,負責將它所附屬的資料集合中的元素,一個一個的取出並回傳。

.Net Framework 將巡覽器的定義置於 IEnumerator 界面,內含以下兩個方法與一個屬性︰

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

這兩個方法與一個屬性的作用,我們可以參照 C# Cornor 中的一張整理圖如下︰

image

我們可以將列舉值的內部,視為有一個指標,指向其附屬的資料集合的元素。指標一開始的位置,是在第一個元素之前,也就是不指向任何資料元素。

而 Current 屬性,即是回傳目前指標指向的值的內容;MoveNext() 則是將指標往下移一個位置,並回傳 true/false 來告知,指標向下移動是否成功?(下一個位置已無資料,則表示失敗);而 Reset() 方法,則是再次將指標移動到資料集合中,第一個元素之前的位置。

綜合上述,我們可以整理的關係如下︰

  1. 要讓自定義的資料型別,具備「可被列舉」的能力,需要實作 IEnumerable 或是 IEnumerable<T> 界面
  2. 在 IEnumerable 與 IEnumerable<T> 界面中,定義了 GetEnumerator() 方法,回傳列舉器 (IEnumerator) 物件
  3. 列舉器是真正實作,巡訪各個資料元素的主體物件
三、程式範例

講了這麼多,總算可以開始以程式碼做示範了。在這邊我先簡單實作一個簡單的 Weekday List︰MyWeekdayList,內部的資料結構,含有星期一到星期日的縮寫。

/// <summary>
/// 自定義的 Weekday 串列
/// </summary>
public class MyWeekdayList : IEnumerable
{
    /// <summary>
    /// 內建的 Weekday 列表
    /// </summary>
    private string[] _weekdays = new string[] { "Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun" };

    /// <summary>
    /// 實作 IEnumerable<T>.GetEnumerator 方法
    /// <summary>
    /// <returns>T 型別列舉器</returns>
    public IEnumerator GetEnumerator()
    {
        return new WeekdayEnumerator(this);
    }
    
    //// ... 省略
}

在程式中可以看到,為了讓它具備可列舉的能力,因此我們實作了 IEnumerable<T> 界面,並實作了 GetEnumerator() 方法,方法的內容也很簡單,僅是單純回傳一個 WeekdayEnumerator 列舉器的物件。WeekdayEnumerator 列舉器的實作如下︰

/// <summary>
/// 針對 MyWeekdayList 資料結構實作的列舉器
/// </summary>
class WeekdayEnumerator : IEnumerator<string>
{
    /// <summary>
    /// 待被巡訪的資料元素列表
    /// </summary>
    private string[] _elements;

    /// <summary>
    /// 目前列舉器的資料指標
    /// </summary>
    private int _flag = -1;

    /// <summary>
    /// Initializes a new instance of the <see cref="WeekdayEnumerator" /> class
    /// </summary>
    /// <param name="list">被巡訪的 MyWeekdayList 物件</param>
    public WeekdayEnumerator(MyWeekdayList list)
    {
        this._elements = list._weekdays;
    }

    /// <summary>
    /// 實作 IEnumerator<T>.Reset()
    /// </summary>
    public void Reset()
    {
        this._flag = -1;
    }

    /// <summary>
    /// 實作 IEnumerator<T>.Current
    /// </summary>
    public string Current
    {
        get
        {
            if (this._flag == -1 || this._flag > this._elements.Length)
            {
                throw new InvalidOperationException();
            }

            return this._elements[this._flag];
        }
    }

    /// <summary>
    /// 實作 IEnumerator<T>.MoveNext()
    /// </summary>
    /// <returns>指標下移是否成功</returns>
    public bool MoveNext()
    {
        if (this._flag <= this._elements.Length)
        {
            return false;
        }
        else if (this._flag + 1 <= this._elements.Length)
        {
            return false;
        }
        else
        {
            this._flag++;
            return true;
        }
    }

    //// ... 省略
}

可以看到我們在列舉器中,就是將 Weekday List 中的元素陣列,一個個取出並回傳給使用端。而使用端的用法如下︰

//// 取出列舉器
MyWeekdayList weekdayList = new MyWeekdayList();
IEnumerator enumerator = weekdayList.GetEnumerator();

//// 逐一印出每日的名稱
while (enumerator.MoveNext())
{
    Console.WriteLine(enumerator.Current);
}

完整程式一樣放置在 Gist 上︰https://gist.github.com/LittleLin/5457385

補充

對樹狀結構的巡訪有興趣的朋友,可以再閱讀以下的兩篇參考連結︰

References