Czy potrafisz usunąć elementy ze standardowej listy podczas iteracji?

239

Mam kod, który wygląda następująco:

for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
    bool isActive = (*i)->update();
    //if (!isActive) 
    //  items.remove(*i); 
    //else
       other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);

Chciałbym usunąć nieaktywne elementy natychmiast po ich aktualizacji, aby uniknąć ponownego przeglądania listy. Ale jeśli dodam skomentowane wiersze, pojawia się błąd, gdy dochodzę do i++: „Nie można zwiększać iteratora listy”. Wypróbowałem kilka alternatyw, które nie zwiększały się w wyciągu for, ale nie mogłem nic zrobić.

Jaki jest najlepszy sposób na usunięcie przedmiotów, gdy idziesz na std :: list?

AShelly
źródło
Nie widziałem żadnego rozwiązania opartego na iteracji wstecznej. Zamieściłem jeden taki .
sancho.s ReinstateMonicaCellio 13.03.19

Odpowiedzi:

286

Musisz najpierw zwiększyć iterator (z i ++), a następnie usunąć poprzedni element (np. Używając zwróconej wartości z i ++). Możesz zmienić kod na pętlę while w następujący sposób:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // alternatively, i = items.erase(i);
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}
Michael Kristofik
źródło
7
W rzeczywistości nie ma gwarancji, że zadziała. Dzięki „erase (i ++);” wiemy tylko, że wstępnie zwiększona wartość jest przekazywana do erase (), a i jest zwiększane przed średnikiem, niekoniecznie przed wywołaniem erase (). „iterator prev = i ++; erase (prev);” z pewnością zadziała, podobnie jak wartość zwracana
James Curran
58
Nie, James, i jest zwiększany przed wywołaniem wymazywania, a poprzednia wartość jest przekazywana do funkcji. Argumenty funkcji muszą zostać w pełni ocenione przed wywołaniem funkcji.
Brian Neal
28
@ James Curran: To nieprawda. WSZYSTKIE argumenty są w pełni oceniane przed wywołaniem funkcji.
Martin York
9
Martin York ma rację. Wszystkie argumenty wywołania funkcji są w pełni przetwarzane przed wywołaniem funkcji, bez wyjątków. Tak po prostu działa funkcja. I to nie ma nic wspólnego ze swoim foo.b (i ++) C (i ++) Przykład (który nie jest zdefiniowany w każdym przypadku).
jalf
75
Alternatywne użycie i = items.erase(i)jest bezpieczniejsze, ponieważ jest równoważne z listą, ale nadal będzie działać, jeśli ktoś zmieni kontener na wektor. W przypadku wektora funkcja erase () przesuwa wszystko w lewo, aby wypełnić dziurę. Jeśli spróbujesz usunąć ostatni element z kodem, który przyrosty iterator po skasowaniu przemieszcza koniec do lewej, a porusza iteracyjnej do prawy-- minione końca. A potem upaść.
Eric Seppanen
133

Chcesz robić:

i= items.erase(i);

To poprawnie zaktualizuje iterator, aby wskazywał lokalizację po usuniętym iteratorze.

MSN
źródło
80
Ostrzegamy, że nie można po prostu upuścić tego kodu w pętli for. W przeciwnym razie pominiesz element za każdym razem, gdy go usuniesz.
Michael Kristofik
2
czy on nie może zrobić; za każdym razem podążając za jego fragmentem kodu, aby uniknąć pomijania?
entuzjastycznie
1
@enthusiasticgeek, co się stanie, jeśli i==items.begin()?
MSN
1
@enthusiasticgeek, w tym momencie powinieneś po prostu zrobić i= items.erase(i);. Jest to forma kanoniczna i już dba o wszystkie te szczegóły.
MSN
6
Michael wskazuje na wielką „gotcha”, musiałem sobie poradzić z tym samym. Najłatwiejszym sposobem na uniknięcie tego, co znalazłem, było po prostu rozkładanie pętli for () na chwilę () i uważanie na zwiększanie
Anne Quinn
22

Musisz wykonać kombinację odpowiedzi Kristo i MSN:

// Note: Using the pre-increment operator is preferred for iterators because
//       there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
//       along the way you can safely save end once; otherwise get it at the
//       top of each loop.

std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end  = items.end();

while (iter != end)
{
    item * pItem = *iter;

    if (pItem->update() == true)
    {
        other_code_involving(pItem);
        ++iter;
    }
    else
    {
        // BTW, who is deleting pItem, a.k.a. (*iter)?
        iter = items.erase(iter);
    }
}

Oczywiście najbardziej wydajną i savy SuperCool® STL jest coś takiego:

// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
    if (m_needsUpdates == true)
    {
        m_needsUpdates = other_code_involving(this);
    }

    return (m_needsUpdates);
}

// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));
Mikrofon
źródło
Rozważyłem twoją metodę SuperCool, wahałem się, czy wywołanie metody remove_if nie wyjaśnia, że ​​celem jest przetworzenie elementów, a nie usunięcie ich z listy aktywnych. (Elementy nie są usuwane, ponieważ stają się nieaktywne, a nie zbędne)
AShelly
Przypuszczam, że masz rację. Z jednej strony jestem skłonny zasugerować zmianę nazwy „update” w celu usunięcia niejasności, ale prawda jest taka, że ​​ten kod jest fantazyjny w stosunku do funktorów, ale nie jest on również niejasny.
Mike
Uczciwy komentarz, albo napraw pętlę while, aby użyć końca lub usuń nieużywaną definicję.
Mike
10

Użyj algorytmu std :: remove_if.

Edycja: Praca ze zbiorami powinna wyglądać tak: 1. przygotować kolekcję. 2. zbieranie procesów.

Życie będzie łatwiejsze, jeśli nie pomieszacie tych kroków.

  1. std :: remove_if. lub list :: remove_if (jeśli wiesz, że pracujesz z listą, a nie z TCollection)
  2. std :: for_each
Mykoła Golubiew
źródło
2
std :: list ma funkcję członka remove_if, która jest bardziej wydajna niż algorytm remove_if (i nie wymaga idiomu „remove-erase”).
Brian Neal
5

Oto przykład wykorzystujący forpętlę, która iteruje listę i zwiększa lub ponownie waliduje iterator w przypadku usunięcia elementu podczas przechodzenia przez listę.

for(auto i = items.begin(); i != items.end();)
{
    if(bool isActive = (*i)->update())
    {
        other_code_involving(*i);
        ++i;

    }
    else
    {
        i = items.erase(i);

    }

}

items.remove_if(CheckItemNotActive);
David Cormack
źródło
4

Alternatywa dla wersji pętli do odpowiedzi Kristo.

Tracisz trochę wydajności, cofasz się, a potem ponownie do przodu podczas usuwania, ale w zamian za dodatkowy przyrost iteratora możesz zadeklarować iterator w zakresie pętli, a kod będzie wyglądał na nieco czystszy. To, co wybrać, zależy od priorytetów chwili.

Odpowiedź była całkowicie spóźniona, wiem ...

typedef std::list<item*>::iterator item_iterator;

for(item_iterator i = items.begin(); i != items.end(); ++i)
{
    bool isActive = (*i)->update();

    if (!isActive)
    {
        items.erase(i--); 
    }
    else
    {
        other_code_involving(*i);
    }
}
Rafael Gago
źródło
1
Tego też użyłem. Ale nie jestem pewien, czy jest gwarantowane, że element do usunięcia jest pierwszym elementem w kontenerze. Myślę, że dla mnie to działa, ale nie jestem pewien, czy jest przenośny na różnych platformach.
trololo
Nie zrobiłem „-1”, jednak iterator listy nie może się zmniejszyć? Przynajmniej mam potwierdzenie z Visual Studio 2008.
milesma
Tak długo, jak połączona lista jest implementowana jako okrągła podwójnie połączona lista mająca węzeł head / stub (używany jako end () rbegin (), a gdy pusty jest również używany jako begin () i rend ()), to będzie działać. Nie pamiętam, na której platformie tego używałem, ale działało to również dla mnie, ponieważ wyżej wymieniona implementacja jest najczęstszą implementacją dla listy std ::. Ale w każdym razie jest prawie pewne, że wykorzystywało to pewne nieokreślone (według standardu C ++) zachowanie, więc lepiej go nie używaj.
Rafael Gago
re: sposób potrzebuje . Niektóre implementacje kolekcji zapewniają, co powoduje asercję. iterator cannot be decrementederaserandom access iteratorforward only iterator
Jesse Chisholm
@Jesse Chisholm pytanie dotyczyło std :: list, a nie arbitralnego kontenera. std :: list zapewnia kasowanie i dwukierunkowe iteratory.
Rafael Gago
4

Mam podsumowanie, oto trzy metody z przykładem:

1. za pomocą whilepętli

list<int> lst{4, 1, 2, 3, 5};

auto it = lst.begin();
while (it != lst.end()){
    if((*it % 2) == 1){
        it = lst.erase(it);// erase and go to next
    } else{
        ++it;  // go to next
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

2. przy użyciu remove_iffunkcji członka na liście:

list<int> lst{4, 1, 2, 3, 5};

lst.remove_if([](int a){return a % 2 == 1;});

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

3. użycie std::remove_iffunkcji funtion w połączeniu z erasefunkcją członka:

list<int> lst{4, 1, 2, 3, 5};

lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
    return a % 2 == 1;
}), lst.end());

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

4. używając forpętli, należy pamiętać o aktualizacji iteratora:

list<int> lst{4, 1, 2, 3, 5};

for(auto it = lst.begin(); it != lst.end();++it){
    if ((*it % 2) == 1){
        it = lst.erase(it);  erase and go to next(erase will return the next iterator)
        --it;  // as it will be add again in for, so we go back one step
    }
}

for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2 
Jayhello
źródło
2

Usunięcie unieważnia tylko iteratory wskazujące na usunięte elementy.

Tak więc w tym przypadku po usunięciu * i, i jest unieważnione i nie można go zwiększać.

Co możesz zrobić, to najpierw zapisać iterator elementu, który ma zostać usunięty, następnie zwiększyć iterator, a następnie usunąć zapisany.

anand
źródło
2
Korzystanie z przyrostu jest znacznie bardziej eleganckie.
Brian Neal
2

Jeśli myślisz o std::listpodobnej kolejce, możesz usunąć kolejkę z kolejki i umieścić w kolejce wszystkie elementy, które chcesz zachować, ale tylko kolejkę (i nie kolejkę) z pozycji, którą chcesz usunąć. Oto przykład, w którym chcę usunąć 5 z listy zawierającej liczby 1-10 ...

std::list<int> myList;

int size = myList.size(); // The size needs to be saved to iterate through the whole thing

for (int i = 0; i < size; ++i)
{
    int val = myList.back()
    myList.pop_back() // dequeue
    if (val != 5)
    {
         myList.push_front(val) // enqueue if not 5
    }
}

myList będzie teraz mieć tylko numery 1-4 i 6-10.

Alex Bagg
źródło
Ciekawe podejście, ale obawiam się, że może być powolne.
sg7
2

Iteracja do tyłu pozwala uniknąć efektu wymazania elementu na pozostałych elementach do przejścia:

typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
    --it;
    bool remove = <determine whether to remove>
    if ( remove ) {
        items.erase( it );
    }
}

PS: zobaczyć to , na przykład, w odniesieniu do tyłu iteracji.

PS2: Nie przetestowałem dokładnie, czy dobrze radzi sobie z usuwaniem elementów na końcach.

sancho.s ReinstateMonicaCellio
źródło
Re: avoids the effect of erasing an element on the remaining elementsdla listy, prawdopodobnie tak. Dla wektora może nie. Nie jest to gwarantowane w przypadku dowolnych kolekcji. Na przykład mapa może podjąć decyzję o ponownym zrównoważeniu.
Jesse Chisholm
1

Możesz pisać

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive) {
        i = items.erase(i); 
    } else {
        other_code_involving(*i);
        i++;
    }
}

Możesz napisać równoważny kod std::list::remove_if, który jest mniej szczegółowy i bardziej wyraźny

items.remove_if([] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
});

std::vector::erase std::remove_ifIdiom powinny być stosowane, gdy przedmioty jest wektorem zamiast listy zachować compexity w O (n) - lub w przypadku pisania kodu rodzajowe i pozycji może być pojemnik bez skutecznego sposobu kasowania pojedynczych elementów (jak wektor)

items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
    bool isActive = (*i)->update();
    if (!isActive) 
        return true;

    other_code_involving(*i);
    return false;
}));
J. Kalz
źródło
-4

Myślę, że masz tam błąd, koduję w ten sposób:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
             itAudioChannel != audioChannels.end(); )
{
    CAudioChannel *audioChannel = *itAudioChannel;
    std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
    itAudioChannel++;

    if (audioChannel->destroyMe)
    {
        audioChannels.erase(itCurrentAudioChannel);
        delete audioChannel;
        continue;
    }
    audioChannel->Mix(outBuffer, numSamples);
}
Marcin Skoczylas
źródło
Domyślam się, że zostało to zanegowane dla preferencji stylu, ponieważ wydaje się funkcjonalne. Tak, jasne, (1) używa dodatkowego iteratora, (2) przyrost iteratora jest w dziwnym miejscu dla pętli bez uzasadnionego powodu, aby go tam umieścić, (3) działa kanał po decyzji o usunięciu wcześniej jak w OP. Ale to nie jest zła odpowiedź.
Jesse Chisholm