Usuwanie elementów ze std :: set podczas iteracji

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.

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

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

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.

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

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.

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.

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”.

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