Net Core教程

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

本文主要是介绍C#:List源码,使用注意,优化,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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-2aggregatepagefirst_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");
        }


这篇关于C#:List源码,使用注意,优化的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!