[STL] Vector iterator an Position springen

[Neugieriger Mitleser]

SeppJ schrieb:

DocShoe schrieb:

Edit:
Sach ma Sepp, hast du´n Trigger auf das Forum? Ich hab den Eindruck, du schreibst Antworten 4.3ns nachdem ein Benutzer einen Beitrag geschrieben hat.

In letzter Zeit sind aber immer seldon und cooky451 vor mir. Ich war auch schon einmal besser

Müsst ihr nicht arbeiten oder seid ihr in Rente?

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