枚举时从列表中删除项目 [英] Remove items from list while enumerating
问题描述
嗨
我有一个包含数千个项目的排序列表。在我的情况下，但是这个
并不重要，对象只存储在Keys中，值都是
没什么。一些存储的对象（可能是一个很大的数字）要删除
（比如当ToBeRemoved = true时）。
class SomeObj
ToBeRemoved是一个布尔字段
结束类
迭代后跟集合更方便，获得
元素
DirectCast（SList.List.GetKey（i），SomeObj）和以防万一（比如说
ToBeRemoved为真）用SList.List.RemoveAt删除它们（i）或者
重建列表只接受未删除的那些？
（在后一种情况下，问题是列表不应该是使用New（）
构造函数重新创建
，因为它可能被其他对象使用，而且其中一个确实需要
不想要断开SList参考。）
-P
Hi
I have a sorted list with several thousands items. In my case, but this
is not important, objects are stored only in Keys, Values are all
Nothing. Several of the stored objects (might be a large number) have
to be removed (say when ToBeRemoved = true).
class SomeObj
ToBeRemoved be a boolean field
end class
It is more convenient to iterate backword the collection, getting the
element
DirectCast(SList.List.GetKey(i), SomeObj) and in case (say if
ToBeRemoved is true) to remove them with SList.List.RemoveAt(i) or to
rebuild the List taking only the ones not removed?
(In the latter case, a problem is that the list should not be recreated
using a New()
constructor, because it may be being used by other objects and one does
not want to disconnect the SList reference. )
How do I do this in the most efficient way?
-P
推荐答案
pa * * *********@libero.it 写道：
嗨
我有一个包含数千个项目的排序列表。在我的情况下，但是这个
并不重要，对象只存储在Keys中，值都是
没什么。一些存储的对象（可能是一个很大的数字）要删除
（比如当ToBeRemoved = true时）。
class SomeObj
ToBeRemoved是一个布尔字段
结束类
迭代后跟集合更方便，获得
元素
DirectCast（SList.List.GetKey（i），SomeObj）和以防万一（比如说
ToBeRemoved为真）用SList.List.RemoveAt删除它们（i）或者
重建列表只接受未删除的那些？
（在后一种情况下，问题是列表不应该是使用New（）
构造函数重新创建
，因为它可能被其他对象使用，而且其中一个确实需要
不想要断开SList参考。）
如何以最有效的方式执行此操作？
Hi
I have a sorted list with several thousands items. In my case, but this
is not important, objects are stored only in Keys, Values are all
Nothing. Several of the stored objects (might be a large number) have
to be removed (say when ToBeRemoved = true).
class SomeObj
ToBeRemoved be a boolean field
end class
It is more convenient to iterate backword the collection, getting the
element
DirectCast(SList.List.GetKey(i), SomeObj) and in case (say if
ToBeRemoved is true) to remove them with SList.List.RemoveAt(i) or to
rebuild the List taking only the ones not removed?
(In the latter case, a problem is that the list should not be recreated
using a New()
constructor, because it may be being used by other objects and one does
not want to disconnect the SList reference. )
How do I do this in the most efficient way?
有两种常用的方法。
您点击其中一种：向后遍历列表并使用
RemoveAt（i）。
另一个是建立第二个要删除的项目列表，然后在循环后建立
完成后，循环遍历项目列表并删除它们。
这对于像Hashtable这样的键控集合更好用，其中
索引是不可用的，或者在其中这并不意味着：
ArrayList thingsToRemove = new ArrayList（）;
foreach（myCollection中的东西）
{
if（ShouldRemove（t））
{
thingsToRemove.Add（t）;
}
}
foreach（事情要移除）
{
myCollection.Remove（t）;
}
There are two usual ways.
You hit upon one of them: iterate backward through the list and use
RemoveAt(i).
The other is to build a second list of items to be removed, and then
after the loop is done, loop through the list of items and remove them.
This tends to work better with keyed collections like Hashtable where
indexing isn''t available, or in which it doesn''t mean much:
ArrayList thingsToRemove = new ArrayList();
foreach (Thing t in myCollection)
{
if (ShouldRemove(t))
{
thingsToRemove.Add(t);
}
}
foreach (Thing t in thingsToRemove)
{
myCollection.Remove(t);
}
pa *********** @ libero.it 写道：
&g t;
[snip]
如何以最有效的方式执行此操作？
>
[snip]
How do I do this in the most efficient way?
您好，
我认为高效率意味着执行速度。我还假设
你在谈论SortedList，因为你说集合
存储了键值对。这实际上非常棘手。你提到
向后枚举整个集合并调用RemoveAt。
这似乎是表面上的一种有效方法，但是在
a的情况下SortedList考虑发生了什么。 RemoveAt方法将导致
列表中较低的所有项目向上移动以替换已删除的项目。
这是一个O（n）操作。首先在
中枚举集合的循环也是一个O（n）操作。合并后的结果是O（n ^ 2）。
您可以使用SortedDictionary或等效的数据结构。
Remove和RemoveAt方法是O（log（n））。因此组合操作
将为O（n * log（n））。这是一个重大改进。
不幸的是，SortedDictionary仅存在于2.0中。所以，如果你仍然在1.1上，那么你必须下载开源.NET Power
集合以获得相同的数据结构。
根据具体要求，您还可以在内部创建自己的
自定义集合，该集合使用ArrayList。
保持列表排序的责任在于你。
的优势在于您可以完全控制
删除的方式和内容。我认为*我可以说服你，如果正确完成，删除所需的项目
将是O（n）操作。我准备错了
。缺点是你需要更多的b $ b b编码。
Brian
Hello,
I assume by efficient you mean execution speed. I also assume that
you''re talking about the SortedList because you said the collection
stores key-value pairs. This is actually quite tricky. You mentioned
enumerating through the collection backwards and calling RemoveAt.
That seems like an efficient method on the surface, but in the case of
a SortedList consider what''s happening. The RemoveAt method will cause
all items lower in the list to move up to replace the removed item.
That''s a O(n) operation. The loop to enumerate the collection in the
first place is also a O(n) operation. The combined result is O(n^2).
You could use a SortedDictionary or equivalent data structure. The
Remove and RemoveAt methods are O(log(n)). So the combined operation
would be O(n*log(n)). That''s a significant improvement.
Unfortunately, the SortedDictionary only exists in 2.0. So if you''re
still on 1.1 you''d have to download the open source .NET Power
Collections to get an equivalent data structure.
Depending on the exact requirements you could also create your own
custom collection that uses an ArrayList internally. The
responsibility of keeping the list sorted would be on you. The
advantage is that you have complete control of how and what items to
remove. I *think* I could convince you that removing the desired items
would be a O(n) operation if done correctly. I''m prepared to be wrong
about that though. The disadvantage is that it would require more
coding on your part.
Brian
全部谢谢。
*非常*乐于助人。
实际上我怀疑仅仅删除就可能是O（n）
我假设二叉树上的一些重构操作必须执行
。
所以SortedDictionary更好去除操作。
但是在这一点上重新创建整个列表会更好。这个
将是O（n）？
在这种情况下，问题是我如何保留具有
$ b的引用$ b已经
附加到其他对象上？
这可能是一个耗时的操作列表吗？
-P
Brian Gideon ha scritto：
Thanks all.
*Very* helpful.
Actually I was suspecting that the mere removal could be O(n) since
I assume that some recompact operation on the binary tree must
be carried out.
So the SortedDictionary is better fore removal operations.
But at this point would be better to recreate the whole list. This
would be O(n) ?
In such a a case, the problem is how do I keep the references that have
already
been attached to other objects?
And is perhaps the list inizialization a time consuming operation ?
-P
Brian Gideon ha scritto:
pa *********** @ libero.it 写道：
[snip]
如何以最有效的方式执行此操作？
[snip]
How do I do this in the most efficient way?
您好，
我认为高效率意味着执行速度。我还假设
你在谈论SortedList，因为你说集合
存储了键值对。这实际上非常棘手。你提到
向后枚举整个集合并调用RemoveAt。
这似乎是表面上的一种有效方法，但是在
a的情况下SortedList考虑发生了什么。 RemoveAt方法将导致
列表中较低的所有项目向上移动以替换已删除的项目。
这是一个O（n）操作。首先在
中枚举集合的循环也是一个O（n）操作。合并后的结果是O（n ^ 2）。
您可以使用SortedDictionary或等效的数据结构。
Remove和RemoveAt方法是O（log（n））。因此组合操作
将为O（n * log（n））。这是一个重大改进。
不幸的是，SortedDictionary仅存在于2.0中。所以，如果你仍然在1.1上，那么你必须下载开源.NET Power
集合以获得相同的数据结构。
根据具体要求，您还可以在内部创建自己的
自定义集合，该集合使用ArrayList。
保持列表排序的责任在于你。
的优势在于您可以完全控制
删除的方式和内容。我认为*我可以说服你，如果正确完成，删除所需的项目
将是O（n）操作。我准备错了
。缺点是你需要更多的b $ b b编码。
Brian
Hello,
I assume by efficient you mean execution speed. I also assume that
you''re talking about the SortedList because you said the collection
stores key-value pairs. This is actually quite tricky. You mentioned
enumerating through the collection backwards and calling RemoveAt.
That seems like an efficient method on the surface, but in the case of
a SortedList consider what''s happening. The RemoveAt method will cause
all items lower in the list to move up to replace the removed item.
That''s a O(n) operation. The loop to enumerate the collection in the
first place is also a O(n) operation. The combined result is O(n^2).
You could use a SortedDictionary or equivalent data structure. The
Remove and RemoveAt methods are O(log(n)). So the combined operation
would be O(n*log(n)). That''s a significant improvement.
Unfortunately, the SortedDictionary only exists in 2.0. So if you''re
still on 1.1 you''d have to download the open source .NET Power
Collections to get an equivalent data structure.
Depending on the exact requirements you could also create your own
custom collection that uses an ArrayList internally. The
responsibility of keeping the list sorted would be on you. The
advantage is that you have complete control of how and what items to
remove. I *think* I could convince you that removing the desired items
would be a O(n) operation if done correctly. I''m prepared to be wrong
about that though. The disadvantage is that it would require more
coding on your part.
Brian
这篇关于枚举时从列表中删除项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
