Worauf zeigen Iteratoren genau?

Hallo,

ich bin mir nicht sicher, wie ich die Iteratoren zu verstehen habe.
Zeigen sie auf ein konkretes Objekt, oder zeigen sie auf ein Feld einer Liste.
Bsp.

vector<int> IntField;

  IntField.push_back(1);
  IntField.push_back(2);

  vector<int>::iterator it = IntField.begin();

  IntField.erase(it); //Das Feld mit der 1 wird entfernt
  cout << *it;  // *it liefert nun 2

Nach diesem Test müsste also it erst auf das erste Feld gezeigt haben, und als das entfernt wurde, ist die 2 nachgerutscht, so dass nun it immer noch auf das selbe Feld zeigt, in dem ist jetzt aber die 2.

Im Gegensatz dazu die schreibt die SGI Doku:

Pointers, for example, are iterators; the value type of int* is int.

Wenn ich aber einen int* lösche, zeigt der Pointer danach ja auf ungültigen Speicher. Hmm.

niemand

erase verändert Deinen Iterator (genauer, setzt ihn auf das nächste Element). Hättest Du einen zweiten Iterator auf denselben Vektor, ist der nach dem erase potentiell ungültig.

MFK

SeppSchrot schrieb:

Nach diesem Test...

Dieser Test ist Unsinn, weil vector::erase alle Iteratoren vom gelöschten Element bis zum Ende ungültig macht.

niemand

Sorry, meine Antwort war natürlich Unsinn. erase gibt einen gültigen Iterator auf das nächste Element zurück (und verändert den übergebenen nicht). Und damit kann (muss aber nicht) Dein iterator nach dem Löschen ungültig sein.

Aah

Jetzt wo ihr das sagt, hab ich auch die Fussnoten in der Doku entdeckt.

Danke

Helium

SeppSchrot schrieb:

Hallo,

ich bin mir nicht sicher, wie ich die Iteratoren zu verstehen habe.
Zeigen sie auf ein konkretes Objekt, oder zeigen sie auf ein Feld einer Liste.
Bsp.
vector<int> IntField;
  
  IntField.push_back(1);
  IntField.push_back(2);

  vector<int>::iterator it = IntField.begin();

  IntField.erase(it); //Das Feld mit der 1 wird entfernt
  cout << *it;  // *it liefert nun 2
Nach diesem Test müsste also it erst auf das erste Feld gezeigt haben, und als das entfernt wurde, ist die 2 nachgerutscht, so dass nun it immer noch auf das selbe Feld zeigt, in dem ist jetzt aber die 2.

Im Gegensatz dazu die schreibt die SGI Doku:

Pointers, for example, are iterators; the value type of int* is int.

Wenn ich aber einen int* lösche, zeigt der Pointer danach ja auf ungültigen Speicher. Hmm.

Quatsch! Wie löscht du denn ein int*? Du willst nicht das Feld löschen (clear) sondern ein Element daraus (erase). Wie machst du das? Genau, imdem du ie dahinterliegenden Elmente jeweils um eins nach vorne ziehst. Dabei ist es egal, ob es sich um einen vorgefertigten Algorithmus (vector::erase) oder eine selbst-geschriebene Variante handelt.

ness

Ansich geht es dich garnichts an, wie iteratoren implementiert sind. Und wenn der Iterator ner liste der Schlüssel zu ner hashmap wär, die nen index für nen assoziierten vektor gibt und beim dereferenzieren genau dieses verfahren benutzt würde, um das element zu finden wäre das standard-konform, IMHO. (natürlich nur wenn alle vom standard geforderten eigenschaften erfüllt sind [semantik, performance, ...?])

Helium schrieb:

Quatsch! Wie löscht du denn ein int*? Du willst nicht das Feld löschen (clear) sondern ein Element daraus (erase).

Was bitte genau ist 'Quatsch'?
Dass ein Pointer int* p nach

delete p;

auf ungültigen Speicher zeigt?

Wie machst du das? Genau, imdem du ie dahinterliegenden Elmente jeweils um eins nach vorne ziehst. Dabei ist es egal, ob es sich um einen vorgefertigten Algorithmus (vector::erase) oder eine selbst-geschriebene Variante handelt.

Offensichtlich ist es nicht egal, da sonst die nachfolgenden Iteratoren nicht ungültig würden.

terraner

Bei einem Vector werden sie nicht zwangsweise ungültig, da der Vector den Speicher an einem Stück alloziert. D.h. solange, der Vector keinen neuen Speicher anfordert, ist der Iterator gültig.
Allerdings weiß ich nicht, inwiefern der Standard, dass allozieren von Speicher erlaubt oder verbietet. Wenn bei jeder Größenänderung die Implementierung neuen Speicher alloziert, dann ist der Iterator natürlich ungültig.

mfg

niemand

Im Standard (23.2.4.2 und 23.2.4.3) steht, dass
a) insert (und damit auch push_back) nur dann die Iteratoren ungültig werden, wenn Speicher "reallokiert" wird
b) erase alle Iteratoren und Referenzen hinter dem zu löschenden Element invalidiert (keine Ausnahme angegeben).

Garantiert ist, dass nach einem Aufruf von reserve mit entsprechender Größe keine Reallokierung bei insert stattfindet, bis diese Größe überschritten wird. Es gibt keine Aussage, wie oft bei welcher Aktion neuer Speicher angefordert wird. Daraus, dass erase nur die Iteratoren hinter dem zu löschenden Element invalidiert, kann man wohl schliessen, dass bei erase keine "Reallokierung" stattfindet (weil sonst die Iteratoren vor dem zu löschenden Element auch ungültig würden). Persönlich würde ich mich nur sehr ungern auf so was verlassen.

Die Invalidierung bei erase ist aber eigentlich auch einleuchtend. Man nehme einen vector mit Klassen und hat jetzt einen Iterator, der auf das letzte Element zeigt. Jetzt löscht mit mittendrin ein Element raus. Der durchaus übliche Algorithmus, alles um eins nach vorne zu kopieren, bewirkt, dass zwar der Speicher der dem letzten Element gehörte noch da ist, das letzte Element aber zerstört ist, d.h. der Beispielsiterator zeigt jetzt auf ein kaputtes Element (und genauer, gar nicht mehr auf ein Element des Vektors). Bei vector<int> hat man wahrscheinlich Glück, der Wert des letzten Elements ist noch da und es gibt keinen Absturz beim derferenzieren. Das ist aber Glück und Zufall (und liegt am int)

Hallo um mal auf die Eingangsfrage zurückzukommen...
Worauf zeigt ein Iterator eigentlich.
Da könnte man denken eine Iterator wäre ein Zeiger. Das ist aber nicht der Fall. Ein Iterator ist ein Objekt einer Klasse mit den überladenen operatoren * und -> (u.a. z.B ++)
, die beide jeweils eine (evtl. const) Referenz auf ein Element des darunterliegenden Containers (muss kein Array sein) zurückgeben.

Gruß

Helium

SeppSchrot schrieb:

Helium schrieb:

Quatsch! Wie löscht du denn ein int*? Du willst nicht das Feld löschen (clear) sondern ein Element daraus (erase).

Was bitte genau ist 'Quatsch'?
Dass ein Pointer int* p nach
delete p;
auf ungültigen Speicher zeigt?

Warum vergelcihst du Äpfel mit Birnen? Ein delete auf einen Zeiger angewand hat nicht das geringste mit einem erase gemeinsam. Bei einem erase wird in der Regel kein Speicher frei gegeben, bei einem delete schon.
Wie bereits gesagt werden die nachfolgenden Elemente nach vorne gezogen (vorher wird natürlich der D'tor des elements aufgerufen). Sicher wäre es auch erlaubt neuen Speicher anzufordern und alle Elemente bis auf das zu entfernende rüberzukopieren, aber das wäre deutlich uneffektiver.
vector<int *> foo;

foo.push_back (new int);

delete foo.front();  // dass ist ein delete

foo.erase (foo.begin());  // dass ist ein erase
Wie machst du das? Genau, imdem du ie dahinterliegenden Elmente jeweils um eins nach vorne ziehst. Dabei ist es egal, ob es sich um einen vorgefertigten Algorithmus (vector::erase) oder eine selbst-geschriebene Variante handelt.

Offensichtlich ist es nicht egal, da sonst die nachfolgenden Iteratoren nicht ungültig würden.

Sie können ungültig werden. Du hast keinerlei Garantie darüber, ob sie gültig bleiben oder nicht. Wenn sie also noch auf ein sinnvolles Objekt verweisen, dann ist das völlig in ordnung und genauso wird es bei einer durchschnittlichen Implementation auch sein, wenn du nicht gerade das letzte Element eines Vektors entfernst.