Как исправить ошибку при удалении элементов из коллекции во время итерации

Что проверяют

Понимаете ли вы, откуда берётся InvalidOperationException с текстом Collection was modified; enumeration operation may not execute, и знаете ли готовые методы вместо самодельных обходов. Следом обычно спрашивают про сложность каждого варианта и про многопоточный код.

Как отвечать

Сначала механизм. List<T> хранит внутренний счётчик версий и увеличивает его при каждом Add, Remove, Insert. Перечислитель, который создаёт foreach, запоминает версию при старте и сверяет её на каждом MoveNext. Не совпала, значит исключение. Потоки тут ни при чём, ошибка воспроизводится в одном потоке.

Варианты исправления:

• list.RemoveAll(predicate): лучший выбор для List<T>. Один проход, элементы сдвигаются один раз, O(n);
• обратный for с RemoveAt(i): корректно, потому что удаление не сдвигает ещё не просмотренные индексы. Но каждый RemoveAt сдвигает хвост массива, в худшем случае O(n²);
• новая коллекция: list = list.Where(x => !Cond(x)).ToList(). Просто и читаемо, но выделяет новый список, а другие ссылки на старый продолжают видеть прежние данные;
• обход копии: foreach (var x in list.ToList()) с удалением из оригинала. Работает, но это копия плюс O(n) на каждый Remove;
• HashSet<T>.RemoveWhere: аналог RemoveAll для множеств;
• Dictionary<TKey, TValue>: начиная с .NET Core 3.0 вызовы Remove и Clear во время foreach перечислитель не ломают, а добавление нового ключа по-прежнему бросает исключение. В .NET Framework бросало и удаление.

Для данных, которые меняют несколько потоков, нужен ConcurrentDictionary: его перечисление не падает при параллельных изменениях, но и снимка на момент начала обхода не даёт.

Где спотыкаются

Пишут прямой for с RemoveAt(i). Исключения нет, зато после удаления следующий элемент встаёт на место i и пропускается: из { 2, 4, 5 } четвёрка останется.

Собирают toRemove, а потом вызывают Remove для каждого элемента. Это O(n·m), а при дубликатах Remove удаляет только первое вхождение.

Оборачивают цикл в lock, считая ошибку гонкой потоков. Блокировка ничего не меняет, потому что коллекцию меняет тот же код, который её перебирает.