C++ wielokrotnego iteratora unieważnienia

Question

Próbuję dowiedzieć się, jak działają iteratory std::multimap, dlatego stworzyłem prosty przykład, który pokazuje istotę mojego problemu. W przypadku odkomentowania 1, oczekuję, że iterator wskaże pierwszy element z kluczem 1, ale w rzeczywistości wypisze wszystkie wartości związane z kluczem 0 (jak nic nie zostało usunięte), a czasami zawiesza się, prawdopodobnie dlatego, że iterator jest nieprawidłowy. Jednak w przypadku odkomentowania 2 wszystkie wartości klucza 1 są poprawnie usuwane.

Czy istnieje jakiś sposób sprawdzenia, jaki jest następny ważny iterator dla multimap po usunięciu? (np std::vector.erase(...) powraca jeden)

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

Przyczyną problemu

Po wywołaniu m.erase(0) w was przykład it punkty na elemencie z kluczem 0 - tak it zostało unieważnione. m.erase(1) działa, ponieważ gdy jest wywoływana po raz pierwszy, it nie wskazuje elementu z kluczem 1, więc nie ma na nie wpływu. W późniejszych iteracjach, żadne elementy z kluczem nie pozostały, więc nic nie jest usuwane i nie ma wpływu na iterator.

Rozwiązanie

multimap nie ma erase -method że zwraca następny ważny iterator. Jedną z możliwości jest wywołanie it = m.upper_bound(deleted_key); po usunięciu. Jest to jednak logarytmiczna, co może być zbyt wolne dla twojego scenariusza (erase(x) i upper_bound byłyby dwie operacje logarytmiczne).

Zakładając chcesz usunąć klucz Twój iterator jest obecnie wskazując, można zrobić coś takiego (w przeciwnym razie erase jest w porządku, oczywiście, nie testowane):

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

ta wykorzystuje działanie jeden liniowy cała reszta to stały czas. Jeśli twoja mapa jest bardzo duża, a masz tylko kilka przedmiotów z równymi klawiszami, prawdopodobnie będzie to szybsze. Jeśli jednak masz wiele pozycji z równymi klawiszami, wyszukiwanie końca interwału jest prawdopodobnie lepiej wykonywane przy użyciu upper_bound (O(log n) zamiast O(n) podczas wyszukiwania końca interwału).

Answer 2

pierwsza odpowiedź

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

Hum ....

Druga odpowiedź, re: edytowane pytanie

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

być bardzo ostrożnym kiedy mutujesz kontener (dowolny kontener) podczas iteracji, tak jak ty może unieważnić iterator, na którym polegasz.

Tzw „węzeł pojemniki na bazie” (list, set, map ...) są najbardziej wytrzymałe pojemnik WRT iterator unieważnienie: oni tylko unieważnia iteratory do usuniętych elementów (nie ma możliwości, aby te iteratory nie być unieważniony).

W takim przypadku należy sprawdzić, czy element, który ma zostać usunięty, nie jest w rzeczywistości *it.

Nie jestem do końca pewien, co próbujesz zrobić z pętlą.

Answer 3

po usunięciu iteratora staje się nieprawidłowy. zamiast tego zapamiętaj następny element, a następnie wymaż:

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

Patrząc na twój kod, myślę, że Twój ++ powoduje problem. Przypisujesz go do miejsca, które mogło zostać usunięte. przenieś go do końca, po instrukcji if i teście. tak:

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

(Edited)

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Oprócz unieważnienia it iterator powodu m.erase, które mogą wystąpić w zależności od zawartości multimap (objętych już w innym odpowiedź) zawsze jest problem, że dereference m.end() iterator po ostatniej iteracji pętli for po wykonaniu if((*it).second == 3) przy każdym uruchomieniu programu.

Proponuję uruchomić i debugować przy użyciu kompilacji debugowania. Jestem prawie pewien, że każda rozsądna implementacja biblioteki standardowej powinna zawierać asert, aby wykryć dereferencje w wersji end().

Answer 6

Niektórzy faceci powyżej już odpowiedzieli, że bawisz się ogniem.

Również myślę, że zapominają, że multimap zarządza mapę, więc są iteracji od najmniejszych kluczy do największych. Dlatego w pierwszym przypadku usuwasz klucze po wydrukowaniu niektórych z nich, ale w drugim przypadku usuwasz je tuż przed przejściem do nich.