这是一个双遍历算法吗?即,它首先迭代枚举一次以计算元素数量,以便可以分配数组,然后再次传递以插入元素吗?
它只循环一次,并不断地调整数组大小吗?
还是使用类似于List的中间结构(可能在内部调整数组大小)?
它使用中间结构。实际涉及的类型是一个Buffer,在框架内部是一个内部结构。在实践中,此类型具有一个数组,每次填满时都会复制该数组以分配更多空间。该数组从长度为4开始(在.NET 4中,这是可能会改变的实现细节),因此在执行ToArray时可能会反复进行大量的分配和复制。
但是此处已经进行了优化。如果源实现了ICollection<T>
,则会利用该接口的Count属性从一开始就分配正确大小的数组。
LargeArrayBuilder<T>
类。它有一个缓冲区数组(每个缓冲区的大小是前一个的2倍),并且将每个缓冲区中的内容复制到目标数组中。不确定那是哪个版本,但这个实现不是.NET Framework 4.8中使用的。 - geekley首先它会检查源是否是 ICollection<T>
,如果是,它会调用源的 ToArray()
方法。
否则,它只枚举源一次。在枚举过程中,它将项存储到一个缓冲数组中。每当它到达缓冲数组的末尾时,它就会创建一个两倍大小的新缓冲区并复制旧元素。一旦枚举完成,它会返回缓冲区(如果大小恰好正确)或将项从缓冲区复制到恰好正确大小的数组中。
以下是该操作的伪代码:
public static T[] ToArray<T>(this IEnumerable<T> source)
{
T[] items = null;
int count = 0;
foreach (T item in source)
{
if (items == null)
{
items = new T[4];
}
else if (items.Length == count)
{
T[] destinationArray = new T[count * 2];
Array.Copy(items, 0, destinationArray, 0, count);
items = destinationArray;
}
items[count] = item;
count++;
}
if (items.Length == count)
{
return items;
}
T[] destinationArray = new TElement[count];
Array.Copy(items, 0, destinationArray, 0, count);
return destinationArray;
}
像这样(通过.NET Reflector):
public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source)
{
if (source == null)
{
throw Error.ArgumentNull("source");
}
Buffer<TSource> buffer = new Buffer<TSource>(source);
return buffer.ToArray();
}
[StructLayout(LayoutKind.Sequential)]
internal struct Buffer<TElement>
{
internal TElement[] items;
internal int count;
internal Buffer(IEnumerable<TElement> source)
{
TElement[] array = null;
int length = 0;
ICollection<TElement> is2 = source as ICollection<TElement>;
if (is2 != null)
{
length = is2.Count;
if (length > 0)
{
array = new TElement[length];
is2.CopyTo(array, 0);
}
}
else
{
foreach (TElement local in source)
{
if (array == null)
{
array = new TElement[4];
}
else if (array.Length == length)
{
TElement[] destinationArray = new TElement[length * 2];
Array.Copy(array, 0, destinationArray, 0, length);
array = destinationArray;
}
array[length] = local;
length++;
}
}
this.items = array;
this.count = length;
}
internal TElement[] ToArray()
{
if (this.count == 0)
{
return new TElement[0];
}
if (this.items.Length == this.count)
{
return this.items;
}
TElement[] destinationArray = new TElement[this.count];
Array.Copy(this.items, 0, destinationArray, 0, this.count);
return destinationArray;
}
}
首先,物品被加载到一个内部类Buffer<T>
中,该类允许生成计数。
接下来,调用Buffer<T>.ToArray
,它会将Buffer<T>
的数组复制到返回的数组中。
.NET Reflector显示了这段代码,如果您想自己查看。
Count
然后分配并复制是不行的。Buffer
的类型,该类型将序列有效地流式传输到数组中,并根据需要调整大小(每次重新分配时将其加倍,以便重新分配的次数为 O(log n)
),然后在到达结尾时返回一个大小适当的数组。