C#:List源码，使用注意，优化

2022-10-19 17:53:00

List内部是用数组实现的，而不是链表，并且当没有给予指定容量时，初始的容量为0

Add

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

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

每次容量不够的时候，整个数组的容量都会扩充一倍，_defaultCapacity 是容量的默认值为4。因此整个扩充的路线为4，8，16，32，64，128，256，512，1024…依次类推。所以创建时预定好容量，写入 2的幂

Remove

// Removes the element at the given index. The size of the list is
// decreased by one.
// 
public void RemoveAt(int index) {
    if ((uint)index >= (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    Contract.EndContractBlock();
    _size--;
    if (index < _size) {
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    _items[_size] = default(T);
    _version++;
}

从源码中我们可以看到，元素删除的原理其实就是用 Array.Copy 对数组进行覆盖。IndexOf 启用的是 Array.IndexOf 接口来查找元素的索引位置，这个接口本身内部实现是就是按索引顺序从0到n对每个位置的比较，复杂度为O(n)

Insert

// Inserts an element into this list at a given index. The size of the list
// is increased by one. If required, the capacity of the list is doubled
// before inserting the new element.
// 
public void Insert(int index, T item) {
    // Note that insertions at the end are legal.
    if ((uint) index > (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
    }
    Contract.EndContractBlock();
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    if (index < _size) {
        Array.Copy(_items, index, _items, index + 1, _size - index);
    }
    _items[index] = item;
    _size++;            
    _version++;
}

与Add接口一样，先检查容量是否足够，不足则扩容。从源码中获悉，Insert插入元素时，使用的用拷贝数组的形式，将数组里的指定元素后面的元素向后移动一个位置。

Clear

Array.Clear(_items, 0, _size);

数组清0，不然list内元素的引用不会-1，导致元素不会被GC

Sort

快速排序

ToArray

ToArray接口中，重新new了一个指定大小的数组，再将本身数组上的内容考别到新数组上，再返回出来。少用。

优化

删除优化

如果对顺序无要求，把要删除的元素与最后一个元素换位置，再删除最后一个元素
Array.Copy(_items, index + 1, _items, index, _size - index);
这样可以使删除时赋值最少。对于item是引用类型要通过深拷贝进行交换
https://blog.csdn.net/weixin_36464906/article/details/115670601?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2_{aggregatepage}first_rank_ecpm_v1~rank_v31_ecpm-1-115670601.pc_agg_new_rank&utm_term=c%23+list+%E6%93%8D%E4%BD%9C%E4%BC%98%E5%8C%96&spm=1000.2123.3001.4430
但是在根据ListA批量ListB中元素删除时

创建时确定具体容量

分别设置4，8，16，32，64，128，256，512，1024…依次类推

Contains优化

List每次Contains遍历全部元素，使用Dictionary替代，Dictionary.ContainsKey(key)，List.AddRange(Dictionary.Values)将值加到List里

List源码及调试用代码

https://github.com/luoyikun/UnityForTest
ListScene场景

ListOri.List<int> list = new ListOri.List<int>(64);//这里list.Count = 0，只是把内部数组预先分配了空间

        for (int i = 0; i < 64; i++)
        {
            list.Add(i);
        }
        if (list.Contains(32))
        {
            Debug.Log("Find");
        }

码农公寓

Add