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

Question

У меня есть список элементов для удаления из упорядоченной коллекции на C#.

Каков наилучший способ обойти это?

Если я удалю элемент посередине, индекс изменится, но что, если я хочу удалить несколько элементов?

Answer 1

Чтобы избежать изменения индекса, начать в конце и идти в обратном направлении, чтобы индекс 0.

Что-то вдоль этих линий:

for(int i = myList.Count - 1; i >= 0; i++) 
{ 
    if(NeedToDelete(myList[i])) 
    { 
     myList.RemoveAt(i); 
    } 
} 

Answer 2

Какой тип коллекции? Если он наследует от ICollection, вы можете просто запустить цикл над списком элементов для удаления, а затем вызвать метод .Remove() в коллекции.

Для примера:

object[] itemsToDelete = GetObjectsToDeleteFromSomewhere(); 
ICollection<object> orderedCollection = GetCollectionFromSomewhere(); 

foreach (object item in itemsToDelete) 
{ 
    orderedCollection.Remove(item); 
} 

Answer 3

Если коллекция является List<T> вы также можете использовать RemoveAll метод:

list.RemoveAll(x => otherlist.Contains(x)); 

Answer 4

Предполагая, что список элементов, подлежащих удалению, является относительно коротким, вы можете первым сортировать целевой список. Затем перейдите в исходный список и сохраните индекс в целевом списке, который соответствует удаляемому элементу.

Предполагается, что список источника haystack и список элементов удаляемых needle:

needle.Sort(); // not needed if it's known that `needle` is sorted 
// haystack is known to be sorted 
haystackIdx = 0; 
needleIdx = 0; 
while (needleIdx < needle.Count && haystackIdx < haystack.Count) 
{ 
    if (haystack[haystackIdx] < needle[needleIdx]) 
     haystackIdx++; 
    else if (haystack[haystackIdx] > needle[needleIdx]) 
     needleIdx++; 
    else 
     haystack.RemoveAt(haystackIdx); 
} 

Таким образом, у вас есть только 1 обход как haystack и needle, плюс время сортировки needle, при условии, что удаление - O(1) (что часто бывает для связанных списков и подобных коллекций). Если коллекция является List<...>, удаление потребуется O(collection size) из-за сдвигов данных, так что лучше начать с конца обеих коллекций и перейти к началу:

needle.Sort(); // not needed if it's known that `needle` is sorted 
// haystack is known to be sorted 
haystackIdx = haystack.Count - 1; 
needleIdx = needle.Count - 1; 
while (needleIdx >= 0 && haystackIdx >= 0) 
{ 
    if (haystack[haystackIdx] > needle[needleIdx]) 
     haystackIdx--; 
    else if (haystack[haystackIdx] < needle[needleIdx]) 
     needleIdx--; 
    else 
     haystack.RemoveAt(haystackIdx--); 
}