List<>中的RemoveRange()方法如何工作? [英] How does the RemoveRange() method work in a List<>?
问题描述
与标题相同.我知道它可能在删除项目之前和之后合并2个子列表，但是在删除LAST元素时该方法的行为如何?换句话说:它是否以某种方式复制了删除索引之前的所有元素?我只是很好奇在大型List(比如说5000个元素)上使用RemoveRange来删除f.e.只有最后两个.
如果它复制了副本，是否有办法更改一些内部变量来设置List的大小(并将其余分配的元素视为垃圾)?
我只能设法找到一个信息，它是一种O(n)复杂度算法，但是我不确定这种情况下的"n"是列表大小还是要删除的项目数.
任何提示都会很高兴.
要做的是将要删除的项目范围结束后的每个项目取走，然后将其在列表中按已删除项目的数量向上移动.就性能影响而言，在移动的项目范围结束后，每个项目都会有一个副本.这意味着从结尾处删除时效果最佳(为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.在删除了最后一个项目之后，每个项目都有一个复制操作.
请注意，由于您可以将整个内存块上移"两个事实，因此在实际操作中比单独复制每个项目更有效.对于计算机内存而言，将整个内存块上移一定数量的字节要容易得多，而不是将很多小部分内存移至不同的任意位置.它将具有相同的渐近复杂度.
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.
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.
Will be glad for any hint.
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)).
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.
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.
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.
这篇关于List<>中的RemoveRange()方法如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
