Jak usunąć elementy z ogólnej listy podczas iteracji?

451

Szukam lepszego wzorca do pracy z listą elementów, które każdy musi przetworzyć, a następnie w zależności od wyniku zostaną usunięte z listy.

Nie możesz używać .Remove(element)wewnątrz foreach (var element in X)(ponieważ powoduje to Collection was modified; enumeration operation may not execute.wyjątek) ... nie możesz także używać for (int i = 0; i < elements.Count(); i++)i .RemoveAt(i)ponieważ zaburza twoją obecną pozycję w kolekcji względem i.

Czy jest na to elegancki sposób?

InvertedAcceleration
źródło

Odpowiedzi:

734

Iteruj swoją listę w odwrotnej kolejności za pomocą pętli for:

for (int i = safePendingList.Count - 1; i >= 0; i--)
{
    // some code
    // safePendingList.RemoveAt(i);
}

Przykład:

var list = new List<int>(Enumerable.Range(1, 10));
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] > 5)
        list.RemoveAt(i);
}
list.ForEach(i => Console.WriteLine(i));

Alternatywnie możesz użyć metody RemoveAll z predykatem, aby przetestować:

safePendingList.RemoveAll(item => item.Value == someValue);

Oto uproszczony przykład do zademonstrowania:

var list = new List<int>(Enumerable.Range(1, 10));
Console.WriteLine("Before:");
list.ForEach(i => Console.WriteLine(i));
list.RemoveAll(i => i > 5);
Console.WriteLine("After:");
list.ForEach(i => Console.WriteLine(i));
Ahmad Mageed
źródło
19
Dla tych, którzy pochodzą z Javy, lista C # jest jak ArrayList w tym, że wstawianie / usuwanie to O (n), a pobieranie przez indeks to O (1). To nie jest tradycyjna lista z linkami. Wydaje się nieco niefortunne, że C # używa słowa „Lista” do opisania tej struktury danych, ponieważ przypomina klasyczną listę z linkami.
Jarrod Smith
79
Nic w nazwie „Lista” nie mówi „LinkedList”. Ludzie pochodzący z innych języków niż Java mogą być zdezorientowani, gdy będzie to połączona lista.
GolezTrol
5
Skończyłem tutaj przez wyszukiwanie vb.net, więc na wypadek, gdyby ktoś chciał mieć równoważną składnię vb.net dla RemoveAll:list.RemoveAll(Function(item) item.Value = somevalue)
pseudocoder
1
Działa to również w Javie z minimalną modyfikacją: .size()zamiast .Counti .remove(i)zamiast .removeAt(i). Sprytne - dzięki!
Jesień Leonard,
2
Zrobiłem mały test wydajności i okazało się, że RemoveAll()zajmuje to trzy razy więcej czasu niż forpętla wsteczna . Zdecydowanie trzymam się pętli, przynajmniej w sekcjach, w których ma to znaczenie.
Crusha K. Rool,
84

Proste i proste rozwiązanie:

Użyj standardowej pętli for działającej wstecz w swojej kolekcji i RemoveAt(i)do usuwania elementów.

Jan
źródło
2
Pamiętaj, że usuwanie elementów pojedynczo nie jest skuteczne, jeśli lista zawiera wiele elementów. Może potencjalnie być O (n ^ 2). Wyobraź sobie Listę zawierającą dwa miliardy pozycji, w której zdarza się, że pierwszy miliard pozycji zostaje ostatecznie usunięty. Każde usunięcie wymusza skopiowanie wszystkich późniejszych elementów, więc każdy z nich kopiuje miliard elementów miliard razy każdy. Nie dzieje się tak z powodu odwrotnej iteracji, lecz z powodu jednorazowego usuwania. RemoveAll zapewnia, że ​​każdy element jest kopiowany maksymalnie raz, dzięki czemu jest liniowy. Usuwanie pojedynczo może być miliard razy wolniejsze. O (n) versus O (n ^ 2).
Bruce Dawson
71

Odwrotna iteracja powinna być pierwszą rzeczą, która przychodzi na myśl, gdy chcesz usunąć elementy z kolekcji podczas iteracji nad nią.

Na szczęście istnieje bardziej eleganckie rozwiązanie niż pisanie pętli for, która wymaga niepotrzebnego pisania i może być podatna na błędy.

ICollection<int> test = new List<int>(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

foreach (int myInt in test.Reverse<int>())
{
    if (myInt % 2 == 0)
    {
        test.Remove(myInt);
    }
}
jedesah
źródło
7
To działało idealnie dla mnie. Prosty i elegancki oraz wymagał minimalnych zmian w moim kodzie.
Stephen MacDougall
1
Czy to po prostu genialny flippin? I zgadzam się z @StephenMacDougall, nie muszę używać tych C ++ do pętli i po prostu zaczynam korzystać z LINQ zgodnie z przeznaczeniem.
Piotr Kula
5
Nie widzę żadnej przewagi nad prostym foreach (int myInt w test.ToList ()) {if (myInt% 2 == 0) {test.Remove (myInt); }} Nadal musisz przydzielić kopię dla Odwrotnej, która wprowadza Huh? chwila - dlaczego jest Rewers.
jahav
11
@jedesah Tak, Reverse<T>()tworzy iterator, który przewija listę do tyłu, ale przydziela dla niej dodatkowy bufor o takim samym rozmiarze jak sama lista ( referenceource.microsoft.com/#System.Core/System/Linq/… ). Reverse<T>nie tylko przegląda oryginalną listę w odwrotnej kolejności (bez przydzielania dodatkowej pamięci). Dlatego obie ToList()i Reverse()mieć taką samą zużycie pamięci (zarówno tworzenie kopii), ale ToList()ma coś do danych nie. Dzięki Reverse<int>(), to zastanawiam się, dlaczego jest lista odwrócony, z jakiego powodu.
jahav
1
@jahav Rozumiem twój punkt widzenia. Jest to dość rozczarowujące, że wdrożenieReverse<T>() tworzy nowy bufor, nie jestem pewien, czy rozumiem, dlaczego jest to konieczne. Wydaje mi się, że w zależności od podstawowej struktury Enumerable, przynajmniej w niektórych przypadkach powinno być możliwe uzyskanie odwrotnej iteracji bez alokacji pamięci liniowej.
jedesah
68
 foreach (var item in list.ToList()) {
     list.Remove(item);
 }

Jeśli dodasz „.ToList ()” do swojej listy (lub wyników zapytania LINQ), możesz usunąć „element” bezpośrednio z „listy” bez obaw: „ Kolekcja została zmodyfikowana; operacja wyliczenia może nie zostać wykonana ”. błąd. Kompilator tworzy kopię „listy”, abyś mógł bezpiecznie usunąć tablicę.

Chociaż ten wzór nie jest super wydajny, ma naturalny charakter i jest wystarczająco elastyczny dla prawie każdej sytuacji . Na przykład, gdy chcesz zapisać każdy „element” w DB i usunąć go z listy tylko wtedy, gdy zapis DB się powiedzie.

Greg Little
źródło
6
To najlepsze rozwiązanie, jeśli wydajność nie jest kluczowa.
IvanP
2
jest to również szybsze i bardziej czytelne: list.RemoveAll (i => true);
Santiago arizti
1
@Greg Little, czy dobrze cię zrozumiałem - kiedy dodajesz kompilator ToList () przechodzi przez skopiowaną kolekcję, ale usuwa z oryginału?
Pyrejkee,
Jeśli twoja lista zawiera zduplikowane elementy i chcesz tylko usunąć element występujący później na liście, to czy to nie usunie niewłaściwego elementu?
Tim MB
Czy to działa również w przypadku listy obiektów?
Tom el Safadi
23

Wybierz elementy, które chcesz, zamiast próbować usunąć elementy, których nie chcesz. Jest to o wiele łatwiejsze (i ogólnie także bardziej wydajne) niż usuwanie elementów.

var newSequence = (from el in list
                   where el.Something || el.AnotherThing < 0
                   select el);

Chciałem opublikować to jako komentarz w odpowiedzi na komentarz pozostawiony przez Michaela Dillona poniżej, ale i tak jest on zbyt długi i prawdopodobnie przydatny w mojej odpowiedzi:

Osobiście nigdy nie usuwałbym elementów jeden po drugim, jeśli potrzebujesz usunięcia, to wywołanie, RemoveAllktóre bierze predykat i tylko raz przestawia wewnętrzną tablicę, podczas gdy Removewykonuje Array.Copyoperację dla każdego usuwanego elementu.RemoveAlljest znacznie wydajniejszy.

A gdy iterujesz wstecz po liście, masz już indeks elementu, który chcesz usunąć, więc wywołanie byłoby znacznie bardziej wydajne RemoveAt, ponieważ Removenajpierw przegląda listę, aby znaleźć indeks elementu, który próbuję usunąć, ale znasz już ten indeks.

Podsumowując, nie widzę powodu, aby kiedykolwiek wywoływać Removepętlę for. I najlepiej, jeśli jest to w ogóle możliwe, użyj powyższego kodu, aby przesyłać strumieniowo elementy z listy w razie potrzeby, aby w ogóle nie trzeba było tworzyć drugiej struktury danych.

JulianR
źródło
1
Albo to, albo dodaj wskaźnik do niechcianych elementów do drugiej listy, a następnie po zakończeniu pętli, iteruj listę usuwania i użyj jej do usunięcia elementów.
Michael Dillon
22

Użycie ToArray () na ogólnej liście pozwala na usunięcie (pozycji) z ogólnej listy:

        List<String> strings = new List<string>() { "a", "b", "c", "d" };
        foreach (string s in strings.ToArray())
        {
            if (s == "b")
                strings.Remove(s);
        }
Etienne Brouillard
źródło
2
To nie jest złe, ale muszę zaznaczyć, że omija to potrzebę utworzenia drugiej listy „przechowywania” elementów, które chcesz usunąć, kosztem skopiowania całej listy do tablicy. Druga lista ręcznie wybranych elementów będzie prawdopodobnie zawierać mniej przedmiotów.
Ahmad Mageed
20

Użycie .ToList () utworzy kopię listy, jak wyjaśniono w tym pytaniu: ToList () - Czy tworzy nową listę?

Używając ToList (), możesz usunąć z oryginalnej listy, ponieważ tak naprawdę iterujesz nad kopią.

foreach (var item in listTracked.ToList()) {    

        if (DetermineIfRequiresRemoval(item)) {
            listTracked.Remove(item)
        }

     }
StuartQ
źródło
1
Ale z punktu widzenia wydajności kopiujesz listę, co może zająć trochę czasu. Dobry i łatwy sposób na zrobienie tego, ale z niezbyt dobrym występem
Florian K
12

Jeśli funkcja, która określa, które elementy należy usunąć, nie ma skutków ubocznych i nie powoduje mutacji elementu (jest to czysta funkcja), prostym i wydajnym (liniowym czasem) rozwiązaniem jest:

list.RemoveAll(condition);

Jeśli są jakieś skutki uboczne, użyłbym czegoś takiego:

var toRemove = new HashSet<T>();
foreach(var item in items)
{
     ...
     if(condition)
          toRemove.Add(item);
}
items.RemoveAll(toRemove.Contains);

Jest to nadal czas liniowy, przy założeniu, że skrót jest dobry. Ale ma zwiększone wykorzystanie pamięci z powodu skrótu.

Wreszcie, jeśli twoja lista jest tylko IList<T>zamiast List<T>, proponuję moją odpowiedź na Jak mogę zrobić ten specjalny iterator Foreach? . Będzie to miało liniowy czas działania przy typowych implementacjach IList<T>, w porównaniu z kwadratowym czasem działania wielu innych odpowiedzi.

CodesInChaos
źródło
11

Jak każde usunięcie jest podejmowane pod warunkiem, którego możesz użyć

list.RemoveAll(item => item.Value == someValue);
Ahmad
źródło
To najlepsze rozwiązanie, jeśli przetwarzanie nie powoduje mutacji przedmiotu i nie wywołuje żadnych skutków ubocznych.
CodesInChaos
9
List<T> TheList = new List<T>();

TheList.FindAll(element => element.Satisfies(Condition)).ForEach(element => TheList.Remove(element));
Mauricio Ramalho
źródło
8

Nie możesz używać foreach, ale możesz iterować do przodu i zarządzać zmienną indeksu pętli po usunięciu elementu, na przykład:

for (int i = 0; i < elements.Count; i++)
{
    if (<condition>)
    {
        // Decrement the loop counter to iterate this index again, since later elements will get moved down during the remove operation.
        elements.RemoveAt(i--);
    }
}

Zauważ, że ogólnie wszystkie te techniki opierają się na zachowaniu iterowanej kolekcji. Pokazana tutaj technika będzie działać ze standardową Listą (T). (Całkiem możliwe jest napisanie własnej klasy kolekcji i iteratora, która umożliwia usuwanie elementów podczas pętli foreach.)

yoyo
źródło
6

Użycie Removelub RemoveAtna liście podczas iteracji po tej liście było celowo utrudnione, ponieważ prawie zawsze jest to niewłaściwe działanie . Możesz być w stanie sprawić, że zadziała z jakąś sprytną sztuczką, ale byłoby to bardzo wolne. Za każdym razem, Removegdy dzwonisz , musi przejrzeć całą listę, aby znaleźć element, który chcesz usunąć. Za każdym razem, RemoveAtgdy dzwonisz , musi przesuwać kolejne elementy o 1 pozycję w lewo. Jako takie, każde rozwiązanie wykorzystujące Removelub RemoveAtwymagałoby czasu kwadratowego, O (n²) .

Użyj, RemoveAlljeśli możesz. W przeciwnym razie następujący wzór będzie filtrował listę w miejscu w czasie liniowym, O (n) .

// Create a list to be filtered
IList<int> elements = new List<int>(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
// Filter the list
int kept = 0;
for (int i = 0; i < elements.Count; i++) {
    // Test whether this is an element that we want to keep.
    if (elements[i] % 3 > 0) {
        // Add it to the list of kept elements.
        elements[kept] = elements[i];
        kept++;
    }
}
// Unfortunately IList has no Resize method. So instead we
// remove the last element of the list until: elements.Count == kept.
while (kept < elements.Count) elements.RemoveAt(elements.Count-1);
bcmpinc
źródło
3

Chciałbym, żeby „wzór” był mniej więcej taki:

foreach( thing in thingpile )
{
    if( /* condition#1 */ )
    {
        foreach.markfordeleting( thing );
    }
    elseif( /* condition#2 */ )
    {
        foreach.markforkeeping( thing );
    }
} 
foreachcompleted
{
    // then the programmer's choices would be:

    // delete everything that was marked for deleting
    foreach.deletenow(thingpile); 

    // ...or... keep only things that were marked for keeping
    foreach.keepnow(thingpile);

    // ...or even... make a new list of the unmarked items
    others = foreach.unmarked(thingpile);   
}

To zrównuje kod z procesem zachodzącym w mózgu programisty.

warrens
źródło
1
Wystarczająco łatwe. Po prostu utwórz tablicę flagi boolowskiej (użyj typu 3-stanowego, np. Nullable<bool>Jeśli chcesz zezwolić na nieoznaczone), a następnie użyj go po foreach, aby usunąć / zachować elementy.
Dan Bechard,
3

Zakładając, że predykat jest logiczną właściwością elementu, że jeśli jest to prawda, element należy usunąć:

        int i = 0;
        while (i < list.Count())
        {
            if (list[i].predicate == true)
            {
                list.RemoveAt(i);
                continue;
            }
            i++;
        }
roeesha
źródło
Dałem tę opinię, ponieważ czasem bardziej efektywne może być poruszanie się po liście w kolejności (a nie w odwrotnej kolejności). Być może możesz przestać szukać pierwszego elementu, którego nie można usunąć, ponieważ lista jest uporządkowana. (Wyobraź sobie „przerwę”, w której i ++ znajduje się w tym przykładzie.
FrankKrumnow
3

Ponownie przypisałbym listę z zapytania LINQ, które odfiltrowało elementy, których nie chciałeś zachować.

list = list.Where(item => ...).ToList();

Jeśli lista nie jest bardzo duża, nie powinno to powodować znaczących problemów z wydajnością.

Martin Liversage
źródło
3

Najlepszym sposobem na usunięcie elementów z listy podczas iteracji jest użycie RemoveAll() . Ale główną troską napisaną przez ludzi jest to, że muszą robić pewne złożone rzeczy w pętli i / lub mieć złożone przypadki porównywania.

Rozwiązaniem jest nadal używać, RemoveAll()ale używaj tej notacji:

var list = new List<int>(Enumerable.Range(1, 10));
list.RemoveAll(item => 
{
    // Do some complex operations here
    // Or even some operations on the items
    SomeFunction(item);
    // In the end return true if the item is to be removed. False otherwise
    return item > 5;
});
Hüseyin Yağlı
źródło
2
foreach(var item in list.ToList())

{

if(item.Delete) list.Remove(item);

}

Po prostu utwórz całkowicie nową listę od pierwszego. Mówię „Łatwy” zamiast „Właściwy”, ponieważ tworzenie zupełnie nowej listy prawdopodobnie wiąże się z wyższą wydajnością w porównaniu z poprzednią metodą (nie zawracałem sobie głowy żadnym testem porównawczym.) Ogólnie wolę ten wzorzec, może być również przydatny w pokonywaniu Ograniczenia Linq-To-Entities.

for(i = list.Count()-1;i>=0;i--)

{

item=list[i];

if (item.Delete) list.Remove(item);

}

W ten sposób lista jest przewijana do tyłu za pomocą zwykłej starej pętli For. Wykonanie tego do przodu może być problematyczne, jeśli zmieni się rozmiar kolekcji, ale wstecz zawsze powinno być bezpieczne.

Lijo
źródło
1

Skopiuj listę, którą iterujesz. Następnie usuń z kopii i połącz oryginał. Cofanie się jest mylące i nie działa dobrze przy równoległym zapętlaniu.

var ids = new List<int> { 1, 2, 3, 4 };
var iterableIds = ids.ToList();

Parallel.ForEach(iterableIds, id =>
{
    ids.Remove(id);
});
Timothy Gonzalez
źródło
1

Zrobiłbym tak

using System.IO;
using System;
using System.Collections.Generic;

class Author
    {
        public string Firstname;
        public string Lastname;
        public int no;
    }

class Program
{
    private static bool isEven(int i) 
    { 
        return ((i % 2) == 0); 
    } 

    static void Main()
    {    
        var authorsList = new List<Author>()
        {
            new Author{ Firstname = "Bob", Lastname = "Smith", no = 2 },
            new Author{ Firstname = "Fred", Lastname = "Jones", no = 3 },
            new Author{ Firstname = "Brian", Lastname = "Brains", no = 4 },
            new Author{ Firstname = "Billy", Lastname = "TheKid", no = 1 }
        };

        authorsList.RemoveAll(item => isEven(item.no));

        foreach(var auth in authorsList)
        {
            Console.WriteLine(auth.Firstname + " " + auth.Lastname);
        }
    }
}

WYNIK

Fred Jones
Billy TheKid
Gambitier
źródło
0

Znalazłem się w podobnej sytuacji, w której musiałem usunąć każdy n- ty element danego elementu List<T>.

for (int i = 0, j = 0, n = 3; i < list.Count; i++)
{
    if ((j + 1) % n == 0) //Check current iteration is at the nth interval
    {
        list.RemoveAt(i);
        j++; //This extra addition is necessary. Without it j will wrap
             //down to zero, which will throw off our index.
    }
    j++; //This will always advance the j counter
}
Paul Nelson Baker
źródło
0

Koszt usunięcia elementu z listy jest proporcjonalny do liczby elementów następujących po elemencie do usunięcia. W przypadku, gdy pierwsza połowa elementów kwalifikuje się do usunięcia, każde podejście polegające na indywidualnym usunięciu elementów będzie musiało wykonać około N * N / 4 operacji kopiowania elementów, co może być bardzo kosztowne, jeśli lista jest duża .

Szybszym rozwiązaniem jest przejrzenie listy w celu znalezienia pierwszego elementu do usunięcia (jeśli istnieje), a następnie skopiowanie każdego elementu, który powinien zostać zachowany, do miejsca, do którego należy. Po wykonaniu tej czynności, jeśli R elementów powinno zostać zachowanych, pierwszymi R elementami na liście będą te R elementów, a wszystkie elementy wymagające usunięcia znajdą się na końcu. Jeśli te elementy zostaną usunięte w odwrotnej kolejności, system nie będzie musiał kopiować żadnego z nich, więc jeśli lista zawiera N elementów, z których R, w tym wszystkie pierwsze F, zostały zachowane, konieczne będzie skopiuj elementy RF i zmniejsz listę o jeden NR NR pozycji. Cały czas liniowy.

supercat
źródło
0

Moje podejście polega na tym, że najpierw tworzę listę indeksów, które należy usunąć. Następnie przeglądam indeksy i usuwam elementy z początkowej listy. Wygląda to tak:

var messageList = ...;
// Restrict your list to certain criteria
var customMessageList = messageList.FindAll(m => m.UserId == someId);

if (customMessageList != null && customMessageList.Count > 0)
{
    // Create list with positions in origin list
    List<int> positionList = new List<int>();
    foreach (var message in customMessageList)
    {
        var position = messageList.FindIndex(m => m.MessageId == message.MessageId);
        if (position != -1)
            positionList.Add(position);
    }
    // To be able to remove the items in the origin list, we do it backwards
    // so that the order of indices stays the same
    positionList = positionList.OrderByDescending(p => p).ToList();
    foreach (var position in positionList)
    {
        messageList.RemoveAt(position);
    }
}
testowanie
źródło
0

W C # jednym prostym sposobem jest zaznaczenie tych, które chcesz usunąć, a następnie utworzenie nowej listy, aby iterować ...

foreach(var item in list.ToList()){if(item.Delete) list.Remove(item);}  

lub jeszcze prostsze użycie linq ....

list.RemoveAll(p=>p.Delete);

ale warto zastanowić się, czy inne zadania lub wątki będą miały dostęp do tej samej listy w tym samym czasie, gdy jesteś zajęty usuwaniem, i może zamiast tego użyj ConcurrentList.

Andrzej Pasztet
źródło
0

Śledź elementy do usunięcia za pomocą właściwości i usuń je wszystkie po procesie.

using System.Linq;

List<MyProperty> _Group = new List<MyProperty>();
// ... add elements

bool cond = true;
foreach (MyProperty currObj in _Group)
{
    if (cond) 
    {
        // SET - element can be deleted
        currObj.REMOVE_ME = true;
    }
}
// RESET
_Group.RemoveAll(r => r.REMOVE_ME);
Roberto Mutti
źródło
0

Chciałem tylko dodać do tego moje 2 centy, na wypadek gdyby komuś to pomogło, miałem podobny problem, ale musiałem usunąć wiele elementów z listy tablic podczas iteracji. najwyżej oceniona odpowiedź zrobiła to dla mnie w przeważającej części, dopóki nie natknąłem się na błędy i nie zdałem sobie sprawy, że indeks był większy niż rozmiar listy tablic w niektórych przypadkach, ponieważ usuwano wiele elementów, ale indeks pętli nie zachowywał się ślad tego. Naprawiłem to prostym sprawdzeniem:

ArrayList place_holder = new ArrayList();
place_holder.Add("1");
place_holder.Add("2");
place_holder.Add("3");
place_holder.Add("4");

for(int i = place_holder.Count-1; i>= 0; i--){
    if(i>= place_holder.Count){
        i = place_holder.Count-1; 
    }

// some method that removes multiple elements here
}
Sasha1296
źródło
-4
myList.RemoveAt(i--);

simples;
południowy zachód
źródło
1
Co simples;tu robi?
Denny
6
jest delegatem .. zanotuje moją odpowiedź za każdym razem, gdy się uruchomi
SW
SW ROFL! Uwielbiam twój komentarz.
Erick Brown