Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 the if() block above to specifically mention that.

like image 846
chaosTechnician Avatar asked Aug 05 '11 19:08

chaosTechnician


2 Answers

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.

like image 54
dlev Avatar answered Oct 05 '22 19:10

dlev


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 */);
like image 43
user703016 Avatar answered Oct 05 '22 19:10

user703016