CODEWITHSUNDEEP
c#
Sergey Slepov
Sergey Slepov

Reputation: 2141

ToList with Capacity?

When we do .ToList() for an IEnumerable, the list can potentially reallocate while scanning the IEnumerable because it doesn't know the size upfront. If the size is known, is there a simple way to avoid the performance penalty? Something to the effect of initializing a List with the required capacity and then copying the IEnumerable into it? Ideally something as simple as .ToList(capacity) (which doesn't exist).

Upvotes: 8

Views: 1594

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727107

In cases when the capacity is part of IEnumerable<T> that is also an ICollection<T>, the library will allocate at the correct capacity.

Here is a reference implementation of List<T>(IEnumerable<T> source), which is invoked when you call ToList():

public List(IEnumerable<T> collection) {
    if (collection==null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    Contract.EndContractBlock();

    ICollection<T> c = collection as ICollection<T>;
    if( c != null) {
        int count = c.Count;
        if (count == 0) {
            _items = _emptyArray;
        } else {
            _items = new T[count];
            c.CopyTo(_items, 0);
            _size = count;
        }
    } else {                
        _size = 0;
        _items = _emptyArray;
        // This enumerable could be empty.  Let Add allocate a new array, if needed.
        // Note it will also go to _defaultCapacity first, not 1, then 2, etc.

        using(IEnumerator<T> en = collection.GetEnumerator()) {
            while(en.MoveNext()) {
                Add(en.Current);                                    
            }
        }
    }
}

Note how the constructor behaves when collection implements ICollection<T>: rather than iterating the content and calling Add for each item, it allocates the internal _items array, and copies the content into it without reallocations.

In situations when the capacity is not embedded in class implementing IEnumerable<T>, you can easily define one yourself, using a combination of standard methods:

public static class ToListExtension {

    public static List<T> ToList<T>(this IEnumerable<T> source, int capacity) 
    {
        var res = new List<T>(capacity);
        res.AddRange(source);
        return res;
    }

}

Upvotes: 14

Related Questions