天天看點
傳回

自己動手，實作一種類似List<T>的資料結構(一）

前言

上一篇文章《Unity3D中常用的資料結構總結與分析》簡單總結了一下小匹夫工作中經常遇到的一些資料結構。不過小匹夫一直有種觀點，就是光說的熱鬧實際啥也不做真的沒啥意思。光說不練假把式，那麼這篇文章不如記錄一下小匹夫自己動手實作一個有類似功能的資料結構的過程吧。

模仿List<T>

尋思半天，寫代碼是為了啥？不是為了寫以緻用嘛?那麼小匹夫工作中用的最多的資料結構是啥？思來想去還就是List<T>了，而且平時使用的時候的确也覺得有自己定制的空間。作為一個類，重要的無非是它的名字，構造函數，屬性和各種方法，因為小匹夫喜歡吃雞蛋，再加上一個好朋友的喵叫蛋殼，是以咱們的新資料結構就叫做EggArray<T>好了，既然是要模仿List<T>，那麼定好類名之後我們自然需要去參考一下List<T>的構造函數，屬性和方法（列出的都是公有的）進而進一步來确定我們自己的類成員咯。不過呢，首先我們要先明确我們自己的EggArray<T>到底需要怎麼實作，以及實作哪些功能，List<T>隻是我們模仿的對象，如果實作的還都是List<T>自己的那一套，我們也就沒有什麼必要做現在的這些事情了。

EggArray<T>是什麼

上一篇文章分析過，List<T>的内部其實也是一個Array，且是強類型的，是以我們的EggArray<T>也秉承這個特點，内部通過一個Array來實作，且需要聲明類型。但是同時我們也看到List<T>繼承和實作了很多接口，比如能實作foreach方法的IEnumerable接口等，而且值類型和引用類型通吃。這裡為了EggArray<T>實作起來輕裝簡行，我們不繼承List<T>繼承的各種接口，同時我們的EggArray隻服務于引用類型。（也是從友善和使用的角度考慮，畢竟值類型不能指派null，引用類型可以指派null這一點，作為一個部落格的内容就沒有必要去考慮服務值類型了）。那麼小夥伴可能想問了，不繼承那些接口，像最基本的foreach這種需求是不是匹夫混蛋你就不想實作了？NO,NO，俗話說得好，"車到山前必有路，聽說委托也不錯"。。。咳咳扯遠了，其實也很簡單，小匹夫上上篇文章《Unity3D中使用委托和事件（一）》介紹過的委托代理其實就可以用來實作EggArray<T>的foreach功能，甚至還有好多小匹夫自己定制的功能，比如Map，Filter，Without之類的。下面具體實作的時候小匹夫還會再扯。

EggArray<T>的成員

那麼明确了大的方向，再經過小匹夫自己的定制，對List<T>的成員進行增減之後，我們的EggArray<T>類和它的成員（變量&&屬性，構造函數，私有方法，公有方法，小匹夫定制方法（在下一篇中說））如下：

EggArray類 

//EggArray類
public class EggArray<T> where T : class
{
}

屬性&變量(暫定，下一篇還會根據情況擴充)：

屬性 說明
Capacity EggArray的容量
Count EggArray中的元素個數
items T[]，一個Array，因為上一篇文章說過List<T>的内部其實還是Array，是以内部我們也使用Array
foreachHandler 一個delegate，用來實作foreach的功能 
//EggArray<T>的屬性&&變量
private int capacity;
private int count;
private T[] items;
public delegate void foreachHandler(T item);

public int Count
{
    get
    {
        return this.count;
    }
}

public int Capacity
{
    get
    {
        return this.capacity;
    }
}

構造函數：

構造函數
EggArray() 初始化 EggArray<T> 類的新執行個體，該執行個體為空并且具有預設初始容量。
EggArray(int32) 初始化 EggArray<T> 類的新執行個體，該執行個體為空并且具有指定的初始容量。 
//EggArray的構造函數，預設容量為8
public EggArray() : this(8)
{
}

public EggArray(int capacity)
{
    this.capacity = capacity;
    this.items = new T[capacity];
}

下面就是EggArray的各種方法了，上文小匹夫已經說過了，咱們這裡隻是參考List<T>列出來的一些公共方法，有一些List<T>爛大街的方法比如Add，Rmove這些公共方法肯定都是要實作的，可是一些私有方法咱們平時接觸不到呀，甚至在List<T>也沒有查到。那麼小匹夫覺得很重要，也很能展現咱們EggArray<T>長度十分靈活特點的一個私有方法，應該就非那個能靈活改變數組長度的方法莫屬了吧？我們稱之為Resize()好了。

小匹夫還說過要自己定制一些平時會用到，但List<T>并沒有現成方法的方法了。比如把EggArray<T>中的每個值映射到一個新的數組中的Map方法，周遊List中的每個值，傳回包含所有通過predicate真值檢測的元素值的Filter方法，或者是周遊List，以List中的元素的某個成員進行排序的indexBy

方法，還有傳回一個除去所有null值的Compact方法等等。下面就按照這3類不同的方法列出來我們的EggArray<T>中的方法。

私有方法

Resize 當數組元素個數大于或等于數組的容量時，調用該方法進行擴容，會建立一個新的Array存放資料，“增長因子”為2 
//當數組元素個數不小于數組容量時，需要擴容，增長因子growthFactor為2
private void Resize()
{
    int capacity = this.capacity * growthFactor;
    if (this.count > capacity)
    {
        this.count = capacity;
    }
    T[] destinationArray = new T[capacity];
    Array.Copy(this.items, destinationArray, this.count);
    this.items = destinationArray;
    this.capacity = capacity;
}

公共方法(List<T>也有的)

公共方法
Add 将對象添加到 EggArray<T> 的結尾處。
AddRange 将指定集合的元素添加到 EggArray<T> 的末尾。
Insert 将元素插入 EggArray<T> 的指定索引處。
Contains 确定某元素是否在 EggArray<T> 中。
Clear 從 EggArray<T> 中移除所有元素。
ToArray 将 EggArray<T> 的元素複制到新數組中。
Sort 使用預設比較器對整個 EggArray<T> 中的元素進行排序。
Foreach 對 EggArray<T> 的每個元素執行指定操作。
Remove 從 EggArray<T> 中移除特定對象的第一個比對項。
RemoveAt 移除 EggArray<T> 的指定索引處的元素。
Find 搜尋與指定謂詞所定義的條件相比對的元素，并傳回整個 EggArray<T> 中的第一個比對元素。
IndexOf 搜尋指定的對象，并傳回整個 EggArray<T> 中第一個比對項的從零開始的索引。 
///List<T>已有的功能
/// <summary>
/// Add the specified item.
/// </summary>
/// <param name="item">Item.</param>
public void Add(T item)
{
    if (this.count >= this.capacity)
    {
        this.Resize();
    }
    this.items[this.count++] = item;
}
/// <summary>
/// Adds the range.
/// </summary>
/// <param name="collection">Collection.</param>
public void AddRange(IEnumerable<T> collection)
{
    if (collection != null)
    {
        foreach (T current in collection)
        {
            this.Add(current);
        }
    }
}
/// <summary>
/// Insert the specified index and item.
/// </summary>
/// <param name="index">Index.</param>
/// <param name="item">Item.</param>
public void Insert(int index, T item)
{
    if (this.count >= this.capacity)
    {
        this.Resize();
    }
    this.count++;
    for (int i = this.count - 1; i > index; i--)
    {
        this.items[i] = this.items[i - 1];
    }
    this.items[index] = item;
}
/// <summary>
/// Contains the specified arg.
/// </summary>
/// <param name="arg">Argument.</param>
public bool Contains(T arg)
{
    for (int i = 0; i < this.count; i++)
    {
        if (this.items[i].Equals(arg))
        {
            return true;
        }
    }
    return false;
}
/// <summary>
/// Clear this instance.
/// </summary>
public void Clear()
{
    if (this.count > 0)
    {
        for (int i = 0; i < this.count; i++)
        {
            this.items[i] = null;
        }
        this.count = 0;
    }
}
/// <summary>
/// Tos the array.
/// </summary>
/// <param name="array">Array.</param>
public void ToArray(T[] array)
{
    if (array != null)
    {
        for (int i = 0; i < this.count; i++)
        {
            array[i] = this.items[i];
        }
    }
}
/// <summary>
/// Sort the specified comparer.
/// </summary>
/// <param name="comparer">Comparer.</param>
public void Sort(IComparer<T> comparer)
{
    Array.Sort<T>(this.items, 0, this.count, comparer);
}
/// <summary>
/// Foreach the specified handler.
/// </summary>
/// <param name="handler">Handler.</param>
public void Foreach(EggArray<T>.IterationHandler handler)
{
    for (int i = 0; i < this.count; i++)
    {
        handler(this.items[i]);
    }
}
/// <summary>
/// Remove the specified arg.
/// </summary>
/// <param name="arg">Argument.</param>
public bool Remove(T arg)
{
    for (int i = 0; i < this.count; i++)
    {
        if (this.items[i].Equals(arg))
        {
            this.items[i] = null;
            this.Compact();
            return true;
        }
    }
    return false;
}
/// <summary>
/// Removes at index.
/// </summary>
/// <param name="index">Index.</param>
public void RemoveAt(int index)
{
    if (index < this.count)
    {
        this.items[index] = null;
        this.Compact();
    }
}

/// <summary>
/// Indexs the of.
/// </summary>
/// <returns>The of.</returns>
/// <param name="arg">Argument.</param>
public int IndexOf(T arg)
{
    for (int i = 0; i < this.count; i++)
    {
        if (this.items[i].Equals(arg))
        {
            return i;
        }
    }
    return -1;
}

以上便是我們仿照List<T>的公共方法所要實作的我們自己的公共方法，但是看說明我們很快就能發現一個問題。啥嘞？對嘞，就是很多方法都有方向性。比如Add方法，是将新的對象添加到EggArray<T>的末尾，可是我想要加到最開始怎麼辦。又或者Find方法，傳回第一個滿足條件的元素，但是要是我想要找最後一個比對的呢？類似的問題還存在于IndexOf，Remove等等。是以這就是我們定制我們自己方法的定制思路之一：為了拓展已有方法的适用範圍。(關于兩端操作，大家想到了什麼嗎？沒錯，就是LinkedList，但是LinkedList本質上是連結清單，而我們的内部實作其實是Array，是以隻是借鑒一下LinkedList的功能而非實作方法。其實這裡對insert方法的實作就能看出和EggArray内部同為Array的List<T>在進行中間插入新的元素是多蛋疼的一件事情)

但是我們回到List<T>的MSDN頁面，看看羅列出來的公有方法，總覺得少了點什麼。哎？最直覺的，貌似沒有Slice呀。或者是我想做一些有限的過濾功能以得到符合我們簡單需求的新數組，哎？貌似也沒有Filter之類的功能？其實我們還有好多需求。。。那麼我們第二條定制思路就有了：為了實作List<T>沒有實作而我們日常需要用到的功能。在繼續下面的内容之前，還是要簡單說明一下幾個需要注意的點。

  1. Insert方法，上面已經說過了，處理元素插入時，數組是不如連結清單的。
  2. Contains、IndexOf等方法，這裡需要說明一下，在這些方法中我使用了.equles來判斷作為參數傳入的元素是否與數組内的元素值相同。作為一個處理引用類型的資料結構，我還是要說明一下equles和==的差別，即equals是比較他們的值，而==相當于比較它們在堆中的位置！即==判斷的是是否是同一個對象。為了嚴謹，下面還将引入用==進行比較确定元素身份的方法。
  3. Foreach的實作手段，如上文所述，我們并沒有繼承和實作那麼多接口，是以List<T>實作Foreach的手段我們就無法使用了。但是想想Foreach的目的無法就是周遊的過程中進行一些自己需要的操作，是以這裡我使用了delegate來實作這一點。同樣，Find這樣的功能也可以通過delegate來實作，關于Find的實作放在下面的代碼中了。

好啦，上面就是這篇文章的内容了，因為斷斷續續寫了一周是以内容有點多，如果都盛放在一篇裡面，可能連小匹夫都要有點密集恐懼症了。那麼在下一篇文章《自己動手，實作一種類似List<T>的資料結構(二）》中，小匹夫将詳細介紹下小匹夫覺得有用且有趣的方法。

裝模作樣的聲明一下：本博文章若非特殊注明皆為原創，若需轉載請保留原文連結及作者資訊慕容小匹夫

自己動手，實作一種類似List&lt;T&gt;的資料結構(一）

本作品采用知識共享署名-非商業性使用-相同方式共享 2.5 中國大陸許可協定進行許可，我的部落格歡迎複制共享，但在同時，希望保留我的署名權陳嘉棟（慕容小匹夫），并且，不得用于商業用途。如您有任何疑問或者授權方面的協商，請給我留言。

知乎專欄：

Runtime

聯系方式：

Email：[email protected]

unity3D 資料結構 c#
上一篇: JS or C#？不存在的腳本之争
下一篇: 自己動手，實作一種類似List&lt;T&gt;的資料結構（二）

繼續閱讀