37

我一直在查看使用 ILSpy 的 .NET 库，并且在命名空间中遇到了List<T>类定义System.Collections.Generic。我看到该类使用这样的方法：

// System.Collections.Generic.List<T>
/// <summary>Removes all elements from the <see cref="T:System.Collections.Generic.List`1" />.</summary>
public void Clear()
{
    if (this._size > 0)
    {
        Array.Clear(this._items, 0, this._size);
        this._size = 0;
    }
    this._version++;
}

所以，类的Clear()方法List<T>实际上是使用Array.Clear方法。我见过许多其他List<T>在体内使用 Array 的方法。

这是否意味着List<T>实际上是一个卧底 Array 或 List 只使用了 Array 方法的一部分？

我知道列表是类型安全的，不需要装箱/拆箱，但这让我有点困惑。

4

4 回答 4

46

列表类本身并不是一个数组。换句话说，它不是从数组派生的。相反，它封装了一个数组，实现使用该数组来保存列表的成员元素。

由于List<T>提供对其元素的随机访问，并且这些元素被索引0..Count-1，使用数组来存储元素是显而易见的实现。

于 2013-05-05T17:47:31.377 回答
32

这往往会让了解 std::list 的 C++ 程序员感到惊讶。一个链表，包含在 .NET 以及 LinkedList 类中。并且具有相同的性能特征，插入和删除 O(1)。

但是，您通常应该避免它。链表在现代处理器上表现不佳。这在很大程度上取决于 cpu 缓存来获得合理的性能，内存比执行核心慢很多倍。到目前为止，一个简单的数组是最能利用缓存的数据结构。访问一个元素使得后续元素也出现在缓存中的几率非常高。链表的情况并非如此，元素往往分散在整个地址空间中，可能会导致缓存未命中。它们可能非常昂贵，多达 200 个周期，而 cpu 什么都不做，只是等待内存子系统提供数据。

但是请记住性能特征，添加或删除不在列表末尾的元素会花费 O(n)，就像数组一样。而且一个大的 List 会在数组需要扩展时产生大量垃圾，预先设置 Capacity 属性可以帮助避免这种情况。有关此答案的更多信息。否则与 std::vector<> 完全相同的问题。

于 2013-05-05T18:35:37.330 回答
24

是的，List<T>在内部使用一个数组来存储项目，尽管在大多数情况下，该数组实际上大于集合中元素的数量——它在末尾有一些额外的“填充”，这样你就可以在没有它的情况下添加新项目每次重新分配内存。它使用单独的字段跟踪集合的实际大小（您可以this._size在生成的代码中看到）。当您添加的元素超出当前数组的空间时，它会自动分配一个新的更大的数组——我认为是两倍大——并复制所有现有元素。

如果您担心List<T>使用过多的内存，您可以使用接受参数的构造函数覆盖capacity显式设置数组的大小，如果您事先知道大小，或者调用该TrimExcess()方法以确保数组是 (接近）集合的实际大小。

于 2013-05-05T18:02:37.463 回答
0

随机存取内存是一个数组，因此从这个意义上说，从链表到堆等所有数据结构，依赖于随机存取内存来实现其性能行为，都建立在系统内存数组上。更多的是介于两者之间的抽象层次的问题。

当然，在现代虚拟内存机器中，随机存取系统内存本身就是建立在多层流水线缓存、非缓存 RAM 和磁盘的复杂虚拟内存模型之上的抽象。

于 2013-05-05T18:34:55.273 回答