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.
++it
powinno 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.Odpowiedzi:
Jest to zależne od implementacji:
Standard 23.1.2.8:
Może mógłbyś spróbować - to jest zgodne ze standardem:
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 (lubset::end
, jeśli ostatni element został usunięty). Tak więc styl C ++ 11 to:źródło
deque
MSVC2013. Albo ich implementacja jest błędna, albo istnieje jeszcze jeden wymóg, który uniemożliwia todeque
. 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.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:
źródło
while
pętli. iefor ( ; it != numbers.end(); )
jest lepiej widoczny zwhile (it != numbers.end())
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.
źródło
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). ;)std::set::erase
na 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 ...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 ():
Wynik:
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:
Wynik:
Oto jeden ze sposobów rozwiązania tego problemu:
źródło
do not trust an old remembered dq.end() value, always compare to a new call to dq.end()
.C ++ 20 będzie miał „jednolite wymazywanie kontenerów” i będziesz mógł pisać:
I że będzie pracować dla
vector
,set
,deque
, itd. Patrz cppReference aby uzyskać więcej informacji.źródło
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.
źródło
Set<T>::erase
version nie zwraca iteratora.gcc 4.8
withc++1y
mają błąd w usuwaniu.it = collection.erase(it);
ma działać, ale może być bezpieczniejsze w użyciucollection.erase(it++);
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:
„
it
” to iterator, który „remove_if
” zwraca, trzeci argument to funkcja lambda, która jest wykonywana na każdym elemencie kontenera. Ponieważ kontener zawieraBullet::Ptr
, funkcja lambda musi pobrać ten typ (lub odwołanie do tego typu) przekazany jako argument.'
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”.źródło
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.
źródło