[数据结构-线性表1.1] 数组（.NET源码学习）

#Updated【2022.7.29 替换文中不清晰的代码图片】

数组，一种数据类型（在绝大数语言中不是基本数据类型）且为引用类型，在内存中以连续的内存单元进行分配，所以其大小在创建对象后为定值，不可更改。

一．内存分配

对于两种不同数据类型而言，其内存分配方式是不同的。值类型直接在栈（C#中称为堆栈Stack）上分配，将其储存的内容直接存放到栈中；引用类型则是将指向实例对象的地址存在栈中，对该地址进行解析后获得一个在堆（此处，C#中称为托管堆）中的位置，这个位置储存着真正的内容。

对于int类型，其大小为32位，即4个字节，所以整型数组中的每个元素占4个字节。但整个数组在内存中所占字节大小并不是“Length * 4”，因为在位数组分配的内存开头会被同步索引块、类型对象指针和数组长度所占据。

一般地：对于32位程序，上述三者分别占用4个字节；64位程序则分别占用8个字节。

在内存分配表中可以看到：（32位程序）

第一行表示同步索引块；第二行表示类型对象指针；第三行表示当前数组所分配的长度；第四行目前本人不知道其具体含义，欢迎大佬留言；之后便是存储的每个元素，每个元素占4个字节。

【注：上述详细内容请查找CLR相关资料】

据此，可以推断出：我们显示看到的长度指的是可储存元素的数量，而数组的整体大小则需要额外加上16字节（32位）/ 32字节（64位）。

二．访问与迭代

（一）数组的访问与遍历

对于数组的访问，一般采用索引的方式访问每一个元素。本人看来，索引读取的内容是内存地址。数组之所以可以用索引来访问，是因为其在内存中是连续的，就像C/C++中用指针访问数组，指针加一即表示下一个元素。此外，由于数组满足通过索引访问，索引由整形数字表示，所以理论上，数组最大长度为整型最大值（int.MaxValue = 2^31 – 1 = 2147483647），但由于实际内存的原因，一般地，一维最好不要超过10^7，二维最好不要超过10^5 * 10^5。

（二）长度索引模式与迭代器模式

长度索引模式要求被访问对象具有可确定的长度且支持索引运算符[]，如数组和集合（List等）；而某些数据结构在运行时长度未知，某些不支持索引访问，如Stack<T>、Queue<T> 和 Dictionary<TKey and TValue>等。

对于迭代器模式，其实现方式基于IEnumerator<T>接口，也就是说能够使用foreach进行访问的对象/类型，必须可以创建/返回该接口的对象。

【注：C#不要求必须实现IEnumerable/IEnumerable<T>才能使用foreach迭代数据类型，只要求包含GetEnumerator（可返回类型为IEnumerator<T>的对象）的公共定义即可】

IEnumerator<T>接口对应的类型是一个集合访问器，即可迭代对象，其内部包含一个属性Current，用于返回当前处理的元素；两个方法（bool）MoveNext，从一个元素移到下一个元素，同时检测是否已枚举完所有项；Reset，通常会抛出 NotImplementedException，是在无法实现请求的方法或操作时引发的异常。

就数组而言对于上述两种模式的效率差异不是很大。平均地，除第一次外，索引访问要快于迭代器访问。

（三）IEnumerable<T>与IEnumerator<T>

对于IEnumerator<T>而言，在多重循环、多线程以及共享状态下，如果两个foreach彼此交错且访问的是同一个集合，那就会出现一个枚举器被多条语句使用的情况。集合必须始终有当前元素的状态指示符，以便在调用MoveNext时，可以确定下一个元素。在这种情况下，交错的一个循环可能会影响另一个循环。

所以，集合类不直接支持IEnumerator<T>和IEnumerator接口。而是直接支持另一种接口IEnumerable<T>。该接口的作用是返回一个类型为IEnumerator<T>的对象。这样不同的迭代语句有着自己的迭代器，不会相互争抢。

三．C#中的数组

（一）维度数组

当然，官方应该没有这样的称法，只是称一维、二维数组等。

对于一维数组，其在内存中就是简单的以连续的方式进行存储。理论上，其最大长度为2147483647，但实测后其最大长度为2147483591（实测平台：.NET 6 32位控制台程序）。

对于二维或更高维的数组，其在内存中的存储方式并不是我们所想象的一个矩阵或一个立方，内存只由一个个独立的存储单元组成，并不能表示出具有相关性的几何区域。

在内存分配表中可以看到：（32位程序）

一维数组占用前16字节，存储数组本体信息；而二维数组占用32字节存储本体信息。之后的数据存储方式与一维数组一致，每个元素占4个字节。由此可以推断出多维数组的存储方式依旧是按连续内存的方式进行存储。

#一维数组和多维数组的下标转换#

（1）多维 => 一维（扁平化处理）

int[,,,,…,] arr = new int[a, b, c, d,…,k];

arr[x, y, z, w,…,n] => idx = x * (b * c * d * …) + y * (c * d * …) + z * (d * …) + … + n

（2）一维 => 多维（以二维为例）

int[,] arr = new int[a, b];

p[x] = arr[u, v] 其中u = x / b v = x % b

（二）交错数组

以数组为元素的数组，叫做交错数组，即该数组内部元素为数组，每个数组的大小可以不同。

以上时两种基本初始化方式。在初始化交错数组时，第一个索引运算符表示长度，第二个索引运算符表示维度，如一维[]，二维[,]等。

元素的访问与之前提到的方法类似，通过单个索引运算符访问

第一个索引运算符表示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为深层拷贝，拷贝后，新数组与源数组引用地址不同，是一个完全新的对象。

【感谢您可以抽出时间阅读到这里，因个人水平有限，可能存在错误，望各位大佬指正，留下宝贵意见，谢谢！】

[数据结构-线性表1.1] 数组（.NET源码学习） - PaperHammer

[数据结构-线性表1.1] 数组（.NET源码学习）

一．内存分配