On Sun, 13 May 2007 16:06:36 -0700, Zytan <zy**********@g mail.comwrote:
Obviously you can't just use a simple for loop, since you may skip
over elements.
You could modify the loop counter each time an element is deleted.
But, the loop ending condition must be checked on each iteration,
since the Count changes as you delete elements. I would think it is
guaranteed to be computed each time, and not cached.
So, is this the best way?
I like Marc's suggestion, to use a predicate delegate to control removal..
It seems tailor-made to the exact scenario you're asking about.
Note that if efficiency is of concern, you may prefer to actually generate
a whole new List<instance instead, copying over only the values you want
to the new List<>. The reason being that, if I recall correctly, the
List<implementa tion uses an array, and insertions and removals in the
array require shifting the contents of the array. In other words, even if
you start at the end, removing elements one at a time involves copying on
average half of the array for each removal.
If you're removing a large percentage of the elements, and you start at
the end of the list, this will help by ensuring that you're shifting the
minimal number of elements with each removal. But you still have the
shift. If you're willing to create a new copy of the List<>, then you can
preallocate the List<to be as large as is necessary to ensure no
reallocations during the processing, and then if you're concerned about
wasted memory once you're done, trim the List<>.
The docs *claim* that RemoveAll() is O(n). So it's possible that
internally, it does exactly what I describe above. It's hard to see how,
if the List<implementa tion really is an array, it could be O(n)
otherwise. But there's a bunch of assumptions in the first part of this
paragraph, so if you really care it seems to me you should probably do
some direct tests between the various methods (and in particular, doing
your own copy-based algorithm vs using RemoveAll()).
If it's not that important (and frankly, it probably isn't until you have
proven to yourself that this part of the code is important for performance
in your application overall), then you should probably just use
RemoveAll() and trust the docs. :)
Finally, note that at the very least I don't see any point in incrementing
a counter that you've just decremented. While the algorithm you posted
could be greatly improved as already mentioned, at a minimum it seems to
me it should look more like this:
List<intmylist = /* whatever */;
int i = 0;
while (i < mylist.Count)
{
if (want_to_remove )
{
mylist.RemoveAt (i);
}
else
{
i++;
}
}
Pete
