[資料結構-線性表1.1] 陣列（.NET原始碼學習）

陣列，一種資料型別（在絕大數語言中不是基本資料型別）且為參照型別，在記憶體中以連續的記憶體單元進行分配，所以其大小在建立物件後為定值，不可更改。

一．記憶體分配

對於兩種不同資料型別而言，其記憶體分配方式是不同的。值型別直接在棧（C#中稱為堆疊Stack）上分配，將其儲存的內容直接存放到棧中；參照型別則是將指向範例物件的地址存在棧中，對該地址進行解析後獲得一個在堆（此處，C#中稱為託管堆）中的位置，這個位置儲存著真正的內容。

 

以上時兩種基本初始化方式。在初始化交錯陣列時，第一個索引運運算元表示長度，第二個索引運運算元表示維度，如一維[]，二維[,]等。

元素的存取與之前提到的方法類似，通過單個索引運運算元存取

 

第一個索引運運算元表示arr中的物件，第二個索引運運算元表示對應物件中的元素。

四．有關陣列的常用API（原始碼學習）

【注：本節提到的原始碼及內容均在.NET 5的基礎上論述】

 

（一）排序Array.Sort()

通過反編譯發現，該方法存在的16個過載最後都會呼叫Line 2125的方法。

【以下內容為原始碼分析】

• Line 2125：

　　　　（1）   Nullable<T> 表示可被分配為null的值型別，[Nullable(type)]表示被修飾的資料結構可以儲存type型別的元素，沒有值則儲存null；

　　　　（2）   keys 表示目標陣列，即待排序的陣列；

　　　　（3）   items 表示另一個陣列（預設為null），其內部的每一個元素與keys中每個關鍵字對應；常用於兩個陣列的關聯排序，預設將keys中的元素按索引順序和items中的元素一一對應，在排序時以keys中的元素為比較物件進行排序，在對keys中的元素進行位置移動時會連帶對應items中的元素一起移動，類似於鍵值對。

　　　　（4）   index：排序起始索引（預設為0）；

　　　　（5）   length：排序長度（預設為arr.Length）；

　　　　（6）   compare：比較器物件（預設為升序）。

• Line 2131：Array.Rank 該屬性獲取陣列的秩，即維度。

• Line 2135：Array.GetLowerBound(Int32) 該方法獲取陣列下限索引，其中的整數代表「行索引」。

• Line 2136：keys的起始索引必須和items的起始索引一致。

• Line 2148：

　　　　（1）   keys.Length - (index - lowerBound) < length 表示 從index開始的要排序的元素長度 小於 標稱長度length，即要排序的元素長度不夠；

　　　　（2）   items != null && index – lowerBound > items.Length – length 表示 index之前的不參與排序元素長度 已經超過 items的長度，使得keys中要排序的部分沒有可對應的items元素。

• Line 2158：預設比較器物件為升序

 

• Line 2160~2169：

　　　　（1）   as 關鍵字判斷並進行轉換。若無法轉換且不發生錯誤，則返回null；否則返回轉換後得到物件；

　　　　（2）   Line 2161：array != null 表示該陣列成功轉換為object型別；

　　　　（3）   Line 2164：表示items為空 或 items成功轉換；

　　【注：（4）（5）為本人結合資料推斷得出，有待證實】

　　　　（4）   as成功轉換的前提是，當需要轉化物件的型別屬於轉換目標型別 或者 屬於轉換目標型別的派生型別時，轉換操作才能成功，而且並不產生新的物件。而陣列型別在System.Array中，並不屬於System.Object，所以自帶的陣列型別無法利用as轉換為object型別。

因此，可推斷：所有基本資料型別均不能以上述方式成功轉換，因為基本資料型別屬於System.ValueType；而自定義的物件資料型別可以成功轉換，因為自定義型別屬於Sytem.Object。

　　　　（5）   如果全都轉換成功，則需要利用物件的排序方式進行排序，不能使用基本資料型別的方式進行排序。（體現在Line 2166與Line 2215）。

 

• Line 2172：CorElementType指定公共語言執行時Type、型別修飾符或有關後設資料型別簽名中的型別的資訊，即指明型別。（詳細內容見：CorElementType 列舉 - .NET Framework | Microsoft Docs）。keys.GetCorElementTypeOfElementType()表示返回keys對應的型別。

• Line 2173：要麼不進行關聯排序（items == null），要麼進行關聯排序（必須保證二者型別相同）。

• Line 2176~2211：根據不同型別選取 不同型別<T> 的方法。

之後將keys轉換為Span列表，Span型別可以表示任意記憶體的相鄰區域，以此達到部分排序的目的；Span中的Sort方法位於MemoryExtensions類中。

 

• Line 1506：當列表長度大於1時，呼叫ArraySortHelper<T>中Default物件的Sort方法。

 

• Line 10：ArraySortHelper<T>派生自介面IArraySortHelper<T>。

• Line 18：進入到Line 24。

• Line 27：建立ArraySortHelper物件；

　　　　（1）   內部的Default物件會根據是否實現了介面IComparable<T>來建立不同的 ArraySortHelper；

　　　　（2）   Type.IsAssignbleFrom(Type c)方法判讀指定型別c的範例是否能分配給當前型別Type的變數；即判斷c是否為Type型別或其派生型別。

• Line 29：預設情況下，使用預設比較器物件（升序）滿足該行條件，使用GenericArraySortHelper中的Sort方法。

 

• Line 16、Line 35：無論是否滿足Line 17處的條件，最終都會首先進入IntroSort方法。

• Line 30：2 * (BitOperations.Log2((uint)keys.Length) + 1) 計算若使用堆排序後，可建成的堆的深度。

【至此，陣列開始正式進入排序階段】

 

• Line 129：注意到，當Length小於等於16時，選用InsertionSort插入排序；反之使用HeapSort堆排序。這是一種優化思想，根據大量實驗表明：資料量小於等於16時插排效率更高。

• Line 151：遞迴操作，每次 depthLimit 都會減1, 當深度為0排序還沒有完成的時候，就會直接使用堆排序(HeapSort)

（插排、堆排程式碼如下）：

 

其中的DownHeap是建立頂堆的過程，預設為小頂堆。

• Line 133：SwapIfGreater(T t, T t)該方法用於交換兩個元素，使其滿足升序。

• Line 157：注意到此處的快速排序，其內部使用了尾遞迴的快速排序以及三數取中法。

小結 一

1. .NET對陣列進行排序時，有較長的「前搖」，需要判斷、轉換等相關操作；

2. .NET中對陣列的排序方法不是單一的，而是綜合許多排序方法，在不同條件下選擇不同的方法，以達到最優的解法。

（二）克隆Array.Clone()

 

 

• Line 24：Object.MemberwiseClone方法，建立當前 Object 的淺表副本；

一個集合的淺度拷貝意味著只拷貝集合中的元素，不管他們是參照型別或者是值型別，不拷貝參照所指的物件。即，新集合中的參照和原始集合中的參照所指的物件是同一個物件。與此形成對比的是深度拷貝，不僅拷貝集合中的元素，而且還拷貝元素直接或者間接參照的所有東西。即，新集合中的參照和原始集合中的參照所指的物件是不同的。

 

【注：下方內容為本人結合資料推斷得出，有待證實】

• Line 26：以被克隆物件為基礎，分配一個新的未初始化的物件。

• Line 27：返回一個指向目標物件的指標（從該指標處開始寫入資料）。

• Line 28、29：分別獲取被克隆物件與目標物件的資料。

• Line 30：以指標形式存取ConatinsCGPointers

 

將傳入的物件的Flags屬性與2^24做且運算 和 (uint)0無符號整數0進行比較。之後按照不同的情況進行資料填充，完成後返回型別為object的物件。

（三）複製Array.Copy()

 

• Line 3：sourceArray源陣列（被複制的陣列），sourceIndex複製起點，destinationArray目標陣列，destinationIndex貼上起點，length複製長度。

• Line 7：獲取源陣列的資料型別。

• Line 8：進行相關判斷，是否滿足複製貼上條件；包括：源陣列型別與目標陣列型別應一致、源陣列不應為多維陣列、複製長度和複製起點大於等於0、複製起點索引值 + 複製長度小於等於目標陣列最大長度、貼上起點索引值 + 複製長度小於等於目標陣列最大長度。

接下來的過程與Clone方法基本一致。

• Line 23：注意到最後一個引數false，表示條件不滿足無法複製。

 

該部分主要功能是丟擲異常，因為在實際使用中，無法呼叫到包含bool reliable引數的這個方法。

 

（四）複製Array.CopyTo()

 

• Line 3：Array array為目標陣列。

可以發現，其原理和Copy方法、Clone方法基本一致。

小結 二

1. 三種方法均可以將一個陣列的內容，放到另一個陣列上。

2. Clone方法具有返回值，為Object型別，在克隆後直接賦值給目標陣列，因此不需要目標陣列範例化。

2. Copy與CopyTo方法沒有返回值，是通過直接在目標陣列上填充，以完成複製，因此目標陣列必須範例化且目標陣列必須和源陣列型別一致。

4. Copy為靜態方法，可通過Array類名直接呼叫；Clone與CopyTo方法為非靜態方法，故需要範例化的一個陣列來呼叫。

5. Clone方法使淺層拷貝，Copy與CopyTo是深層拷貝。

總結

1. 本文從原始碼的角度，對陣列、陣列遍歷以及常見方法進行了分析與論述。更多關於陣列的內容可參閱（.NET API 瀏覽器 | Microsoft Docs）。

2. 對於記憶體分配，陣列屬於參照型別，其值儲存在堆中，但參照的物件儲存在棧中（是一個記憶體地址），通過該參照物件找到並存取堆中的值。

3. 對於迭代器存取，所以可使用迭代器存取的資料型別均必須可以建立或返回一個IEnumerator<T>的物件，供迭代器使用。

4. 對於Array.Sort()方法，其內部不是單一的排序方式，而是在不同情況下使用不同的的排序方式，以達到最佳效率。

5. 對於三種複製方法，Clone為淺層拷貝，拷貝後，新陣列與源陣列參照地址相同；Copy與CopyTo為深層拷貝，拷貝後，新陣列與源陣列參照地址不同，是一個完全新的物件。

【感謝您可以抽出時間閱讀到這裡，因個人水平有限，可能存在錯誤，望各位大佬指正，留下寶貴意見，謝謝！】