How does IEnumerable<T>.ToArray() work?

Question

Is it a two-pass algorithm? i.e., it iterates the enumerable once to count the number of elements so that it can allocate the array, and then pass again to insert them?

Does it loop once, and keep resizing the array?

Or does it use an intermediate structure like a List (which probably internally resizes an array)?

Answer 1

It uses an intermediate structure. The actual type involved is a Buffer, which is an internal struct in the framework. In practice, this type has an array, that is copied each time it is full to allocate more space. This array starts with length of 4 (in .NET 4, it's an implementation detail that might change), so you might end up allocating and copying a lot when doing ToArray.

There is an optimization in place, though. If the source implementes ICollection<T>, it uses Count from that to allocate the correct size of array from the start.

Answer 2

First it checks to see if the source is an ICollection<T>, in which case it can call the source's ToArray() method.

Otherwise, it enumerates the source exactly once. As it enumerates it stores items into a buffer array. Whenever it hits the end of the buffer array it creates a new buffer of twice the size and copies in the old elements. Once the enumeration is finished it returns the buffer (if it's the exact right size) or copies the items from the buffer into an array of the exact right size.

Here's pseudo-source code for the operation:

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; }