使用AddRange()时,List <T>的内部数组是如何增加的

Question

我正在循环一个潜在的巨大(数百万项)数据集(存储在磁盘上)并拉出我要添加到的所选项目List<T>.当我将一个项目添加到列表中时,我会锁定它,因为有其他线程访问列表.

我试图在两种可能的实现之间做出决定:

1)每次我需要添加项目时锁定列表.

2)使用我在找到项目时添加项目的临时列表,然后用于List<T>.AddRange()将该列表中的项目添加到块中(例如,当我找到1000个匹配项时).这导致需要不经常请求锁定列表,但是如果AddRange()仅增加容量以足以容纳新项目,那么列表将最终重新调整大小很多次.

我的问题是:据我了解,每次添加一个项目将导致List<T>每次达到容量时a的内部容量增加一倍,但我不知道List<T>.AddRange()行为如何.我认为它只增加了容纳新物品的容量,但我找不到任何方法来证实这一点.关于如何在MSDN上增加容量的描述对于Add()和AddRange()几乎是相同的,除了对于AddRange它说如果新计数大于容量,则容量增加而不是如果Count已经是与容量相同.
对我来说,这就好像使用AddRange()来添加足够的项目以超过当前容量将导致容量增加,就像使用Add()将超过当前容量一样.

那么,List<T>.AddRange()在一个大到足以超过当前容量的块中添加项目会导致容量增加到足以容纳新项目,还是会导致容量加倍？或者它是否做了我甚至没有考虑过的其他事情？

希望这很清楚,没有任何代码示例,因为它是关于如何List<T>实现的一般性问题,但如果不是,我将添加任何将使我的问题更清楚的问题.如上所述,我已经阅读了MSDN文档,但找不到明确的答案.我在这里也搜索过任何类似的问题但找不到任何类似的问题,但如果有一个我错过的请指点我!

Answer 1

只要集合作为AddRange参数实现传递,ICollection<T>数组大小只增加一次:

ICollection<T> collection2 = collection as ICollection<T>;
if (collection2 != null)
{
    int count = collection2.Count;
    if (count > 0)
    {
        this.EnsureCapacity(this._size + count);

    // (...)

否则Insert,每个元素的标准枚举和方法调用都完成了:

}
else
{
    using (IEnumerator<T> enumerator = collection.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            this.Insert(index++, enumerator.Current);
        }
    }
}

编辑

研究EnsureCapacity方法:

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num > 2146435071)
        {
            num = 2146435071;
        }
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

它增加了数组大小Max(old_size * 2, min),并且因为它min = old_size + count在AddRange调用后将被设置为最终数组大小调用Max(old_size * 2, old_size + count)- 它将对List<T>使用AddRange方法添加的当前大小和集合大小保持警惕.