Unity的List底层源码剖析
- Unity
- 2024-05-29
- 897热度
- 0评论
我们在Unity经常会使用List类型，但是却没有好好了解过List类型，它其实是使用了一个连续的内存块来存储元素，它的结构有点类似链表，但又与链表有着许多不同的地方.让我们来了解一下List的底层实现.
C#的List源码: C#源码
一、构造函数
List是C#中一个常见的可伸缩的数组组件，通常用来代替数组，其底层的数据结构就是基于数组（非链表）.由于它是可伸缩的，所有我们在编写程序的时候不需要手动的去分配数组的大小，甚至将它当作一个链表去使用.
当我们创建一个List实例时，如果没有指定容量和集合的话，那么初始容量为0，List内部的数组大小为0
public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
{
private const int _defaultCapacity = 4;
private T[] _items; // 主要数组
private int _size; // 数组大小(非容量)
private int _version; // List的版本（List内部维持）
static readonly T[] _emptyArray = new T[0]; // 默认空数组
// 构造函数: 默认为空数组，容量为0
public List()
{
_items = _emptyArray;
}
// 构造函数：声明初始容量
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];
}
// 构造函数：声明集合的内容，列表的大小和容量都等于给定的集合
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;
using (IEnumerator<T> en = collection.GetEnumerator())
{
while (en.MoveNext())
{
Add(en.Current);
}
}
}
}
}二、List的Capacity
Capacity即list的容量，当List的容量不足时，就会整个数组的容量都动态地扩容一倍。
public int Capacity
{
get => this._items.Length;
set
{
if (value < this._size)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
if (value == this._items.Length)
return;
if (value > 0)
{
T[] destinationArray = new T[value];
if (this._size > 0)
// 将原数组的数据拷贝到新数组中
Array.Copy((Array)this._items, (Array)destinationArray, this._size);
this._items = destinationArray;
}
else
this._items = List<T>._emptyArray;
}
}三、Add接口剖析
List每次添加一个元素时,都会判断数组的容量够不够，如果不够将调用Grow函数来增加容量.
其中Grow 函数有这么一行代码
int num = this._items.Length = 0 ? _defaultCapacity : 2 * this._items.Length;
每次容量不够时，整个数组的容量都会扩增一倍, _defaultCapacity表示容量的默认值为4，因此扩充的路线为4, 8, 16, 32, 64, 128, 256, 512 ...以此类推。
注意: List频繁的使用Add时，数组会不断被扩容，如果使用不当，会浪费大量内存空间，也会造成GC的不小负担。
public void Add(T item)
{
++this._version;
T[] items = this._items;
int size = this._size;
if ((uint)size < (uint)items.Length)
{
this._size = size + 1;
items[size] = item;
}
else
this.AddWithResize(item);
}
private void AddWithResize(T item)
{
int size = this._size;
this.Grow(size + 1);
this._size = size + 1;
this._items[size] = item;
}
internal void Grow(int capacity)
{
int num = this._items.Length == 0 ? _defaultCapacity : 2 * this._items.Length;
if ((uint)num > 2147483591U)
num = 2147483591;
if (num < capacity)
num = capacity;
this.Capacity = num;
}四、Remove接口剖析
Remove()函数中包括IndexOf()和RemoveAt()函数, 其中使用IndexOf()是利用Array.IndexOf接口来查找元素的索引位置，使用RemoveAt是利用ArrayCopy接口将指定位置的后面元素进行覆盖，从而来删除指定位置的元素。
public bool Remove(T item)
{
int index = this.IndexOf(item);
if (index < 0)
return false;
this.RemoveAt(index);
return true;
}
public int IndexOf(T item)
{
return Array.IndexOf<T>(this._items, item, 0, this._size);
}
public void RemoveAt(int index)
{
if ((uint)index > (uint) this._size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
--this._size;
if (index < this._size)
Array.Copy((Array)this._items, index + 1, (Array)this._items, index, this._size - index);
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
this._items[this._size] = default (T);
++this._version;
}五、Insert接口剖析
与Add接口一样，先检查数组容量是否足够，不足则扩容两倍。Insert()插入元素时，采用的与Remove类似，是复制数组的形式，将数组里指定元素后面的所有元素向后移动一个位置。
public void Insert(int index, T item)
{
if ((uint)index > (uint) this._size)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
if (this._size == this._items.Length)
this.Grow(this._size + 1);
if (index < this._size)
Array.Copy((Array)this._items, index, (Array)this._items, index + 1, this._size - index);
this._items[index] = item;
++this._size;
++this._version;
}六、其他接口剖析
6.1 []接口
[]接口是直接使用数组的索引方式获取元素。
public T this[int index]
{
get
{
if ((uint) index> (uint) _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
return _items[index];
}
set
{
if ((uint) index > (uint) _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
_items[index] = value;
_version++;
}
}6.2 Clear接口
采用了Array.Clear()清除对象引用的标记，便于垃圾回收。
public void Clear()
{
++this._version;
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
int size = this._size;
this._size = 0;
if (size < 0)
return;
Array.Clear(this._items, 0, _size);
}
else
this._size = 0;
}6.3 Contains接口
直接使用Array.IndexOf查找元素是否存在。
public bool Contains(T item) => this._size != 0 && this.IndexOf(item) > 0;6.4 ToArray接口
ToArray接口是重新创建了一个大小一直的数组，然后将原有数组上的内容复制到新数组中，在将新数组返回。
注意:如果使用过多，就会造成大量内存的分配，会使内存上留上很多无用的垃圾。
public T[] ToArray()
{
if (this._size == 0)
return List<T>._emptyArray;
T[] destinationArray = new T[this._size];
Array.Copy((Array) this._items, (Array)destinationArray, this._size);
return destinationArray;
}6.5 Find接口
查找接口，线性查找，对每个元素进行比较，时间复制度为O(n)
public T? Find(Predicate<T> match)
{
if (match == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
for (int index = 0; index < this._size; index++)
{
if (match(this._items[index]))
return this._items[index];
}
return default(T);
}6.6 Enumerator接口
Enumerator接口是枚举迭代部分细节的接口，注意：每次获得迭代器时，Enumerator都会被创建出来，如果大量使用迭代器，则会产生大量的垃圾,所有我们在开发时尽量不要使用foreach。
public List<T>.Enumerator GetEnumerator() => new Enumerator(this);
public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
{
private readonly List<T> _list;
private int _index;
private readonly int _version;
private T _current;
internal Enumerator(List<T> list)
{
this._list = list;
this._index = 0;
this._version = list._version;
this._current = default(T);
}
public void Dispose()
{
}
public bool MoveNext()
{
List<T> list = this._list;
// _version判断是否对list有修改
if (this._version != list._version || (uint)this._index >= (uint)list._size)
{
return this.MoveNextRare();
}
this._current = list._items[this._index];
this._index++;
return true;
}
private bool MoveNextRare()
{
// _version版本不一致，则抛出异常
if (this._version != this._list._version)
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
this._index = this._list._size + 1;
this._current = default(T);
return false;
}
public T Current => this._current;
object? IEnumerator.Cureent
{
get
{
if (this._index == 0 || this._index == this._list._size + 1)
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
return (object)this.Current;
}
}
void IEnumerator.Reset()
{
if (this._version != this._list._version)
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
this._index = 0;
this._current = default(T);
}
}
// foreach 实现原理
var _enumerator = list.GetEnumerator();
while (_enumerator.MoveNext())
{
}6.7 Sort接口
Sort接口是排序接口，它使用了Array.Sort接口进行排序。
public void Sort(int index, int count, IComparable<T> comparer)
{
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (count < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (this._size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (count > 1)
Array.Sort<T>(this._items, index, count, comparer);
++this._version;
}七、总结
部分源码看出来，List的效率并不高，只是通用性强，List的内存分配方式也极为不合理，当List里的元素不断增加时，会多次重新分配数组，导致原有的数组被抛弃，最后GC被调用时就会造成回收的压力。如果我们在使用List列表时提前声明列表大小时，增加元素时就不会重新生成数组了。
List并不是高效的组件，只是通用性比较强，真实情况下，它比数组的效率还要差，它只是一个兼容性比较强的组件，好用但是效率并不高。