Does removing items from a C# List<T> retain other items' orders?

Lately, I've been writing a lot of code that looks like this:

List<MyObject> myList = new List<MyObject>();
...
for(int i = 0; i < myList.Count; ++i)
{
  if(/*myList[i] meets removal criteria*/)
  {
     myList.RemoveAt(i);
     --i;  //Check this index again for the next item
     //Do other stuff as well
  }
}

and I just became a little paranoid that maybe List doesn't retain object order at removal. I don't know the C# spec well enough to know for sure. Can someone verify that I either am or am not asking for trouble with this pattern?

EDIT: Perhaps I should clarify that the above is a very simplified example and more things happen if the item needs to be removed so I don't think List<T>.RemoveAll() is terribly applicable here. Although it is a nice function. I have added a comment in开发者_JAVA技巧 the if() block above to specifically mention that.

List<T> will always maintain relative order when adding, inserting and removing; it wouldn't be a list if it didn't.

Here's the (ILSpy'ed) code for RemoveAt():

public void RemoveAt(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;
}

Note the array copy from index + 1 to index; that's the items being shifted wholesale and "squeezing" the array together. But there is definitely no re-ordering of the elements.

You are indeed right, List<T>.RemoveAt will not change the order of the items of the list.

Your snippet could however be simplified to use List<T>.RemoveAll like this:

List<MyObject> myList = new List<MyObject>();
...
myList.RemoveAll(/* Removal predicate */);

Edit following comment:

myList.Where(/* Removal predicate */).ToList().ForEach(/* Removal code */);
myList.RemoveAll(/* Removal predicate */);

The order should be maintained. A better approach is to traverse the list in reverse:

for(int i = myList.Count - 1; i >= 0; i--)
{
    if(/*myList[i] meets removal criteria*/)
    {
        myList.RemoveAt(i);
    }
}

Or you could use the RemoveAll method:

myList.RemoveAll(item => [item meets removal criteria]);

Although the accepted answer is a great answer to the original question, Cicada's answer suggests an alternative approach.

With CLR 4 (VS 2010) we gain yet another approach, which has the further advantage of only executing the predicate once per item (and making it convenient to avoid writing the predicate twice in our code).

Suppose you have a IEnumerable<string>:

IEnumerable<string> myList = new[] {"apples", "bananas", "pears", "tomatoes"};

You need to divide it into two lists according to whether the items pass some criteria:

var divided = myList.ToLookup(i => i.Length > 6);

The returned object is somewhat like a Dictionary of lists. Suppose you want to keep the ones that pass the criteria:

 myList = divided[true];

And you can use a familiar imperative loop to operate on the other items:

foreach (var item in divided[false])
    Console.WriteLine("Removed " + item);

Note that there is no need to use List<T> specifically. We never modify an existing list - we just make new ones.

From Reflector:

public void RemoveAt(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;
}

So at least with MS' implementation - items' order doesn't change on RemoveAt.

When you call RemoveAt, all the elements following the index you remove will be copied and shifted forward.

Sort the positions list in descending order and remove elements in that order.

foreach (var position in positions.OrderByDescending(x=>x))
   list.RemoveAt(position);

positions is the list of indexes. list is the one you want to delete from (it contains the actual data).