C#如何为List <T>动态分配内存？

Question

从LukeH的答案到c#中列表<string>的最大数据限制是什么？

可以存储在List的当前实现中的最大元素数量理论上是Int32.MaxValue - 仅超过20亿.

我们看到一个List可以携带大量的物品.我假设编译器不仅T为每个新实现释放20亿倍大小的空间List<T>,那么列表如何动态增长？它是否有指向内存中不连续空格的指针？

Answer 1

所述List<T>类被实现为使用一个内部T[]阵列罩下.如果使用List<T>(int)构造函数初始化它,它将分配指定大小的数组.如果使用默认构造函数,则默认容量为4,但在这种情况下,数组只会在第一次添加时分配.

每次向列表中添加元素时,它将首先检查是否已达到容量(即现有是否Count等于Capacity).如果是这样,它将创建一个大小比前一个大两倍的新数组,将所有现有元素复制到其中,然后继续编写新元素.这将在后续元素添加中无限期地发生,直到Int32.MaxValue达到您引用的硬限制().

在性能方面,这意味着添加元素是O(1)或O(n)操作,具体取决于是否需要增加容量(如下所述Add).但是,由于容量在需要增加时会加倍,因此随着列表变大,这种重新分配会以指数级递减的频率发生.例如,从4开始,容量增加将发生在4,8,16,32,64,128 ......元素处.因此,当调用Addn次时重新分配的总成本将大致为4 + 8 + 16 + ... + n/8 + n/4 + n/2,其仍然对应于O(n).

这是一个示例,显示了内部数组沿着一系列加法运算的状态:

                               //   ??
var list = new List<char>();   //   ??   Count:    0
                               //   ??   Capacity: 0
                               //   ?????????????????
list.Add('h');                 //   ? h ? ? ? ? ? ? ?   Count:    1
                               //   ?????????????????   Capacity: 4
                               //   ?????????????????
list.Add('e');                 //   ? h ? e ? ? ? ? ?   Count:    2
                               //   ?????????????????   Capacity: 4
                               //   ?????????????????
list.Add('l');                 //   ? h ? e ? l ? ? ?   Count:    3
                               //   ?????????????????   Capacity: 4
                               //   ?????????????????
list.Add('l');                 //   ? h ? e ? l ? l ?   Count:    4
                               //   ?????????????????   Capacity: 4
                               //   ?????????????????????????????????
list.Add('o');                 //   ? h ? e ? l ? l ? o ? ? ? ? ? ? ?   Count:    5
                               //   ?????????????????????????????????   Capacity: 8
                               //   ?????????????????????????????????
list.Add(' ');                 //   ? h ? e ? l ? l ? o ?   ? ? ? ? ?   Count:    6
                               //   ?????????????????????????????????   Capacity: 8
                               //   ?????????????????????????????????
list.Add('w');                 //   ? h ? e ? l ? l ? o ?   ? w ? ? ?   Count:    7
                               //   ?????????????????????????????????   Capacity: 8
                               //   ?????????????????????????????????
list.Add('o');                 //   ? h ? e ? l ? l ? o ?   ? w ? o ?   Count:    8
                               //   ?????????????????????????????????   Capacity: 8
                               //   ?????????????????????????????????????????????????????????????????
list.Add('r');                 //   ? h ? e ? l ? l ? o ?   ? w ? o ? r ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?   Count:    9
                               //   ?????????????????????????????????????????????????????????????????   Capacity: 16
                               //   ?????????????????????????????????????????????????????????????????
list.Add('l');                 //   ? h ? e ? l ? l ? o ?   ? w ? o ? r ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?   Count:    10
                               //   ?????????????????????????????????????????????????????????????????   Capacity: 16
                               //   ?????????????????????????????????????????????????????????????????
list.Add('d');                 //   ? h ? e ? l ? l ? o ?   ? w ? o ? r ? l ? d ? ? ? ? ? ? ? ? ? ? ?   Count:    11
                               //   ?????????????????????????????????????????????????????????????????   Capacity: 16

该?符号代表分配的空间仍然未使用.这些阵列的位置将包含默认值的T.在这种情况下char,这将是空字符,\0.但是,这些值永远不会被消费者看到.

通过一起添加多个元素时AddRange,最多只执行一次重新分配.如果将先前容量加倍不足以容纳所有新元素,则内部数组会立即增加到新计数.

与添加不同,删除元素不会自动缩小列表.但是,您可以通过调用手动执行此操作TrimExcess.

正如评论中所提到的,上面的某些方面(例如默认初始容量为4)是从.NET Framework 4.7.2 的源代码派生的实现细节.但是,核心原则是根深蒂固的,不太可能在其他/未来的框架中发生变化.

Answer 2

您的假设是正确的，编译器不会分配任何东西。所述List<T>类内部使用一个数组来存储中的元素，并且检查是否数组的大小是足够在每次调用Add，你可以看到在源代码：

public void Add(T item) {
    if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
    _version++;
}

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