Einträge aus STL Container löschen
-
pumuckl schrieb:
Also zu dem "mal nachfolgenden, mal vorherigen Element" - man kann immer einen nachfolgenden Iterator zurueckgeben, der nachfolgende des letzten Elements waeere dann end(). Meinen Vorpostern glaube ich entnehmen zu duerfen, dass das bei sequentiellen Containern (vector, deque &Co.) im Standard auch so gemacht wird, bei den anderen Containern ists nicht vorgeschrieben, aber die eine oder andere Bilbiothek (z.B. Dinkumware) machts trotzdem (ist aber dann nicht Standard => nicht portabel).
Das Problem dabei ist, daß mehrere Iteratoren auf das selbe Element zeigen könnten - erase() könnte aber nur bestenfalls den Iterator berichtigen, den du übergeben hast (und alle eventuell von dem erase() betroffenen Iteratoren zu finden dürfte wohl jede Laufzeit-Anforderung sprengen).
Folgendes sollte aber eigentlich fuer alle Container gehn:
MyContainer::iterator pos; /* ... */ mycont.erase(pos++);Nein, das fliegt dir bei vector<> (erase() macht alle Iteratoren ab der Löschposition ungültig) und deque<> (erase() könnte alle Iteratoren ungültig machen) vermutlich um die Ohren (oder liefert zumindest nicht das erwartete Ergebnis).
-
hm gut... dann sollte auch ich mich mal etwas doller mit den spezifikationen auseinandersetzen...
-
deswegen isses auch bei nichtassiozativen containern vorgeschrieben, das erase() nen wert zurueckliefern muss. Bei assiozativen (map, set) kann mans halt allein neu suchen ... bei nichtassoziativen hat man eher da eher weniger möglichkeiten.
in meinem schlauen buch(die C++ Standardbiblothek) steht das bei allen container bei jeglicher einfuege / loeschoperation alle iteratoren des containers ungueltig werden können.
Ciao ...
-
Aus der Hilfe von DevStudio 2005:
Da steht auch was mit dem Return-Value passiert.Für eine multimap gibt es die folgenden erase Funktionen.
iterator erase(
iterator _Where
);
iterator erase(
iterator _First,
iterator _Last
);
size_type erase(
const key_type& _Key
);Return Value:
For the first two member functions, a bidirectional iterator that designates the first element remaining beyond any elements removed, or a pointer to the end of the multimap if no such element exists.Note that this return type does not conform to the C++ standard.
For the third member function, returns the number of elements that have been removed from the multimap.
-
RHBaum schrieb:
...in meinem schlauen buch(die C++ Standardbiblothek) steht das bei allen container bei jeglicher einfuege / loeschoperation alle iteratoren des containers ungueltig werden ...
So hatte ich es auch in Erinnerung (und sogar zuerst geschrieben), dann aber nach genauerem Nachschlagen korrigiert.
Und mit
RHBaum schrieb:
...können. ...
kann man ja alles relativieren.
Aber mal in den Standard geschaut, ergibt:23.1.2 Associative Containers Pkt 8 schrieb:
...The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to te erased elements...
Gruß,
Simon2.
-
RHBaum schrieb:
in meinem schlauen buch(die C++ Standardbiblothek) steht das bei allen container bei jeglicher einfuege / loeschoperation alle iteratoren des containers ungueltig werden können.
Das ist definitiv falsch. Alle Node-basierenden Container (list,map,set) haben naturgemäß stabile Iteratoren und Referenzen, die im Allgemeinen nur ungültig werden, wenn das betreffende Element zerstört wird. Und selbst für vector werden bei erase tatsächlich nur die letzten n (=Anzahl der gelöschten Elemente) Referenzen ungültig - da erase niemals zu Reallokationen führt und das Speicherlayout feststeht; der dem entgegenstehende Text im Standard dürfte ein Relikt von c++98 sein: dort war noch nicht festgelegt, dass die Elemente von vector ein Array bilden. Damit bleibt hier nur noch deque übrig: bei diesem Container ist diese Festlegung tatsächlich sinnvoll, es gibt mehre Möglichkeiten - mit unterschiedlichen Stabilitätsgarantien - um diesen Container zu implementieren.
-
Also hab auch noch mal genauer nachgeschaut, naja fachbuecher sind manchmal seltsam literarische Werke
Im allgemeinen Teil ueber iteratoren und container steht, dass bei einfuege und loeschoperationen die Zeiger / iteratoren etc die noch auf dem container sind, ungueltig werden können
bei der genauren beschreibung der einzelnen container steht dann:
liste: besonderheit beim insert, push_irgendwas etc bleiben alle iteratoren gueltig und bleiben auch auf den gleichen elementen.
beim erase() werden nur die Zeiger / iteratoren ungueltig, die auf das geloeschte Element gezeigt haben.assoziative container: besonderheit beim insert, push_irgendwas etc bleiben alle iteratoren gueltig und bleiben auch auf den gleichen elementen.
beim erase() werden nur die Zeiger / iteratoren ungueltig, die auf das geloeschte Element gezeigt haben.Also der einzige der seine Iteratoren versaubeutelt ist der vector
Die schreibweisse (3.Auflage) laesst aber schon den verdacht zu, dass da nachtraeglich kleinigkeiten veraendert wurden ... naja die STL ist besitmmt auch irgendwie gewachsen.
Ciao ...
-
RHBaum schrieb:
Also der einzige der seine Iteratoren versaubeutelt ist der vector
Nicht ganz - die deque geht auch etwas rabiater mit ihren Iteratoren um.
vector: Einfüge-Operationen können ALLE Iteratoren vernichten (wenn der vector dabei seine Kapazität überschreitet - im Regelfall werden nur die Iteratoren hinter das Ziel ungültig), Lösch-Operationen nur Iteratoren auf oder hinter das Ziel.
deque: Einfüge- und Lösch-Operationen können alle Iteratoren ungültig machen (abgesehen von push_back(), push_front(), pop_back(), pop_front() - die sind "sicher") - idR betreffen sie nur den Bereich zwischen dem Ziel und dem näherliegenden Ende der deque.
-
Lösch-Operationen nur Iteratoren auf oder hinter das Ziel.
Beim vector referenziert der iterator doch die position, also den Index ?
wenn ich da das 1. element loesche, rutscht doch alles andere nach ? Damit sind die iteratoren ja vielleicht noch gueltig, aber zeigen nimmer auf die urspruenglichen elemente ?
und im schlimmsten fall ist es doch der STL Impl ned verboten, bei nem loeschen auf dem 1. element den kompletten vector neu zu bauen ?
Ciao ...
-
RHBaum schrieb:
Lösch-Operationen nur Iteratoren auf oder hinter das Ziel.
Beim vector referenziert der iterator doch die position, also den Index?
Der Iterator zeigt auf ein Objekt im vector, nciht auf einen Index.
wenn ich da das 1. element loesche, rutscht doch alles andere nach ?
Ja, dann werden saemtliche Elemente im vector eins nach vorn kopiert
Damit sind die iteratoren ja vielleicht noch gueltig, aber zeigen nimmer auf die urspruenglichen elemente ?
vielleicht, vielleicht auch nicht. Vielleicht greifst du ueber einen solchen Iterator zu und erhaelst einen Blumestrauss, eine Handvoll Spinnen oder die Monopoly-Karte "gehen sie ins Gefaengnis" - Zugriff ueber die Iteratoren ist nach dem Loeschen undefiniert.
und im schlimmsten fall ist es doch der STL Impl ned verboten, bei nem loeschen auf dem 1. element den kompletten vector neu zu bauen ?
Wenn, wie CStoll schreibt die Operatoren vor dem geloeschten noch gueltig sind, kann der vector sich nicht eben komplett neu bauen..
-
RHBaum schrieb:
wenn ich da das 1. element loesche, rutscht doch alles andere nach ? Damit sind die iteratoren ja vielleicht noch gueltig, aber zeigen nimmer auf die urspruenglichen elemente ?
Wenn der Standard sagt, eine Operation invalidiert den Iterator, heißt das nicht unbedingt, daß dieser auf NULL oder ähnliches umgebogen wird - das heißt vor allem, daß du nicht mehr garantieren kannst, was sich hinter dem Iterator für Daten verbergen.
Im Fall des vector sieht es idR wirklich so aus, daß die Iteratoren nach dem Löschen noch auf die selbe Speicherposition verweisen - aber eben nicht mehr auf die selben Nutzdaten, da die Elemente zusammengeschoben wurden, um die Lücke zu füllen. Und wenn du oft genug das erste Element löschst, zeigen deine Iteratoren sogar auf den Reservebereich, den der vector sich für schlechte Zeiten aufgehoben hat.