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

Question

来自LukeH's answer to what is the max limit of data into list<string> in c#?

The maximum number of elements that can be stored in the current implementation of List is, theoretically, Int32.MaxValue - just over 2 billion.

我们看到一个 List 可以承载大量的项目。我假设编译器不会为 List<T> 的每个新实现释放 space 20 亿倍大小的 T，那么列表如何动态增长？它是否有指向内存中不连续 space 的指针？

Answer 1

你的假设是正确的，编译器没有分配任何东西。 List<T> class 内部使用一个数组来存储元素，它会在每次调用 Add 时检查数组的大小是否足够，如您所见 in the source code :

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

Answer 2

List<T> class is implemented to use an internal T[] array under the hood. If you initialize it using the List<T>(int)构造函数，它将分配一个指定大小的数组。如果您使用默认构造函数，它将使用默认容量 4，但在这种情况下，数组只会在第一次添加时分配。

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

在性能方面，这意味着添加一个元素是 O(1) 或 O(n) 操作，具体取决于是否需要增加容量（如 Add 下所述） ).但是，由于容量在需要增加时加倍，因此随着列表变大，这种重新分配的频率呈指数下降。例如，从 4 开始，容量增加将发生在 4、8、16、32、64、128 ……元素处。因此，当调用 Add n 次时，重新分配的总成本大约为 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

░ 符号表示分配的 space 仍未使用。这些数组位置将包含 default value for T。在 char 的情况下，这将是空字符 [=22=]。但是，消费者永远不会看到这些值。

通过AddRange将多个元素相加时，最多只进行一次重新分配。如果将以前的容量加倍不足以容纳所有新元素，则内部数组会立即增加到新的计数。

与添加不同，删除元素不会自动缩小列表。但是，您可以通过调用 TrimExcess.

手动触发此操作

如 .NET Framework 4.7.2 的 , some aspects of the above (such as the default initial capacity of 4) are implementation details derived from the source code 中所述。但是，核心原则根深蒂固，不太可能在 other/future 框架中改变。

Answer 3

源代码将是明确的，如中，关于具体如何实现，但文档也涵盖了这一点。

Remarks section of the List<> class 状态：

The List class is the generic equivalent of the ArrayList class. It implements the IList generic interface by using an array whose size is dynamically increased as required.

Remarks section of the Capacity property阐述：

Capacity is the number of elements that the List can store before resizing is required, whereas Count is the number of elements that are actually in the List.

Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array before copying the old elements and adding the new elements.

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

How does C# dynamically allocate memory for a List<T>?

.net

c#

memory

list

dynamic-memory-allocation