RemoveRange()方法如何在List <>中工作？

Question

如标题.我知道它可能在删除项目之前和之后合并了2个子列表,但是在删除LAST元素时该方法的行为如何？换句话说:它是否以某种方式复制了删除索引之前所有元素？我只是对在巨型列表上使用RemoveRange的性能感到好奇(假设说5000个元素)只是为了删除fe中的最后2个.

如果它复制了那么,是否有办法更改一些设置List大小的内部变量(并将其余的已分配元素视为垃圾)？

我只是设法找到一个信息,它是一个O(n)复杂度算法,但我不确定该情况下的"n"是列表大小,还是要删除的项目数.

任何提示都会很高兴.

Answer 1

它将做的是在项目范围结束后取出每个项目,并将其移除并在列表中按移除的项目数量向上移动.就性能影响而言,在移动的项目范围结束后,每个项目将有一个副本.这意味着当从末尾移除时它将表现最佳(它将是O(1))并且在从开始移除时执行最差(O(n)).

例如,请考虑以下列表:

index - value

0 - A
1 - B
2 - C
3 - D
4 - E
5 - F
6 - G

如果我们调用RemoveRange(2, 2) 那么我们将从索引2开始删除两个项目,因此我们将删除C和D.

这意味着需要将E复制到索引2,然后需要将F复制到索引3,并且需要将G复制到索引4.在删除最后一个项目后,每个项目都有一个复制操作.

请注意,由于您可以将整个内存块"向上"移动两个,因此最终在实践中更有效地单独复制每个项目.对于计算机内存来说,将整个内存块向上移动一定数量的字节比将大量内存小部分移动到不同的任意位置要容易得多.它虽然具有相同的渐近复杂性.

Answer 2

List<T>只是一个数组的包装器,_items在下面的代码中调用.数组中的插槽可能比列表中的项目多,因此_size用于跟踪实际有效的数量.当你做RemoveRange(index, count)...

_size -= count;
if (index < _size)
    Array.Copy(_items, index + count, _items, index, _size - index);
Array.Clear(_items, _size, count);

...它将项目从过去的范围复制到现在空白的空间中,并清除旧项目.

如果要删除接近大列表开头的范围,那么成本与列表的大小成比例,因为必须向下移动很多东西.

如果要移除靠近大型列表末尾的大范围,则复制很便宜但清除费用很高,因此成本将与移除范围的大小成比例.