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

Question

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

как лучше всего это сделать?

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

Answer 1

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

Что-то вроде этого:

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

Answer 2

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

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

Answer 3

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

Например:

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

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

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