Wie löscht man Elemente aus std::set innerhalb einer Schleife?

khalderon

Hi!
Ich will manche Elemente aus einer std::set löschen. Das bedeutet, dass der iterator nach dem Löschen invalidiert wird. Ist das die richtige Lösung des Problems:

set<etwas> sc;
/* ...	*/
for (set<etwas>::iterator i = sc.begin(), ie = sc.end(); i != ie; ++i)
	if ((*i)->irgendwas()) {
		set<etwas>::iterator temp = i;
                ++temp;
		sc.erase(i);
                i = temp;
	}

if((*i)->irgendwas())
{
    m.erase(i++);
}
else
{
    ++i;
}

pumuckl

oder du schreibst ein kleines Prädikat lokal zu der Funktion in der du die Elemente löschen willst und benutzt std::remove_if()

JimmydaMage

khalderon schrieb:

Hi!
Das bedeutet, dass der iterator nach dem Löschen invalidiert wird.

Du hast das ein bisschen falsch verstanden ;). Nicht der Wert des Iterators wird ungültig (geht auch gar nicht, da nur eine Kopie an erase() übergeben wird), sondern das Objekt, auf das der Iterator verweist. Das bedeutet, dass das Dereferenzieren dieses Iterators nach dem Löschen zu undefiniertem Verhalten führt. Du darfst den Iterator danach gerne Inkrementieren, um zum nächsten (gültigen) Element zu kommen .

set<etwas> sc;
/* ...    */
for (set<etwas>::iterator i = sc.begin(), ie = sc.end(); i != ie; ++i)
{
    if ((*i)->irgendwas()) 
        sc.erase(i);
}

Grüße

Martin

khalderon

Toll! Danke!

ist der code von JimmydaMage nicht falsch?

Wusste ichs doch, Visual C++ meldet bei dem Code von JimmydaMage:

map/set iterator not incrementable

JimmydaMage schrieb:

Du hast das ein bisschen falsch verstanden ;). Nicht der Wert des Iterators wird ungültig (geht auch gar nicht, da nur eine Kopie an erase() übergeben wird), sondern das Objekt, auf das der Iterator verweist.

Öhm. Nein!

http://www.velocityreviews.com/forums/t277880-setltgteraseiterator-question.html

khalderon

Ich benutze also das:

schöner schrieb:

if((*i)->irgendwas())
{
    m.erase(i++);
}
else
{
    ++i;
}

i++ macht eine Kopie des Iterators die zurückgegeben wird. Danach aber wird i intern inkrementiert und so zeigt er zu dem nächsten Element

Phoemuex

Wieso benutzt du nicht einfach den Rückgabewert von erase()?

Dinkumware Compleat Reference schrieb:

set::erase
iterator erase(iterator where);
The [...] member function removes the element of the controlled sequence pointed to by where. [...] It returns an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

Dann sieht das ganze ungefähr so aus:

set<etwas> sc;
//...
for (set<etwas>::iterator it = sc.begin(), ie = sc.end(); it != ie;)
    if ((*i)->irgendwas())
    {
        it = sc.erase(it); //it wird auf das nächste Element gesetzt
    }
    else
    {
        ++it; //it wird so auch auf das nächste Element gesetzt
    }

Felix

Phoemuex schrieb:

Wieso benutzt du nicht einfach den Rückgabewert von erase()?

Weil bei Set erase keinen Rückgabewert hat. Das ist laut Standard nicht vorgeschrieben.

http://www.cppreference.com/cppset/erase.html

khalderon

Ja, das habe ich auch erfahren davon:
http://www.sgi.com/tech/stl/set.html

pumuckl

Um meinen etwas knappen Beitrag zum Them Nutze die Standardbibliothek zu vervollständigen hier etwas Code:

set<etwas> sc;
/*...*/
struct testetwas {
  bool operator()(etwas const& e) {return e.irgendwas();}
};
std::remove_if(sc.begin(), sc.end(), testetwas());

Da es ein etwas unbekannteres Feature von C++ ist hier eine kurze Erklärung: testetwas ist eine lokale Klasse, die direkt vor dem Aufruf von remove_if definiert werden kann, also innerhalb der Funktion, in der sie benutzt wird.

khalderon

pumuckl schrieb:

Um meinen etwas knappen Beitrag zum Them Nutze die Standardbibliothek zu vervollständigen hier etwas Code:
set<etwas> sc;
/*...*/
struct testetwas {
  bool operator()(etwas const& e) {return e.irgendwas();}
};
std::remove_if(sc.begin(), sc.end(), testetwas());
Da es ein etwas unbekannteres Feature von C++ ist hier eine kurze Erklärung: testetwas ist eine lokale Klasse, die direkt vor dem Aufruf von remove_if definiert werden kann, also innerhalb der Funktion, in der sie benutzt wird.

Für mich ist das nicht unbekannt. Meinst du so:
sc.erase(remove_if(sc.begin(), sc.end(), predikat), sc.end());?
Bist du dir sicher, dass die remove_if Funktion mit set Iteratoren arbeiten kann?

pumuckl

khalderon schrieb:

Meinst du so:
sc.erase(remove_if(sc.begin(), sc.end(), predikat), sc.end());?

Natürlich. Unachtsamkeit meinerseits.

Bist du dir sicher, dass die remove_if Funktion mit set Iteratoren arbeiten kann?

Wäre schon blöd, wenn STL-Algorithmen nicht mit STL-Iteratoren arbeiten könnten oder? Dafür sind sie ja gemacht, würde mich also mehr als verwundern wenns das nicht tut.

khalderon

remove_if arbeitet nicht mit set iteratoren. Punkt.

LordJaxom

khalderon schrieb:

remove_if arbeitet nicht mit set iteratoren. Punkt.

Richtig, weil remove_if die Reihenfolge in der Sequenz ändert. Da im set die Reihenfolge festgelegt ist, klappt das nicht.

pumuckl

ok, wieder was gelernt. Andere Frage: muss es überhaupt ein set sein?

khalderon

Ja, weil set Duplikaten nicht erlaubt. Ich muss ständig Zeiger inserten. Im Fall wenn 2 oder mehrmals die gleiche Adresse inserted wird, passiert nix schlimmes (ein counter wird intern im set inkrementiert) und meine Anwendung funktioniert einfach problemlos.