Einträge aus STL Container löschen

[BlackPepper]

Hallo,

wenn ich einen Container mit einer entsprechenden Operation zur Verfügung stellen würde, würde ich nach dem Löschen auf das darauf folgende Element zeigen, beziehungswese auf das vorherige wenn ich schon am Ende gewesen wäre. Nur wenn ich das einzige Element gelöscht hätte, hätte ich auf NULL verwiesen. Wenn das dem Anwender nicht passt, kann er immer noch von vorne beginnen. Etwas ähnliches hab ich auch bei den STL Containern erwartet und gemerkt, das es nicht so ist. Nur ist nichts dokumentiert. Zumindest habs ich nicht gefunden.

Grüße M. Incani

Simon2 schrieb:

BlackPepper schrieb:

...
ich würde gerne wissen wohin ein Iterator zeigt, wenn ich das Element aus dem STL Container lösche, auf das der Iterator zeigt. ...

Ganz einfach: Undefiniert !

Löschen macht alle iteratoren auf gelöschte Elemente ungültig.

Gruß,

Simon2.

[LordJaxom]

BlackPepper schrieb:

wenn ich einen Container mit einer entsprechenden Operation zur Verfügung stellen würde, würde ich nach dem Löschen auf das darauf folgende Element zeigen, beziehungswese auf das vorherige wenn ich schon am Ende gewesen wäre. Nur wenn ich das einzige Element gelöscht hätte, hätte ich auf NULL verwiesen. Wenn das dem Anwender nicht passt, kann er immer noch von vorne beginnen. Etwas ähnliches hab ich auch bei den STL Containern erwartet und gemerkt, das es nicht so ist. Nur ist nichts dokumentiert. Zumindest habs ich nicht gefunden.

(ad Ändern) By Design werden Iteratoren eigentlich immer als Wert übergeben. Damit haben die entsprechenden Funktionen garnicht die Möglichkeit ihn zu ändern.

(ad Doku) Hast Du Dir schonmal die Dokumentation zu erase angeschaut? Bzw. was diese Funktion zurückliefert?

[Simon2]

Hi,

also ich habe nachgesehen in Kuhlins/Schrader: Die C++-Standardbibliothek (allerdings nur die 2 Auflage).

Wieso das im Standard so definiert, weiß ich jetzt auch nicht (bei vectoren ist mir das klar, aber hier (wo es nur die gelöschten Elemente betrifft) nicht).

Gruß,

Simon2.

[BlackPepper]

Ja, hab ich. Dort steht nur, was erase mit dem Element im container macht. Zumindest in der Doku die ich benutzt hab (http://www.cppreference.com, Ein Buch über die STL von Addison-Wesley). Ansonsten laß mich wissen wo Du nachschaust.

Grüße M. Incani

LordJaxom schrieb:

(ad Ändern) By Design werden Iteratoren eigentlich immer als Wert übergeben. Damit haben die entsprechenden Funktionen garnicht die Möglichkeit ihn zu ändern.

(ad Doku) Hast Du Dir schonmal die Dokumentation zu erase angeschaut? Bzw. was diese Funktion zurückliefert?

[BlackPepper]

Hallo,

leider hab ich das Buch nicht. Was steht denn dort?

Grüße M. Incani

Simon2 schrieb:

Hi,

also ich habe nachgesehen in Kuhlins/Schrader: Die C++-Standardbibliothek (allerdings nur die 2 Auflage).

Wieso das im Standard so definiert, weiß ich jetzt auch nicht (bei vectoren ist mir das klar, aber hier (wo es nur die gelöschten Elemente betrifft) nicht).

Gruß,

Simon2.

[Simon2]

LordJaxom schrieb:

...
(ad Doku) Hast Du Dir schonmal die Dokumentation zu erase angeschaut? Bzw. was diese Funktion zurückliefert?

void multimap::erase( iterator pos );
size_type multimap::erase( const key_type& key );

helfen da nicht wirklich.

Gruß,

Simon2.

[Simon2]

BlackPepper schrieb:

Hallo,
leider hab ich das Buch nicht. Was steht denn dort?
...

Naja. insgesamt hat es 400 Seiten und das Kapitel über Container immerhin auch fast 60. Du verzeihst mir, wenn ich das jetzt nicht abtippe, hoffe ich ...

Aber das Entscheidende ist:

Seite 105 (Kap. 7.2) schrieb:

void erase(iterator position);

[...]
Der Wert des Iterators ist nach dem Aufruf von erase nicht mehr definiert, weil der Element auf das er verwies, gelöscht wurde. erase(end()) hat keinen Effekt.
[...]
Bei allen drei Versionen der Elementfunktion erase verlieren nur Referenzen, Zeiger und Iteratoren auf gelöschte Containerelemente ihre Gültigkeit. Im Gegensatz zu den entsprechenden Funktionen sequentieller Container ist der Rückgabetyp für die beiden letzten Elementfunktionen void statt iterator [...], weil so die unter Umständen recht aufwändige BEstimmung des nachfolgenden Containerelements entfällt.

Übrigens:

BlackPepper schrieb:

...würde ich nach dem Löschen auf das darauf folgende Element zeigen, beziehungswese auf das vorherige wenn ich schon am Ende gewesen wäre. Nur wenn ich das einzige Element gelöscht hätte, hätte ich auf NULL verwiesen....

Ersteres fände ich "kernschlecht": "Mal auf das folgende, mal auf das vorherige verweisen" ?
Sorry, das ist total unbrauchbar. Außerdem wäre das Verhalten komplett anders als bei andern Containern, was den Umgang nicht einfacher machen würde (und einen Containertausch quasi unmöglich).

Zweiteres ist nicht nur wegen der "CopyÜbergabe" (s. LordJaxom) unmöglich (könnte man ja ändern), sondern deswegen weil es gar kein "NULL" bei Iteratoren gibt. Anders ausgedrückt: Du müsstest nicht nur den Container ändern, sondern auch die komplette Semantik von Iteratoren - und spätestens da, wo Iteratoren zu simplen Zeigern degenerieren, hättest Du den Bruch.

Gruß,

Simon2.

[BlackPepper]

Simon2 schrieb:

Naja. insgesamt hat es 400 Seiten und das Kapitel über Container immerhin auch fast 60. Du verzeihst mir, wenn ich das jetzt nicht abtippe, hoffe ich ...

Ausnahmsweise

Simon2 schrieb:

Aber das Entscheidende ist:

Seite 105 (Kap. 7.2) schrieb:

void erase(iterator position);

[...]
Der Wert des Iterators ist nach dem Aufruf von erase nicht mehr definiert, weil der Element auf das er verwies, gelöscht wurde. erase(end()) hat keinen Effekt.
[...]
Bei allen drei Versionen der Elementfunktion erase verlieren nur Referenzen, Zeiger und Iteratoren auf gelöschte Containerelemente ihre Gültigkeit. Im Gegensatz zu den entsprechenden Funktionen sequentieller Container ist der Rückgabetyp für die beiden letzten Elementfunktionen void statt iterator [...], weil so die unter Umständen recht aufwändige BEstimmung des nachfolgenden Containerelements entfällt.

Gruß,

Simon2.

Danke, das wollte ich wissen. Dein Buch scheint besser zu sein als meins. Muß ich mal unserer Bücherei sagen.

Grüße M. Incani

[LordJaxom]

Simon2 schrieb:

void multimap::erase( iterator pos );
size_type multimap::erase( const key_type& key );

helfen da nicht wirklich.

Ups. Tatsache. Da ist Dinkumware (meine Onlinereferenz) doch tatsächlich mal nicht 100% standardkonform, deren erase Methoden liefern den nächsten Iterator zurück.

[Simon2]

BlackPepper schrieb:

...
Ausnahmsweise :-)...

Danke

Welches Buch hast Du denn ?
Zur Info: Ich habe mein letztes Post nochmal um Kommentare zu Deinem Containervorschlag erweitert.

Gruß,

Simon2.

[Simon2]

LordJaxom schrieb:

...
Ups. Tatsache. Da ist Dinkumware (meine Onlinereferenz) doch tatsächlich mal nicht 100% standardkonform, deren erase Methoden liefern den nächsten Iterator zurück.

Das Gemeine ist ja, dass Du für andere Container Recht gehabt hättest !!
Finde ich nicht gerade optimal von den STL-Entwicklern ... bestimmt wieder ein Kompromiss oder "historisch gewachsen".

Gruß,

Simon2.

[camper]

Ein bekanntes Problem

[*john 0]

Hallo,
für Zweifelsfragen sollte man Zugriff auf die ISO Norm haben.

BlackPepper schrieb:

Nur ist nichts dokumentiert. Zumindest habs ich nicht gefunden.

In der ISO Norm steht genau drin, was bei erase passiert.
Für Sequenzen (siehe §23.1.1 Absatz 7 bzw. gilt genau das was Du beschreibst, S.erase(q) setzt q auf den Nachfolger von q. Im Zweifelsfall ist das S.end().
Für assoziative Container gilt dagegen § 23.1.2 Absatz 8. Nur die Iteratoren auf die gelöschten Elemente werden ungültig, alle anderen bleiben gültig.

[pumuckl]

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).
Folgendes sollte aber eigentlich fuer alle Container gehn:

MyContainer::iterator pos;
/* ... */
mycont.erase(pos++);

Dazu:
Vermutlich ist fuer sequentielle Container der Ausdruck

pos = mycont.erase(pos);

mindestens so effizient. Wie gross da die Unterschiede sind weiss ich nicht. Semantisch sehe ich keine Unterschiede, und fuer den Fall dass man sich spaeter noch fuer einen anderen, nicht-sequentiellen Container entscheidet, kann mans auf jeden Fall erstmal bei der ersten Version belassen (Optimierungen sollten ja sowieso immer erst gegen Ende der Entwicklung stattfinden).

[BlackPepper]

Simon2 schrieb:

BlackPepper schrieb:

...
Ausnahmsweise :-)...

Danke

Welches Buch hast Du denn ?
Zur Info: Ich habe mein letztes Post nochmal um Kommentare zu Deinem Containervorschlag erweitert.

Gruß,

Simon2.

Unsere Bücherei hat mehrere STL Bücher. Ich hab ISBN 0-321-41299-0

Grüße M. Incani

[CStoll]

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

[pumuckl]

hm gut... dann sollte auch ich mich mal etwas doller mit den spezifikationen auseinandersetzen...

[RHBaum]

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

[schokomann]

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.

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

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.