Usuwanie elementów ze std :: set podczas iteracji

147

Muszę przejść przez zestaw i usunąć elementy, które spełniają predefiniowane kryteria.

Oto kod testowy, który napisałem:

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

Na początku myślałem, że wymazanie elementu ze zbioru podczas iteracji przez niego unieważniłoby iterator, a przyrost w pętli for miałby niezdefiniowane zachowanie. Mimo to wykonałem ten kod testowy i wszystko poszło dobrze i nie potrafię wyjaśnić dlaczego.

Moje pytanie: czy to jest zdefiniowane zachowanie dla zestawów standardowych, czy jest to specyficzne dla tej implementacji? Nawiasem mówiąc, używam gcc 4.3.3 na Ubuntu 10.04 (wersja 32-bitowa).

Dzięki!

Proponowane rozwiązanie:

Czy to właściwy sposób iteracji i usuwania elementów z zestawu?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

Edycja: PREFEROWANE ROZWIĄZANIE

Znalazłem rozwiązanie, które wydaje mi się bardziej eleganckie, mimo że robi dokładnie to samo.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

Jeśli w środku while jest kilka warunków testowych, każdy z nich musi zwiększać iterator. Ten kod podoba mi się bardziej, ponieważ iterator jest zwiększany tylko w jednym miejscu , dzięki czemu kod jest mniej podatny na błędy i bardziej czytelny.

pedromanoel
źródło
1
Zapytany i odpowiedział: stackoverflow.com/questions/263945/…
Martin York
3
Właściwie przeczytałem to pytanie (i inne), zanim zadałem moje, ale ponieważ były one powiązane z innymi kontenerami STL i ponieważ mój pierwszy test najwyraźniej zadziałał, pomyślałem, że jest między nimi jakaś różnica. Dopiero po odpowiedzi Matta pomyślałem o użyciu valgrind. Mimo to wolę moje NOWE rozwiązanie od innych, ponieważ zmniejsza to ryzyko błędów, zwiększając iterator tylko w jednym miejscu. Dziękuję wszystkim za pomoc!
pedromanoel
1
@pedromanoel ++itpowinno być nieco bardziej wydajne niż it++dlatego, że nie wymaga użycia niewidocznej tymczasowej kopii iteratora. Wersja Kornela, choć dłużej zapewnia, że ​​niefiltrowane elementy są iterowane najbardziej efektywnie.
Alnitak
@Alnitak Nie myślałem o tym, ale myślę, że różnica w wydajności nie byłaby tak duża. Kopia jest również tworzona w jego wersji, ale tylko dla pasujących elementów. Zatem stopień optymalizacji jest całkowicie zależny od struktury zbioru. Od dłuższego czasu wstępnie optymalizowałem kod, szkodząc w tym procesie czytelności i szybkości kodowania ... Więc wykonałem kilka testów, zanim użyłem innego sposobu.
pedromanoel

Odpowiedzi:

178

Jest to zależne od implementacji:

Standard 23.1.2.8:

Elementy wstawiające nie wpływają na ważność iteratorów i odniesień do kontenera, a elementy usuwające unieważniają tylko iteratory i odniesienia do usuniętych elementów.

Może mógłbyś spróbować - to jest zgodne ze standardem:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Zauważ, że ++ jest postfiksem, dlatego przekazuje starą pozycję do usunięcia, ale najpierw przeskakuje do nowszej z powodu operatora.

Aktualizacja 2015.10.27: C ++ 11 rozwiązał usterkę. iterator erase (const_iterator position);zwraca iterator do elementu, który następuje po ostatnim usuniętym elemencie (lub set::end, jeśli ostatni element został usunięty). Tak więc styl C ++ 11 to:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}
Kornel Kisielewicz
źródło
2
To nie działa w przypadku deque MSVC2013. Albo ich implementacja jest błędna, albo istnieje jeszcze jeden wymóg, który uniemożliwia to deque. Specyfikacja STL jest tak zawiła, że ​​nie można oczekiwać, że wszystkie implementacje będą jej przestrzegać, nie mówiąc już o zapamiętaniu jej przez zwykłego programistę. STL to potwór, którego nie da się oswoić, a ponieważ nie ma unikalnej implementacji (a zestawy testowe, jeśli takie istnieją, najwyraźniej nie obejmują tak oczywistych przypadków, jak usuwanie elementów w pętli), sprawia, że ​​STL jest błyszczącą, kruchą zabawką, która może się równać huk, kiedy patrzysz na to z boku.
kuroi neko
@MatthieuM. Działa w C ++ 11. W C ++ 17 pobiera teraz iterator (const_iterator w C ++ 11).
tartaruga_casco_mole
19

Jeśli uruchomisz swój program przez valgrind, zobaczysz kilka błędów odczytu. Innymi słowy, tak, iteratory są unieważniane, ale w swoim przykładzie masz szczęście (lub naprawdę pecha, ponieważ nie widzisz negatywnych skutków niezdefiniowanego zachowania). Jednym z rozwiązań jest utworzenie tymczasowego iteratora, zwiększenie temperatury, usunięcie iteratora docelowego, a następnie ustawienie celu na temp. Na przykład ponownie napisz pętlę w następujący sposób:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 
Matt
źródło
Jeśli tylko warunek ma znaczenie i nie wymaga inicjalizacji w zakresie ani po operacji, lepiej użyć whilepętli. ie for ( ; it != numbers.end(); )jest lepiej widoczny zwhile (it != numbers.end())
iammilind
7

Nie rozumiesz, co oznacza „niezdefiniowane zachowanie”. Niezdefiniowane zachowanie nie oznacza „jeśli to zrobisz, program ulegnie awarii lub spowoduje nieoczekiwane rezultaty”. To znaczy „jeśli to zrobisz, Twój program może zawiesić lub spowodować nieoczekiwane rezultaty” lub zrobić cokolwiek innego, w zależności od kompilatora, systemu operacyjnego, fazy księżyca itp.

Jeśli coś jest wykonywane bez awarii i zachowuje się tak, jak tego oczekujesz, tak nie jest dowód, że nie jest to niezdefiniowane zachowanie. Wszystko to dowodzi, że jego zachowanie było takie, jak obserwowane dla tego konkretnego uruchomienia po kompilacji z tym konkretnym kompilatorem w tym konkretnym systemie operacyjnym.

Wymazanie elementu z zestawu unieważnia iterator do wymazanego elementu. Używanie unieważnionego iteratora jest niezdefiniowanym zachowaniem. Tak się złożyło, że zaobserwowane zachowanie było tym, co zamierzałeś w tym konkretnym przypadku; nie oznacza to, że kod jest poprawny.

Tyler McHenry
źródło
Och, doskonale zdaję sobie sprawę, że niezdefiniowane zachowanie może również oznaczać „To działa na mnie, ale nie na wszystkich”. Dlatego zadałem to pytanie, ponieważ nie wiedziałem, czy to zachowanie jest poprawne, czy nie. Gdyby tak było, po prostu bym tak wyszedł. Zatem użycie pętli while rozwiązałoby mój problem? Zmieniłem pytanie, podając proponowane przeze mnie rozwiązanie. Proszę sprawdź to.
pedromanoel
Na mnie też działa. Ale kiedy zmieniam warunek na if (n > 2 && n < 7 )to otrzymuję 0 1 2 4 7 8 9. - Konkretny wynik tutaj prawdopodobnie zależy bardziej od szczegółów implementacji metody kasowania i ustawionych iteratorów, a nie od fazy księżyca (nie tej powinien zawsze polegać na szczegółach implementacji). ;)
UncleBens
1
STL dodaje wiele nowych znaczeń do „niezdefiniowanego zachowania”. Na przykład „Microsoft pomyślał mądrze, aby ulepszyć specyfikację, zezwalając std::set::erasena zwrócenie iteratora, aby Twój kod MSVC wzrósł z hukiem po skompilowaniu przez gcc” lub „Microsoft przeprowadza kontrole powiązane, std::bitset::operator[]aby dokładnie zoptymalizowany algorytm zestawu bitów zwolnił indeksuj po skompilowaniu z MSVC ”. STL nie ma unikalnej implementacji, a jego specyfikacja to wykładniczo rosnący, rozdęty bałagan, więc nic dziwnego, że usuwanie elementów z wewnątrz pętli wymaga doświadczenia starszego programisty ...
kuroi neko
2

Aby ostrzec, że w przypadku kontenera deque, wszystkie rozwiązania, które sprawdzają równość iteratora deque z liczbami.end () prawdopodobnie zawiodą na gcc 4.8.4. Mianowicie, wymazanie elementu deque generalnie unieważnia wskaźnik do numbers.end ():

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Wynik:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

Zauważ, że chociaż transformacja deque jest poprawna w tym konkretnym przypadku, wskaźnik końcowy został po drodze unieważniony. Przy deque innego rozmiaru błąd jest bardziej widoczny:

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Wynik:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Oto jeden ze sposobów rozwiązania tego problemu:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}
McKryak
źródło
Kluczowa istota do not trust an old remembered dq.end() value, always compare to a new call to dq.end().
Jesse Chisholm
2

C ++ 20 będzie miał „jednolite wymazywanie kontenerów” i będziesz mógł pisać:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

I że będzie pracować dla vector, set, deque, itd. Patrz cppReference aby uzyskać więcej informacji.

Marshall Clow
źródło
1

To zachowanie jest specyficzne dla implementacji. Aby zagwarantować poprawność iteratora, należy użyć "it = numbers.erase (it);" instrukcja, jeśli chcesz usunąć element i po prostu wprowadzić iterator w innym przypadku.

Witalij Bogdanow
źródło
1
Set<T>::eraseversion nie zwraca iteratora.
Arkaitz Jimenez
4
Właściwie tak, ale tylko w przypadku implementacji MSVC. Jest to więc prawdziwa odpowiedź specyficzna dla implementacji. :)
Eugene
1
@Eugene Robi to dla wszystkich implementacji z C ++ 11
mastov
Niektóre implementacje gcc 4.8with c++1ymają błąd w usuwaniu. it = collection.erase(it);ma działać, ale może być bezpieczniejsze w użyciucollection.erase(it++);
Jesse Chisholm
1

Myślę, że używając metody STL ”remove_if „z” może pomóc w zapobieganiu dziwnym problemom podczas próby usunięcia obiektu opakowanego przez iterator.

To rozwiązanie może być mniej wydajne.

Powiedzmy, że mamy jakiś kontener, na przykład wektor lub listę o nazwie m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

it” to iterator, który „ remove_if” zwraca, trzeci argument to funkcja lambda, która jest wykonywana na każdym elemencie kontenera. Ponieważ kontener zawiera Bullet::Ptr, funkcja lambda musi pobrać ten typ (lub odwołanie do tego typu) przekazany jako argument.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

' remove_if' usuwa kontener, w którym funkcja lambda zwróciła wartość true, i przesuwa tę zawartość na początek kontenera. Znak „ it” wskazuje na niezdefiniowany obiekt, który można uznać za śmieci. Obiekty od „it” do m_bullets.end () mogą zostać usunięte, ponieważ zajmują pamięć, ale zawierają śmieci, dlatego w tym zakresie wywoływana jest metoda „erase”.

John Behm
źródło
0

Natknąłem się na ten sam stary problem i stwierdziłem, że poniższy kod jest bardziej zrozumiały, co jest w pewnym sensie zgodne z powyższymi rozwiązaniami.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}
Anurag
źródło
Działa to tylko wtedy, gdy zawsze usuniesz każdy element. OP polega na selektywnym usuwaniu elementów i nadal posiadaniu prawidłowych iteratorów.
Jesse Chisholm