Is it safe to delete from SortedList during iteration

Question

Hi,

My question is is it safe for enumerator to remove item from SortedList?

SortedList<decimal, string> myDictionary;
// omitted code

IEnumerator<decimal, string> enum = myDictionary.GetEnumerator();

while(enum.MoveNext)
{
  // is it ok to remove here?
  myDictionary.Remove(enum.Current.Key);
}

Answer 1

This will throw an exception - you cannot modify a collection while iterating over it.

If you think about it a little, you will understand why. If adding or removing from the collection was allowed, you would no longer be iterating over the same collection - you either have too many (adding) or not enough items (removing).

Answer 2

Operations on the list during iterations are not supported in general. The expected behaviour is to throw an exception, but even if a collection fails to do this you must not rely on this working correctly.

You can first copy the elements into another list and then iterate over this new list of items to be modified.

Answer 3

No. An InvalidOperationExcpetion is thrown. I agree that already enumerated items might be deletable since there is a fixed index. However the issue is the following:

The implementation of SortedList is not clever enough to figure out that the removal will have no affect on the further execution of the enumerable. And to keep it simple and performing well, it shouldn't.

Answer 4

As already stated what you are looking to do is not possible. However, an alternative solution would be to simply maintain a list of items marked for deletion and then remove these afterwords. I would also opt for a foreach rather than a while loop, less code e.g.

var removeList = new List<decimal>();
foreach (var item in myDictionary)
{
    // have a condition which indicates which items are to be removed
    if (item.Key > 1)
    {
        removeList.Add(item.Key);
    }
}

Or if you are simply trying to retrieve items for deletion, use LINQ

var removeList = myDictionary.Where(pair => pair.Key > 1).Select(k => k.Key).ToList();

Then just remove them from the list.

// remove from the main collection
foreach (var key in removeList)
{
    myDictionary.Remove(key);
}

Answer 5

As others have already pointed out it will not work. However, since the collection is a SortedList you can use the RemoveAt method.

This method has a slightly better memory profile since it requires no overhead as opposed to a O(n) increase using a separate list to keep track of removals. It would also have a O(n^2) performance profile as opposed to O(n^2 * log(n)). The RemoveAt method is O(n) since it must perform an array copy. The Remove method adds a O(log(n)) operation to find the index before internally calling RemoveAt. All of this is probably of no concern to you, but it is useful know in case you run into situations involving a lot of 'n'.

var myDictionary = new SortedList<decimal, string>();

// omitted code

int i = 0;
while (myDictionary.Count > 0 && i < myDictionary.Count)
{
  if (/* predicate to use for removal */)
  {
    myDictionary.RemoveAt(i);
  }
  else
  {
    i++;
  }
}