C# RemoveRange() 方法如何在 List<> 中工作？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16064983/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How does the RemoveRange() method work in a List<>?
提问by Tarec
As in title. I know it probably merges 2 sublists before and after deleted items, but how does that method behave when removing LAST elements? In other words: does it somehow make a copy of all elements located before remove index? I'm just curious about perfomance of using RemoveRange on a giant List (let's say 5000 elements) just to remove f.e. only last 2 of them.
如标题。我知道它可能会在删除项目之前和之后合并 2 个子列表，但是在删除 LAST 元素时该方法的行为如何？换句话说：它是否以某种方式复制了删除索引之前的所有元素？我只是对在一个巨大的列表（假设有 5000 个元素）上使用 RemoveRange 的性能感到好奇，只是为了删除 fe 只删除其中的最后 2 个。
If it makes a copy then, is there a way to change some internal variable that sets size of the List (and treat rest of allocated elements as garbage)?
如果它进行复制，有没有办法更改一些设置列表大小的内部变量（并将其余已分配元素视为垃圾）？
I only managed to find an info, that it's an O(n) complexity algorithm, but I'm not sure if the "n" by that case is a List size, or a number of items to delete.
我只找到了一个信息，它是一个 O(n) 复杂度算法，但我不确定这种情况下的“n”是列表大小还是要删除的项目数。
Will be glad for any hint.
任何提示都会很高兴。
采纳答案by Servy
What it will do is take each item after the end of the range of items to remove and move it up in the list by the number of items that were removed. In terms of performance implications there will be one copy for each item after the end of the range of items moved. This means that it will perform best when removing from the end (it'll be O(1)) and perform worst when removing from the start (O(n)).
它将做的是在要删除的项目范围结束后取出每个项目，并根据已删除项目的数量将其在列表中向上移动。就性能影响而言，在移动的项目范围结束后，每个项目将有一个副本。这意味着它在从末尾移除时性能最好（它将是 O(1)），而在从头移除时性能最差（O(n)）。
As an example, consider the following list:
例如，请考虑以下列表：
index - value 0 - A 1 - B 2 - C 3 - D 4 - E 5 - F 6 - G
If we call RemoveRange(2, 2)Then we're removing two items starting at index 2, so we're removing C and D.
如果我们调用RemoveRange(2, 2)Then 我们将删除从索引 2 开始的两个项目，因此我们将删除 C 和 D。
This means E needs to be copied to index 2, then F needs to be copied to index 3, and G needs to be copied to index 4. There is one copy operation for each item after the last item removed.
这意味着需要将 E 复制到索引 2，然后需要将 F 复制到索引 3，需要将 G 复制到索引 4。在删除最后一项后，每个项都有一个复制操作。
Note that because of the fact that you can move the entire block of memory "up" by two this ends up being more efficient in practice that copying each item individually. It's a lot easier for a computers memory to move an entire block of memory up by some fixed number of bytes than to move lots of little sections of memory to different arbitrary locations. It will have the same asymptotic complexity though.
请注意，由于您可以将整个内存块“向上”移动两个，这在实践中最终比单独复制每个项目更有效。对于计算机内存来说，将整个内存块向上移动一定数量的字节比将许多小的内存部分移动到不同的任意位置要容易得多。尽管如此，它将具有相同的渐近复杂性。
回答by Eric Lippert
List<T>is just a wrapper around an array, called _itemsin the code below. The array might have more slots in it than there are items in the list, so _sizeis used to keep track of how many are actually valid. When you do a RemoveRange(index, count)...
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);
...it copies the items from past the range into the now-empty space, and clears the old items.
...它将超出范围的项目复制到现在为空的空间，并清除旧项目。
If you are removing a range close to the beginning of a large list then the cost is proportional to the size of the list, because so much stuff has to be moved down.
如果您要删除靠近大列表开头的范围，那么成本与列表的大小成正比，因为必须向下移动太多内容。
If you are removing a large range close to the end of a large list then the copying is cheap but the clearing is expensive, so the cost will be proportional to the size of the range removed.
如果要删除靠近大列表末尾的大范围，则复制便宜但清除费用昂贵，因此成本将与删除的范围的大小成正比。
