Wird vector.end() ungültig bei vector.erase()?

ipsec

Hab ich da grade ne Schraube im Hirn? Wenn man ein Element im vector löscht, werden doch die darauffolgenden nach vorne kopiert. Also wird der end-Iterator ungültig, oder? Du kannst doch aber in der Schleifenbedingung immer direkt .end() aufrufen.
Btw: Wird bei dem it = this->m_vecWorker.erase(it); mit anschließendem it++ im Schleifenkopf nicht ein Element übersprungen?

drakon

end ist halt kein normaler Iterator. Den gibts ja z.B auch, auch wenn es kein Element im Container gibt. Es macht auch logisch überhaupt keinen Sinn den irgendwie zu verändern, wenn man den Container verändert.

Btw: Wird bei dem it = this->m_vecWorker.erase(it); mit anschließendem it++ im Schleifenkopf nicht ein Element übersprungen?

Doch. Das habe ich im obigen Code übersehen.

ipsec

Ich stell mir das blos grade bildlich vor (beim Vector sind die Iteratoren im einfachsten Fall ja blos einfache Zeiger):

1  2  3  4  5  6
   ^              ^
  it             end

// Element bei it wird gelöscht

1  3  4  5  6  ?
   ^              ^
  it             end

Also wird end ungültig (beachte, das hier die Variable end gemeint ist, nicht der Rückgabewert von end()).
Wo ist jetzt mein Denkfehler?

otze

drakon schrieb:

Nein. Das ist Ok.

Da das Beispiel von ipsec korrekt ist, kann das so nicht stimmen. Du iterierst ja nicht bis (vec.begin()+vec.size()) sondern bis vec.end(). Und das ist halt schwierig zu implementieren, wenn das mit einem Zeiger gemacht wird. Und wie wir wissen sind Zeigerimplementationen standardkonform.

Der Punkt ist eigentlich, dass die Funktion vector::end() sich anpasst. Es wird also nach jedem erase ein anderer Iterator zurückgegeben. Aber speichert man ihn wie der OP in einer variable, geht da snatülich nicht mehr. Das ist ein Zugriff auf tote Objekte. crasht zwar (meistens) nicht, tut aber auch nicht das, was es soll.

drakon

otze schrieb:

drakon schrieb:

Nein. Das ist Ok.

Da das Beispiel von ipsec korrekt ist, kann das so nicht stimmen. Du iterierst ja nicht bis (vec.begin()+vec.size()) sondern bis vec.end(). Und das ist halt schwierig zu implementieren, wenn das mit einem Zeiger gemacht wird. Und wie wir wissen sind Zeigerimplementationen standardkonform.

Der Punkt ist eigentlich, dass die Funktion vector::end() sich anpasst. Es wird also nach jedem erase ein anderer Iterator zurückgegeben. Aber speichert man ihn wie der OP in einer variable, geht da snatülich nicht mehr. Das ist ein Zugriff auf tote Objekte. crasht zwar (meistens) nicht, tut aber auch nicht das, was es soll.

Widersprichst du dir da jetzt nicht gerade?

Ich habe kurz mal im Standard gesucht, aber auf die schnell nix gefunden, was gross über ::end etwas aussagt.

Ich verstehe auch nicht ganz, warum das schwierig sein sollte zu implementieren und warum sich end anpassen muss.

Wenn man Zeiger nimmt kann man das ja einfach mit einem 0 Zeiger realisieren, welcher allgemeingültig ist. Wenn ein Iterator sonst über das Ziel schiesst, wird er halt auch auf 0 gesetzt und ein Vergleich klappt und ist sinnvoll.

Nexus

drakon schrieb:

Nein. Das ist Ok.

Bist du dir hier sicher oder tun das die Implementierungen, die du kennst? Mir wäre jedenfalls nicht bekannt, dass der Standard dieses Verhalten garantiert.

Ich sehe das ähnlich wie otze und denke nicht, dass end() zwischengespeichert werden kann. Zumindest nicht bei std::vector und std::deque , bei std::list und den assoziativen Containern hat man ohnehin die Iterator-Gültigkeits-Garantie.

Edit:

drakon schrieb:

Ich verstehe auch nicht ganz, warum das schwierig sein sollte zu implementieren und warum sich end anpassen muss.

Weil die Semantik bei Zeigeriterationen so aussieht, dass auf das Element hinter dem letzten gültigen gezeigt wird. Die Adresse ist also immer wieder eine andere.

drakon schrieb:

Wenn man Zeiger nimmt kann man das ja einfach mit einem 0 Zeiger realisieren, welcher allgemeingültig ist. Wenn ein Iterator sonst über das Ziel schiesst, wird er halt auch auf 0 gesetzt und ein Vergleich klappt und ist sinnvoll.

Wie willst du ihn auf Null setzen? Das einzige, was du hast, ist ein ++itr auf Anwenderseite. Kein if , kein gar nichts, nur ein roher Zeiger und ein ++.

ipsec

Ich hab eben mal in den MSVC-Headern geguckt, wie die das dort gemacht haben:

iterator end()
{	// return iterator for end of mutable sequence
	return (iterator(_Mylast, this));
}

// _Mylast ist definiert als

pointer _Mylast;	// pointer to current end of sequence

Hier ist also end() ein Iterator, der auf das hypotethische Element hinter dem letzten zeigt. Damit mach auch der Vergleich Sinn, die Größe ergibt sich aus end() - begin(), beim Inkrement der Iteratoren muss im Prinzip nichts beachtet werden, kurzum eine imho sinnvolle Implementierung, die wohl in ähnlicher Form auch bei anderen Compilern zu finden sein wird. Einziges Problem: Wenn ich ein Element des vectors lösche, rücken alle nachfolgenden Elemente eine Position vor. Also muss auch end() eine Position vorrücken. Wenn man es aber den Wert in einer Variable speichert, passiert das nicht, d.h. bei der Iteration würde man über ein nicht vorhandenes Element iterieren, bevor man zu Variable end kommt. Das meinte otze mit "end() passt sich an": Wenn man Elemente löscht, hat end() danach einen anderen Wert.

Shade Of Mine

Wenn end() immer das selbe liefern würde, wäre das eine ziemliche Katastrophe.

Einfach besipiel: implementiert einen iterator für std::vector um folgenden Code korrekt ausführen zu können:

vector::iterator i=vec.begin();
while(i!=vec.end()) {
  ++i;
}

Das Problem für i ist nun: wann ist das Ende erreicht? Ein simples

iterator& operator++() {
  ++pointer_to_element;
}

reicht ja plötzlich nicht mehr. man muss ein:

iterator& operator++() {
  ++pointer_to_element;
  if(pointer_to_element >= vec.begin()+vec.size()) *this=vec.end();
}

von komplexeren containern mal komplett abgesehen

Tachyon

drakon schrieb:

end ist halt kein normaler Iterator. Den gibts ja z.B auch, auch wenn es kein Element im Container gibt. Es macht auch logisch überhaupt keinen Sinn den irgendwie zu verändern, wenn man den Container verändert.

Btw: Wird bei dem it = this->m_vecWorker.erase(it); mit anschließendem it++ im Schleifenkopf nicht ein Element übersprungen?

Doch. Das habe ich im obigen Code übersehen.

Bei std::vector::erase() werden alle Iteratoren ab position bzw. first invalidiert. Wo steht was von einer Ausnahme für Iteratoren die man von std::vector::end() bekommen hat?

drakon schrieb:

[...]Ich habe kurz mal im Standard gesucht, aber auf die schnell nix gefunden, was gross über ::end etwas aussagt.[...]

Die Beschreibung steht nich bei std::vector::end() , sondern bei std::vector::erase() :

ISO/IEC 14882:2003 schrieb:

`iterator erase ( iterator position );

iterator erase ( iterator first, iterator last );`

[...]Effects: Invalidates all the iterators and references after the point of the erase.

Da steht nicht "with the exception of iterators to end".

drakon schrieb:

Wenn man Zeiger nimmt kann man das ja einfach mit einem 0 Zeiger realisieren, welcher allgemeingültig ist. Wenn ein Iterator sonst über das Ziel schiesst, wird er halt auch auf 0 gesetzt und ein Vergleich klappt und ist sinnvoll.

Das wäre dann für sowas wie std::vector<T>::difference_type d = std::distance(vec.begin(), vec.end()) aber schlecht...

theliquidwave

Hi.
Also doch anders. Mist.

Btw: Wird bei dem it = this->m_vecWorker.erase(it); mit anschließendem it++ im Schleifenkopf nicht ein Element übersprungen?

Stimmt, dass ergibt Sinn
Wie kann ich das Problem lösen? So wäre es doch korrekt oder?

for (vector<Key_s*>::iterator it = this->m_vecWorker.begin(); it != this->m_vecWorker.end();
; )
{
    Key_s *pKey = (*it);

    // mach was

    if (pKey->bla)
    {
        it = this->m_vecWorker.erase(it);
    }
    else
    {
        it++;
    }
}

Sieht aber ziemlich doof aus. Gibt es da nichts praktischeres?

Edit: Aber wenn ich (theoretisch) nichts lösche, bleibt .end() doch valid, oder?
Edit2: Wenn ich mir das gerade noch einmal überlege, wie ein vector überhaupt von "innen" funktioniert, ist es ja doch eher sinnlos das Ende zwischenzuspeichern oder? Ich dachte bisher immer, dass bei jedem Aufruf der Enditerator neu berechnet wird. Aber meiner Meinung nach sollte die Funktion beim nicht löschen eines Items immer den gleichen Iterator liefern. Deshalb ist Zwischenspeichern eigentlich nicht nötig oder?

Gruß und Danke!

hustbaer

Shade Of Mine schrieb:

Wenn end() immer das selbe liefern würde, wäre das eine ziemliche Katastrophe.

Einfach besipiel: implementiert einen iterator für std::vector um folgenden Code korrekt ausführen zu können:
vector::iterator i=vec.begin();
while(i!=vec.end()) {
  ++i;
}
Das Problem für i ist nun: wann ist das Ende erreicht? Ein simples
iterator& operator++() {
  ++pointer_to_element;
}
reicht ja plötzlich nicht mehr. man muss ein:
iterator& operator++() {
  ++pointer_to_element;
  if(pointer_to_element >= vec.begin()+vec.size()) *this=vec.end();
}
von komplexeren containern mal komplett abgesehen

Naja, man könnte es auch im operator == regeln. Ob das in den meisten Programmen nen Geschwindigkeits-Vorteil bringt ist natürlich wieder eine andere Sache.

Im Übrigen teile ich deine Meinung, es wäre für std::vector ne ziemliche Katastrophe (bei std::list hingegen bietet es sich ja geradezu an).

Simon2

theliquidwave schrieb:

...
Wie kann ich das Problem lösen? ...
...

Ich würde dafür remove_if() nehmen - dann ist's ein "Einzeiler"(OK, leicht geschummelt ).
Dazu muss man natürlich eine geeignete "predicate function" schreiben, aber das ist nicht wirklich schwer.
... ach ja: Rückgabenwert dann einfach in vector::erase() einsetzen und schon klappt's.

(ungetestet)

bool IsBla(Key_s* const& i) { return (i->bla()); }

....
m_vecWorker.erase(remove_if(m_vecWorker.begin(), m_vecWorker.end(), IsBla), m_vecWorker.end());

Gruß,

Simon2.

drakon

Tachyon schrieb:

...

Ok, stimmt. Hatte ich mich extrem geirrt. Hab da einiges durcheinander gebracht. Danke für den Auszug aus dem Standard.