.net源码解读之List＜T＞

本文链接： https://blog.csdn.net/lishuangquan1987/article/details/122869962

我们知道，List与数组的区别是，可以Add元素，但是这是如何实现的呢？

翻看源码，解开面纱，发现List的内部实现，就是使用数组实现的。

List的源码地址：https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,cf7f4095e4de7646

部分源码片段解答：

public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
 {
     private const int _defaultCapacity = 4;

     private T[] _items;
     [ContractPublicPropertyName("Count")]
     private int _size;
     private int _version;
     [NonSerialized]
     private Object _syncRoot;

     static readonly T[]  _emptyArray = new T[0];
 }

其中， _items 变量中便是存储的List中的元素

_size 就是List中的元素个数

无参构造函数

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,52

// Constructs a List. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to 16, and then increased in multiples of two as required.
public List() {
    _items = _emptyArray;
}

这时候， _items 变量为长度为0的数组

有参构造函数(传入容量)

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,60

// Constructs a List with a given initial capacity. The list is
// initially empty, but will have room for the given number of elements
// before any reallocations are required.
//
public List(int capacity) {
    if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
    Contract.EndContractBlock();

    if (capacity == 0)
        _items = _emptyArray;
    else
        _items = new T[capacity];
}

如果传入的容量是0，则 _items 为长度为0的数组，否则，为 capacity 大小的数组（无任何元素）

有参构造函数（传入一个集合）

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,74

// Constructs a List, copying the contents of the given collection. The
// size and capacity of the new list will both be equal to the size of the
// given collection.
//
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);
            }
        }
    }
}

如果传入的集合为空，则抛出异常

如果传入的集合长度为0，则 _items 为长度为0的数组

如果集合有内容，则把集合的内容添加到 _items 中，这时，_size=items.Lenth

Add方法

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,220

// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
//
public void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

从注释可以看到：

• 如果需要， _items 的容量会增大一倍
• 每次添加一个元素， _size 会+1

其中 _items 的容量增大一倍，在 EnsureCapacity 函数中实现：

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,405

// Ensures that the capacity of this list is at least the given minimum
// value. If the currect capacity of the list is less than min, the
// capacity is increased to twice the current capacity or to min,
// whichever is larger.
private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
        // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
        // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

可以看到

• 若 _items 的长度为0，则扩容时，长度为 _defaultCapacity 也就是4
• 若 _items 的长度不为0，则扩容时，长度为 _items.Lenth*2
• 最后赋值 Capacity = newCapacity，跳转到Capacity的set中：

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,110

// Gets and sets the capacity of this list.  The capacity is the size of
// the internal array used to hold items.  When set, the internal
// array of the list is reallocated to the given capacity.
//
public int Capacity {
    get {
        Contract.Ensures(Contract.Result<int>() >= 0);
        return _items.Length;
    }
    set {
        if (value < _size) {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }
        Contract.EndContractBlock();

        if (value != _items.Length) {
            if (value > 0) {
                T[] newItems = new T[value];
                if (_size > 0) {
                    Array.Copy(_items, 0, newItems, 0, _size);
                }
                _items = newItems;
            }
            else {
                _items = _emptyArray;
            }
        }
    }
}

扩容时，New了一个新的数组，长度为Capacity,将 _items 之前的元素（如果有）复制到新的数组。然后将新的数组赋值到 _items