CODEWITHSUNDEEP
c#genericscollections
chaosTechnician
chaosTechnician

Reputation: 1700

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.

Upvotes: 13

Views: 9844

Answers (6)

Daniel Earwicker
Daniel Earwicker

Reputation: 116674

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.

Upvotes: 5

user703016
user703016

Reputation: 37945

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 */);

Upvotes: 10

dlev
dlev

Reputation: 48596

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.

Upvotes: 15

Ahmad Mageed
Ahmad Mageed

Reputation: 96487

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]);

Upvotes: 5

user195488
user195488

Reputation:

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).

Upvotes: 2

Ivan Danilov
Ivan Danilov

Reputation: 14777

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.

Upvotes: 3

Related Questions