[STL] Vector iterator an Position springen

[seldon]

https://xkcd.com/303/

[Klaus82]

Ah,
danke für die Antworten. Tatsächlich kann ich auf Elemente des Vektors wie bei einem Array über den Index zugreifen.

Ich habe dazu mal was gebastelt:

#include <iostream>
#include <vector>

using namespace std;

class FOO
{
public:
	FOO(int i){ fooVariable = i; }
	double fooVariable;

};

int main()
{
	vector<FOO> v_foo;

	for(int i = 0; i < 20; ++i)
	{
		v_foo.push_back(FOO(i));
	}

	for(unsigned int i = 0; i < v_foo.size(); ++i)
	{
			cout << v_foo[i].fooVariable << endl;
	}

	return 0;

}

Jetzt habe ich aber das Problem, dass ich gerne etwas aus dem Vektor an einer bestimmten Stelle löschen würde. Der Knackpunkt ist nur, dass die Operation erase() als Input eine Iteratorposition haben möchte, z.B. kann meine zweite For-Schleife so aussehen:

for(unsigned int i = 0; i < v_foo.size(); ++i)
	{
		if(v_foo[i].fooVariable == 10)
		{ v_foo.erase(iter); }

			cout << v_foo[i].fooVariable << endl;
	}

Nur wie kriege ich jetzt die Position eines Iterators iter (siehe Code Schnippsel) an die Stelle mit dem Index i ?
Muss ich da die ganze Zeit einen Iterator mitlaufen lassen?

vector<FOO>::iterator iter = v_foo.begin();	
	for(unsigned int i = 0; i < v_foo.size(); ++i)
	{
		if(v_foo[i].fooVariable == 10)
		{ v_foo.erase(iter); }

			cout << v_foo[i].fooVariable << endl;
		iter++;
	}

Das funktioniert zwar, wäre doch aber ziemlich umständlich, wenn ich schon Zugriff über einen Index habe.

Gruß,
Klaus.

P.S.: Ich bemerke gerade: Die cpp-Umgebung wertet "[i]" als Beginn der Italic Umgebung, die code-Umgebung tut das zum Glück nicht.

[SeppJ]

Dir wurde doch schon bestimmt 5x gesagt, wie du zu einem Index den Iterator bekommst. Lies nochmal alle Antworten gründlich.

Außerdem möchtest du deine ganze Löschschleife vermutlich eher durch ein erase-remove ersetzen:
http://en.wikipedia.org/wiki/Erase-remove_idiom

P.S.: Ich weiß nicht, was du für Probleme mit den Tags hast:

foo[i]; bla

P.P.S.: Hah, jetzt sehe ich, was du meinst. Aber ich kann es nicht reproduzieren, du hast da irgendwas ganz geheimnisvolles in deinem Beitrag angestellt. ICh werde dem bei Gelegenheit mal nachspüren.

[Klaus82]

SeppJ schrieb:

Dir wurde doch schon bestimmt 5x gesagt, wie du zu einem Index den Iterator bekommst. Lies nochmal alle Antworten gründlich.

Na ja, wiederholt lese ich das:

seldon schrieb:

std::vector<double>::iterator iter = numbers.begin() + position;

Also kann ich z.B. eingeben:

iter = v_foo.begin() + 13;

Und dabei springt der Iterator jetzt an diese Stelle? Wenn das ganze nur bedeutet, dass intern 13 mal iter++ aufgerufen wird, dann wäre das ja Quatsch.

SeppJ schrieb:

Außerdem möchtest du deine ganze Löschschleife vermutlich eher durch ein erase-remove ersetzen:
http://en.wikipedia.org/wiki/Erase-remove_idiom

Ich gucks mir an.

Gruß,
Klaus.

[SeppJ]

Wie kommst du denn auf die Idee? vector-Iteratoren sind random_access-Iteratoren, mit denen kann man rechnen. Wäre sonst doch total bescheuert. Die Standardbibliothek ist schon recht gut durchdacht . (Natürlich nicht perfekt)

Wenn du es eine runde abstrakter möchtest, kannst du auch std::advance benutzen, dann geht das auch mit nicht-random-access-Iteratoren. Wobei bei einem list-Operator dann natürlich 13x operator++ aufgerufen würde, da es anders nicht geht. Aber dank Templatemagie würde für den vector-Iterator ein normales +13 gemacht.

[Klaus82]

seldon schrieb:

Was mir grad noch auffällt:

Klaus82 schrieb:

int position = rand() * size;

Ich nehme an, du meinst

int position = rand() % size;

Nein. Ich habe einen Zufallsgenerator, der Zufallszahlen zwischen 0 und 1 generiert. D.h. wenn ich ein zufällig bestimmtes Element des Vektors haben möchte, so mache ich:

unsigned int size = r_electrons.size();
	unsigned int position = (*p_random)() * size;

	r_electrons[position].energy = r_electrons[position].energy + transfered_energy;

Allerdings bekomme ich da nach ein paar Durchläufen einen Speicherzugriffsfehler.

Also scheint es nicht so richtig zu klappen. Habe ich dabei einen Gedankenfehler was schief gehen könnte?

Gruß,
Klaus.

[SeppJ]

Da kann ja auch size als position rauskommen, das wäre dann jenseits der Grenze.

Was du aber bisher so gezeigt hast, flößt nicht gerade Zuversicht ein, dass der Rest des Programmes richtig wäre, wahrscheinlich hast du noch mehr Fehler.

[Klaus82]

SeppJ schrieb:

Da kann ja auch size als position rauskommen, das wäre dann jenseits der Grenze.

Das stimmt natürlich, dann muss ich das korrigieren:

unsigned int position = (*p_random)() * (size - 1);

SeppJ schrieb:

Was du aber bisher so gezeigt hast, flößt nicht gerade Zuversicht ein, dass der Rest des Programmes richtig wäre, wahrscheinlich hast du noch mehr Fehler.

Ja,
irgendwo knirscht es da ganz gewaltig.

Ich meine ich habe eine große for Schleife:

vector<electron> electrons;
vector<electron> & r_electrons = electrons;

for(unsigned int i = 0; i < electrons.size(); ++i)
{
  // .. stuff
  auger.auger_process(r_electrons,i);
  // .. stuff
}

Mit der Klassenfunktion:

void AUGER::auger_process(vector<electron> & r_electrons, unsigned int i)
{

	if(r_electrons[i].energy > 5 || (*p_random)() > auger_probability(r_electrons[i].energy) )
	{ return; }

	double transfered_energy = r_electrons[i].energy + ionization_potential(4);

	r_electrons.erase(r_electrons.begin()+i);

	unsigned int size = r_electrons.size();
	unsigned int position = (*p_random)() * (size - 1);
	r_electrons[position].energy = r_electrons[position].energy + transfered_energy;

	return;
}

Und ich kriege immer dann einen Speicherzugriffsfehler, wenn ich diese Klassenfunktion ausführe.
Maaaan, so schief programmiert ist das doch hoffentlich nicht - auch wenn natürlich schon 'ein-wenig-schief' reicht.

Gruß,
Klaus.

[SeppJ]

Solche Abstürze kann man am besten im Debugger oder mit Tools wie valgrind nachvollziehen, dazu bräuchten wir aber den gesamten Code (möglichst weit gekürzt, so dass deine Fehler gerade noch auftreten). Oder das kannst du natürlich auch selber machen, muss man sowieso irgendwann mal üben.

Vermutlich liegen deine Fehler ganz woanders. Dadurch, dass du deine Klassen nicht sauber designed hast, du selber manuelle Speicherverwaltung probiert hast (ohne es zu können) oder du irgendwo C-Mittel mit C++ gemischt hast (ohne die Fallstricke genau zu kennen).

[Klaus82]

SeppJ schrieb:

Oder das kannst du natürlich auch selber machen, muss man sowieso irgendwann mal üben.

Ja, ich versuche mich gerade an gdb...

SeppJ schrieb:

Vermutlich liegen deine Fehler ganz woanders. [..]

Wahrscheinlich. Und nur durch das Aufrufen der Klassenfunktion kommt der Fehler ans Licht, sonst habe ich scheinbar Glück, dass nichts passiert.

Gruß,
Klaus.

[Klaus82]

Edit:

SeppJ schrieb:

Dadurch, dass du deine Klassen nicht sauber designed hast [..]

Ich nehme an du meinst die Regel der Großen Drei?

SeppJ schrieb:

[..] du selber manuelle Speicherverwaltung probiert hast (ohne es zu können)

Was genau bezeichnest du als manuelle Speicherverwaltung? Die Anwendung von Zeigern und / oder Referenzen?

Gruß,
Klaus.

[DocShoe]

Kann size in Zeile 11 0 werden?
Sonst bau dir doch ein paar Debug Ausgaben in deine Funktion ein, die Auskunft darüber geben, was passiert. Das VS hat z.B. das TRACE Makro, sowas kann man sich zur Not auch noch selbst basteln. Damit brauchst du nicht ewig mit dem Debugger durch dutzende Schleifendurchläufe zu gehen, sondern kannst dir den Inhalt verschiedener Variablen bis zu dem Punkt wo´s knallt ausgeben lassen.

[seldon]

Klaus82 schrieb:

unsigned int position = (*p_random)() * (size - 1);

Unter der Annahme, dass p_random gleichverteilte Fließkommazahlen zwischen 0 und 1 generiert, geht die Gleichverteilung durch diese Rechnung verloren. size - 1 wird wesentlich weniger häufig vorkommen als alle anderen Werte.

Diese Fließkommarunderei verkompliziert die ganze Angelegenheit deutlich - selbst wenn du sicherstellst, dass p_random im Intervall [0, 1) statt [0, 1] generiert, kannst du nicht sicher sein, dass p_random() * size nicht size wird - Rundungsfehler halt. Es wäre besser, einen Zufallszahlengenerator zu benutzen, der gleich Integer ausspuckt und ihn durch std::uniform_int_distribution zu pressen.

[Klaus82]

DocShoe schrieb:

Kann size in Zeile 11 0 werden?
Sonst bau dir doch ein paar Debug Ausgaben in deine Funktion ein, die Auskunft darüber geben, was passiert.

Puh, ja. Ich versuche gerade debuggen zu lernen und finde diese Kurzanleitung ganz gut.

Ich habe das ganze mit einer core Datei probiert und dann Backtrace.

.
..
...
Program terminated with signal 11, Segmentation fault.
[New process 5100]
#0  0x00000000004060de in AUGER::auger_process ()
(gdb) bt
#0  0x00000000004060de in AUGER::auger_process ()
#1  0x000000000040370c in main ()
Current language:  auto; currently asm

Also schon ein guter Hinweis darauf, dass es an dem liegen muss was in auger_process() passiert.

seldon schrieb:

Klaus82 schrieb:

unsigned int position = (*p_random)() * (size - 1);

Unter der Annahme, dass p_random gleichverteilte Fließkommazahlen zwischen 0 und 1 generiert, geht die Gleichverteilung durch diese Rechnung verloren. size - 1 wird wesentlich weniger häufig vorkommen als alle anderen Werte.

Also ich habe mal (das Debuggen lerne ich ja noch) ganz naiv eine Ausgabe implementiert:

unsigned int size = r_electrons.size();
	unsigned int position = (*p_random)() * (size - 1);
	cout << "Size : " << size << " vs. position : " << position << endl;
	r_electrons[position].energy = r_electrons[position].energy + transfered_energy;

Und heaus kam jetzt folgendes:

Size : 0 vs. position : 1872372286
Speicherzugriffsfehler (core dumped)

EDIT:
Na klar, weil ich size -1 eingebaut habe.
D.h. wenn size gerade 1 ist, dann knallt es eben! Baue ich also wieder aus.

Also das wundert mich jetzt doch. Vor allen Dingen weil ich vorher eine if Abfrage drin habe

if(electrons.size() > 0)

Also diese Funktion dürfte gar nicht ausgeführt werden, wenn electrons.size() Null ist!

Aber ich habe ja noch eine andere starke Vermutung, wo wahrscheinlich reinspielt, dass ich keinen Destruktor definiert habe (also schlechtes Klassendesign).

Grob habe ich (leicht erweitert) die Struktur:

vector<electron> electrons;
vector<electron> & r_electrons = electrons;

for(int k = 0; k < 1000; ++k)
{

  for(int n = 0; n < 10; ++n)
  {
    electrons.push_back(...)
  }

  for(unsigned int i = 0; i < electrons.size(); ++i)
  {
    // .. stuff
    auger.auger_process(r_electrons,i);
    // .. stuff
  } 

electrons.clear();
}

Also ich definiere einmal die Referenz auf meinen Vektor. Allerdings leere ich meinen Vektor öfters, d.h. ich rufe eigentlich Destruktoren auf, die ich aber in der Klasse nicht explizit definiert habe.
Kann es sein, dass dadurch die Adresse (in der Referenz) irgendwie in Mitleidenschaft gezogen wird? In der Beschreibung von clear steht dazu nichts, dass Pointer o.ä. dadurch ungültig würden (wie z.B. bei erase() aber das bezieht sich dann ja wieder auf Pointer auf das gelöschte Element).

Oh man ...

Gruß,
Klaus.

[krümelkacker]

Klaus82 schrieb:

Ich meine ich habe eine große for Schleife:

vector<electron> electrons;
vector<electron> & r_electrons = electrons;

for(unsigned int i = 0; i < electrons.size(); ++i)
{
  // .. stuff
  auger.auger_process(r_electrons,i);
  // .. stuff
}

Die Referenz ist da unnötig; denn der Ausdruck electrons hat denselben Typ und dieselbe Wertkategorie wie der Ausdruck r_electrons . Dass lezteres als Referenz deklariert war, merkt die Funktion gar nicht. Es beeinflusst auch nicht die Überladungsauflösung. Ausdrücke haben nie einen Referenztypen.

Klaus82 schrieb:

Mit der Klassenfunktion:

void AUGER::auger_process(vector<electron> & r_electrons, unsigned int i)
{

	if(r_electrons[i].energy > 5 || (*p_random)() > auger_probability(r_electrons[i].energy) )
	{ return; }
	
	double transfered_energy = r_electrons[i].energy + ionization_potential(4);
	
	r_electrons.erase(r_electrons.begin()+i);
	
	unsigned int size = r_electrons.size();
	unsigned int position = (*p_random)() * (size - 1);
	r_electrons[position].energy = r_electrons[position].energy + transfered_energy;
	
	return;
}

Und ich kriege immer dann einen Speicherzugriffsfehler, wenn ich diese Klassenfunktion ausführe.
Maaaan, so schief programmiert ist das doch hoffentlich nicht - auch wenn natürlich schon 'ein-wenig-schief' reicht.

Das sieht schon komisch aus. Wenn man sich die äußere Schleife anguckt, denkt man: die geht über alle Elemente rüber, aber, hinterhältig wie du bist, veränderst du die Größe des vektors innerhalb der Funktion.

Das *(size-1) ist auch nicht richtig. Jedenfalls dann nicht, wenn Du eine Gleichverteilung haben willst. Bedenke auch, dass die implizite Umwandlung die Nachkommastellen einfach abschneidet. size ist also richtig als Faktor, wenn man annimmt, dass die Zufallszahl aus [0,1) gezogen wird. Sollte da doch dann mal eine 1.0 dabei sein oder Rundungsfehler auftreten, ist

static_cast<unsigned>((*p_random)() * size) % size

wahrscheinlich die beste Idee, sofern Du es unbedingt mit p_random machen willst.

[Klaus82]

krümelkacker schrieb:

Die Referenz ist da unnötig; denn der Ausdruck electrons hat denselben Typ und dieselbe Wertkategorie wie der Ausdruck r_electrons . Dass lezteres als Referenz deklariert war, merkt die Funktion gar nicht. Es beeinflusst auch nicht die Überladungsauflösung. Ausdrücke haben nie einen Referenztypen.

Aber ich dachte das brauche ich genau dafür:

krümelkacker schrieb:

Das sieht schon komisch aus. Wenn man sich die äußere Schleife anguckt, denkt man: die geht über alle Elemente rüber, aber, hinterhältig wie du bist, veränderst du die Größe des vektors innerhalb der Funktion.

Wenn ich keinen Pointer oder Referenz übergebe, so mache ich doch Call bei Value, also es wird eine lokale Kopie angelegt. Das Problem bei Call by Value ist doch aber, dass die lokale Kopie bearbeitet wird und Änderungen daran keine Auswirkungen auf das ursprüngliche Objekt haben.
So dachte ich, dass mein Vektor dementsprechend nicht bearbeitet wird, wenn ich das ganze nicht als Referenz übergebe.

Aber nochmal:

krümelkacker schrieb:

Das sieht schon komisch aus. Wenn man sich die äußere Schleife anguckt, denkt man: die geht über alle Elemente rüber, aber, hinterhältig wie du bist, veränderst du die Größe des vektors innerhalb der Funktion.

Was genau ist daran komisch? Dafür ist doch der Vektor zum Glück dynamisch. Oder wie macht man das 'professionell' ? Während ich die einzelnen Elemente durchgehe, kann welche wegnehmen, hinzufügen oder modifizieren.

Oder nachdem ich SeppJ Link gesehen habe 'merkt' man sich diese Elemente beim Durchgang und tut nach dem Durchgang entsprechend hinzufügen und löschen?

Gruß,
Klaus.

[Klaus82]

Also ich habe nochmal über diese Problemstellung nachgedacht, zum Einen das Verändern der Länger des Vektors, während er durchlaufen wird und zum Zweiten die Anwendung von Erase remove Idiom.

Zum ersten Punkt sehe ich ein, dass es sicherlich komisch ist die Länge eines Arrays zu ändern, während man ihn durchläuft - aber wie ich schon sagte, dafür ist es doch ein dynamisches Objekt?
Ich durchlaufe den Vektor mehrmals und durch Zufallszahlen bedingt ergibt sich bei jedem Durchlauf und für jedes Element individuell, ob es gelöscht wird oder nicht.

Und so verstehe ich auch nicht so recht, wie dieser Algorithmus des Löschens so recht funktionieren soll.
Ich würde meinen Vektor durchlaufen und jedes Mal, wenn sich ergibt, dass ein Element gelöscht werden soll, bekommt es sagen wir int remove = 1 gesetzt (vorher remove = 0).

Und anschließend (!) lasse ich den Algorithmus drüberlaufen, der alle Elemente mit remove = 1 nach hinten schiebt, um sie dann zu löschen?
Da würde ich ja zwei Mal meinen Vektor durchlaufen!

So frage ich mich natürlich direkt umgekehrt, ob ich meine Elemente nicht individuell löschen soll, sondern erstmal ans Ende schieben, um sie anschließend alle zu löschen. Das wäre dann scheinbar ein Kompromiss aus meiner bisherigen Lösung un dem Erase remove Idiom.
Nein wäre es nicht, denn Elemente in einem Vektor zu verschieben ist ziemlich umständlich.
Ich brauche den Vektor bisher eigentlich nur, weil ich auf ein beliebiges Element daraus zugreifen möchte. Ansonsten würde mir ja eine Liste oder ein Set völlig reichen.!

Ansonsten bin ich natürlich für vollkommen neue Sichtweisen dankbar.

Viele Grüße,
Klaus.

[redrew99]

Klaus82 schrieb:

So frage ich mich natürlich direkt umgekehrt, ob ich meine Elemente nicht individuell löschen soll, sondern erstmal ans Ende schieben, um sie anschließend alle zu löschen. Das wäre dann scheinbar ein Kompromiss aus meiner bisherigen Lösung un dem Erase remove Idiom.
Nein wäre es nicht, denn Elemente in einem Vektor zu verschieben ist ziemlich umständlich.
Ich brauche den Vektor bisher eigentlich nur, weil ich auf ein beliebiges Element daraus zugreifen möchte. Ansonsten würde mir ja eine Liste oder ein Set völlig reichen.!

Ansonsten bin ich natürlich für vollkommen neue Sichtweisen dankbar.

Wenn Du Elemente löscht, müssen die verbleibenden Elemente meines Wissens auch verschoben werden.
Zusätzlich denke ich mir, daß beim Löschen von Elementen jedes Element
einzeln gelöscht werden muß.

Verschiebt man allerdings erst die Elemente ans Ende und löscht dann, kann man "alle aufeinmal" löschen.

Je nach Anzahl der Elemente, die gelöscht werden sollen, kann das effektiver sein.

[camper]

seldon schrieb:

Diese Fließkommarunderei verkompliziert die ganze Angelegenheit deutlich - selbst wenn du sicherstellst, dass p_random im Intervall [0, 1) statt [0, 1] generiert, kannst du nicht sicher sein, dass p_random() * size nicht size wird - Rundungsfehler halt.

Sofern size nicht mehr signifikante Bits hat als die Mantisse der Zufallszahl (also typischerweise 53 bit für double), sollte das nicht passieren. Und falls size größer ist, kann sowieso nicht jede Ganzzahl im relevanten Intervall entstehen - dann muss ohnehin anders vorgegangen werden.

[Klaus82]

Also ich habe mit meinen begrenzten C++ Fähigkeiten noch einmal über diese Problematik nachgedacht.
Soweit ich das überblicke stehen die beiden Anfordungen kontraproduktiv gegenüber:
Zum Einen möchte ich einen Indexzugriff, zum anderen auch beliebige dynamisch Elemente löschen können

Von meinem Verständnis her sind die Elemente in vector komplexer angelegt, als z.B. in einer Liste. Dort kennt jedes Element ja nur seinen Vordermann und Nachfolger.
Um einen Indexzugriff zu ermöglichen benötige ich weitere Informationen, um das Element n schnell finden zu können.

Und das ist auch das Problem beim Löschen. Wenn ich nun das Element n löschen will, so muss ich die komplexe Anordnung des vectors aufbrechen, das Element löschen und anschließend müssen die übrigen Elemente neu angeordnet werden, um wieder schnellen Indexzugriff zu erlauben.

Bei einer Liste geht das ganze schneller, da ich lediglich die Adressen des Vordermanns und Nachfolger entsprechend vergeben muss. Also der Nachfolger des Elements wird der Nachfolger des Vordermanns und vice versa. Nicht viel Aufwand.

Jetzt habe ich bei meinem vector zwei Möglichkeiten die ganzen Elemente zu durchlaufen:

Index:

for(unsigned int i = 0; i < vector.size(); ++i)
{
  vector[i] // do something
}

Jetzt muss ich beim Löschen eines Elements natürlich auf den Index i aufpassen. Also wenn ich mit der Zeit beim Index i = 17 angekommen bin und entscheide, dass dieses Element gelöscht werden muss, welches Element wird denn dann als nächstes bearbeitet nach dem ++i der for-Schleife?
Spontan würde ich sagen, dass die übrigen Elemente 'nachrutschen', sodass der Nachfolger von i = 17 dann das Element 17 ist. D.h. nach der Aktion ++i wäre ich schon bei i = 18 und hätte somit ein Element übersprungen?

Ich hatte auch überlegt, die Indizes der zu löschenden Elemente separat zu speichern, sodass ich anschließend nach dem Durchlauf das Löschen durchführen kann.
Das Problem ist doch dabei wieder nur, sobald ein Element gelöscht ist, sind die ganzen übrigen gespeicherten Indizes falsch, weil die Indexnotation um ein Element verschoben ist.

Also auch Müll!

Iterator:

for(vector::iterator iter = vector.begin(); iter != vector.end(); ++iter)
{
 iter // do something
}

Hierbei hatte ich mir sogar noch was ganz anderes überlegt, sodass ich sogar komplett auf den Vektor verzichten kann.

Denn während bei der Indexnotation die Problematik das Löschen ist, ist die Problematik bei einer Liste o.ä. eben der fehlende Indexzugriff. Denn ich will eine Eigenschaft eines vorher gelöschten Objekts auf ein zufälliges restliches Objekt verteilen.
Nachdem ich aber bei Listen keinen Indexzugriff habe, kann ich das zufällig bestimmte Element n aber nur finden, indem ich vom Start ausgehend n Element entlangehe - und das dauert!

Also habe ich mir überlegt, diese Übertragung auf ein zufällig bestimmtes Element für den nächsten Durchlauf aufzuheben.
Sprich ich lösche ein Element und speichere eine Eigenschaft. Dann bestimme ich ein zufälliges Element, dass diese Eigenschaft erhalten soll und speichere dies in einer separaten Liste (alle Eigenschaften werden sortiert, also nehme ich beser ein Set?)

Und beim nächsten Durchlauf läuft ein Zähler mit, der vergleicht ob das aktuelle Element die gleiche Nummer trägt wie das zufällig bestimmte und falls ja - wird die Eigenschaft übertragen.

Damit spare ich mir das mühselige Durchlaufen, um das n. Element zu erreichen, da ich es auf den nächsten Durchlauf verschiebe, wo die ganze Liste sowieso durchgegangen wird.

Vielen Dank an alle, die bis zum Ende gelesen haben.

Viele Grüße,

Klaus.