IEnumerable<T>.ToArray()是如何工作的？

Question

这是一个双遍历算法吗？即，它首先迭代枚举一次以计算元素数量，以便可以分配数组，然后再次传递以插入元素吗？

它只循环一次，并不断地调整数组大小吗？

还是使用类似于List的中间结构（可能在内部调整数组大小）？

- mpen

---

我的建议是下载.NET Reflector并自己查看源代码。 - Justin Niessner

使用微软的框架参考源代码，可以查看其中的注释和更好的变量名称 :-) 这就是我用来研究答案的工具。 - driis

Answer 1

它使用中间结构。实际涉及的类型是一个Buffer，在框架内部是一个内部结构。在实践中，此类型具有一个数组，每次填满时都会复制该数组以分配更多空间。该数组从长度为4开始（在.NET 4中，这是可能会改变的实现细节），因此在执行ToArray时可能会反复进行大量的分配和复制。

但是此处已经进行了优化。如果源实现了ICollection<T>，则会利用该接口的Count属性从一开始就分配正确大小的数组。

- driis

---

supercat：请注意，该算法仍然使用O(n)的空间和时间。 - Gabe

为什么不使用不安全的堆栈分配来利用临时对象，这将显著提高性能？ - Andriy Shevchenko

@Backwards_Dave：每次缓冲区填满时，一半的项目将被写入一次（在上次填满后），另一半将从先前的缓冲区复制。那个先前缓冲区中的一半项目将被写入一次，另一半来自更早的缓冲区，以此类推。在缓冲区填满后，新缓冲区中一半的项目将被复制，并且其中一个项目将被写入一次。 - supercat

啊，我现在明白了，在更近期的dotnet实现中，它似乎做了一些类似于我想的东西（？），使用了这个LargeArrayBuilder<T>类。它有一个缓冲区数组（每个缓冲区的大小是前一个的2倍），并且将每个缓冲区中的内容复制到目标数组中。不确定那是哪个版本，但这个实现不是.NET Framework 4.8中使用的。 - geekley

@geekley: 迭代加倍大小是一个合理的方法，只要临时集合保持足够小以避免被放置在大对象堆中。否则，我认为节点链表可能是一个不错的方法，每个节点包含一个T[]和指向下一个节点的链接。我不知道.NET是否已经有一种好的方法来确定最大数组大小，以避免大对象堆分配。 - supercat

Answer 2

首先它会检查源是否是 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;
}

- Gabe

Answer 3

像这样（通过.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;
    }
}

- StriplingWarrior

Answer 4

首先，物品被加载到一个内部类Buffer<T>中，该类允许生成计数。

接下来，调用Buffer<T>.ToArray，它会将Buffer<T>的数组复制到返回的数组中。

.NET Reflector显示了这段代码，如果您想自己查看。

http://www.red-gate.com/products/reflector/

- Martin Peck

Answer 5

一般来说，尝试对可枚举对象进行两次迭代可能会导致灾难，因为无法保证可枚举对象可以第二次迭代。因此，执行 Count 然后分配并复制是不行的。

在 Reflector 中，它使用了一种称为 Buffer 的类型，该类型将序列有效地流式传输到数组中，并根据需要调整大小（每次重新分配时将其加倍，以便重新分配的次数为 O(log n)），然后在到达结尾时返回一个大小适当的数组。

- jason