Was passiert beim Einfuegen in eine Datenstrucktur

l'abra d'or

qw schrieb:

kann mir mal einer ein kleines Beispiel geben ?

Hab ich deinen Code 1:1 übernommen und aus dem Node im Container ein Node* gemacht undZugriffe und Einfügen so abgeändert dass es passt.

weil vector<*Node> hatte ich erst ausprobiert, aber das geht nicht

Schreibt man da dann normalerweise dazu, WAS nicht geht (Fehler und Code)

Wenn du möchtest dass dir jemand etwas zeigt wäre ein kleines "Bitte" nicht schlecht, sonst sind >99,9% der Leute nicht gewillt nochmal zu antworten.

quessstion schrieb:

vector<Node> asd;
	hash_map<int,Node> bla;
Mache, und ich fuege das Node in eine der Datenstruckturen ein, warum ist es dann nicht mehr das gleiche Node so dass ich es von ausserhalb veraendern kann ?
Sprich, bei mir komm beim cout beides mal 1 raus, das heißt doch das Node* vector und hash_map nicht auf den gleichen Speicherbereich zeigen,

Die "zeigen" gar nicht. Die Datenstruktoren speichern keine Zeiger auf Deine Objekte, sondern Kopien. Du hast hier sogar ein Speicherleck, da Du ein Objekt mit new erzeugt, es aber nirgendswo wieder mit delete gelöscht wird.

Dich überrascht das vielleicht, weil Du von anderen Sprachen etwas anderes gewöhnt bist. Anere Sprachen (wie zB Java) nutzen implizit Indirektion. In C++ erreichst Du das durch explizite Verwendung von Zeigern oder anderen "Handles".

Probier mal folgendes:

list<Node> nodelist;
    typedef list<Node>::iterator listiter_t;

    hash_map<int,listiter_t> bla;
    nodelist.push_front( Node(23) );
    bla[23] = nodelist.begin();

    bla[23]->num = 42;

    nodelist.erase(bla[23]);
    bla.erase(23);

Hier werden die Objekte in der Liste gespeichert und verwaltet. Das erspart Dir die explizite Verwaltung der Lebenszeit -- kein new und kein delete gibt es hier. Wenn die Liste zerstört wird, werden auch automatisch alle Node-Objekte zerstört, die zur Liste gehören. Die Map speichert hier eine Zuordnung von int zu einem List-Iterator, über den man das Node-Objekt erreichen kann.

Warum list statt vector? Nur std::list garantiert Dir, dass, wenn Du neue Objekte hinzufügst oder irgendwelche Objekte aus der Liste löscht, sich die Adressen der anderen Objekte nicht ändert und die anderen Iteratoren noch gültig bleiben. Ein std::vector dagegen kopiert die Elemente schonmal um, wenn neue Elemente hinzugefügt werden sollen aber die Kapazität des aktuellen Vektors nicht ausreicht.

Alternativ könnte man boost::shared_ptr benutzen:

vector<shared_ptr<Node> > nodelist;
    hash_map<int,shared_ptr<Node> > bla;

    shared_ptr<Node> temp ( new Node(23) );
    nodelist.push_back( temp );
    bla[23] = & nodelist.back();

Auch hier wird wieder der Verwaltungsaufwand der Lebenszeit der Node-Objekte abgegeben, in diesem Fall an shared_ptr.

Das Problem bei einem Ansatz wie diesem hier:

vector<Node*> nodelist;
    hash_map<int,Node*> bla;

    nodelist.push_back( new Node(23) );
    bla[23] = nodelist.back();

dass man sich hier selbst um's "Aufräumen" kümmern muss.

krümelkacker schrieb:

Alternativ könnte man boost::shared_ptr benutzen:

vector<shared_ptr<Node> > nodelist;
    hash_map<int,shared_ptr<Node> > bla;

    shared_ptr<Node> temp ( new Node(23) );
    nodelist.push_back( temp );
    bla[23] = & nodelist.back();

Upps, die letzte Zeile sollte heißen

bla[23] = temp;

(war ein copy & paste Fehler)

l'abra d'or schrieb:

qw schrieb:

kann mir mal einer ein kleines Beispiel geben ?

Hab ich deinen Code 1:1 übernommen und aus dem Node im Container ein Node* gemacht undZugriffe und Einfügen so abgeändert dass es passt.

weil vector<*Node> hatte ich erst ausprobiert, aber das geht nicht

Schreibt man da dann normalerweise dazu, WAS nicht geht (Fehler und Code)

Oh man, ja vector<*Node> kann ja auch nicht gehen, vector<Node*> geht wunderbar, das hat mich jetzt viel Zeit gekostet.

Wenn du möchtest dass dir jemand etwas zeigt wäre ein kleines "Bitte" nicht schlecht, sonst sind >99,9% der Leute nicht gewillt nochmal zu antworten.

Hey das sollte nicht fordernd oder so klingen, ich bin hier fuer jede Antwort wirklich sehr dankbar.
Aber du hast schon recht ein Bitte fehlt, aber du bekommst jetzt auf jeden Fall ein Danke!

krümelkacker schrieb:

quessstion schrieb:
vector<Node> asd;
	hash_map<int,Node> bla;
Mache, und ich fuege das Node in eine der Datenstruckturen ein, warum ist es dann nicht mehr das gleiche Node so dass ich es von ausserhalb veraendern kann ?
Sprich, bei mir komm beim cout beides mal 1 raus, das heißt doch das Node* vector und hash_map nicht auf den gleichen Speicherbereich zeigen,
Die "zeigen" gar nicht. Die Datenstruktoren speichern keine Zeiger auf Deine Objekte, sondern Kopien. Du hast hier sogar ein Speicherleck, da Du ein Objekt mit new erzeugt, es aber nirgendswo wieder mit delete gelöscht wird.

Dich überrascht das vielleicht, weil Du von anderen Sprachen etwas anderes gewöhnt bist. Anere Sprachen (wie zB Java) nutzen implizit Indirektion. In C++ erreichst Du das durch explizite Verwendung von Zeigern oder anderen "Handles".

Probier mal folgendes:
list<Node> nodelist;
    typedef list<Node>::iterator listiter_t;

    hash_map<int,listiter_t> bla;
    nodelist.push_front( Node(23) );
    bla[23] = nodelist.begin();

    bla[23]->num = 42;

    nodelist.erase(bla[23]);
    bla.erase(23);
Hier werden die Objekte in der Liste gespeichert und verwaltet. Das erspart Dir die explizite Verwaltung der Lebenszeit -- kein new und kein delete gibt es hier. Wenn die Liste zerstört wird, werden auch automatisch alle Node-Objekte zerstört, die zur Liste gehören. Die Map speichert hier eine Zuordnung von int zu einem List-Iterator, über den man das Node-Objekt erreichen kann.

Warum list statt vector? Nur std::list garantiert Dir, dass, wenn Du neue Objekte hinzufügst oder irgendwelche Objekte aus der Liste löscht, sich die Adressen der anderen Objekte nicht ändert und die anderen Iteratoren noch gültig bleiben. Ein std::vector dagegen kopiert die Elemente schonmal um, wenn neue Elemente hinzugefügt werden sollen aber die Kapazität des aktuellen Vektors nicht ausreicht.

Alternativ könnte man boost::shared_ptr benutzen:
vector<shared_ptr<Node> > nodelist;
    hash_map<int,shared_ptr<Node> > bla;

    shared_ptr<Node> temp ( new Node(23) );
    nodelist.push_back( temp );
    bla[23] = & nodelist.back();
Auch hier wird wieder der Verwaltungsaufwand der Lebenszeit der Node-Objekte abgegeben, in diesem Fall an shared_ptr.

Das Problem bei einem Ansatz wie diesem hier:
vector<Node*> nodelist;
    hash_map<int,Node*> bla;

    nodelist.push_back( new Node(23) );
    bla[23] = nodelist.back();
dass man sich hier selbst um's "Aufräumen" kümmern muss.

Ja ums aufraeumen muss ich mich sowieso nicht kuemmern, da mein Programm nachdem der Graph aufgebaut ist nur noch eine Wegsuche macht und dann beendet wird. Der Speicher wird doch dann sowieso wieder frei gegeben oder ?

Fellhuhn

An sich ja, aber man sollte dennoch nicht schlurig sein und sowas immer gleich richtig machen. Ist ja auch nicht wirklich Arbeit.

l'abra d'or

Und irgendwann muss dein Destruktor DOCH noch mal wichtige Aufgaben erledigen - und du bist es gewohnt dass dein Speicher automatisch vom OS freigegeben wird und löschst deine Objekte immer noch nicht selbständig

Fellhuhn

Warum auf Klo gehen wenn die Windel so schön alles hält?

Fellhuhn schrieb:

Warum auf Klo gehen wenn die Windel so schön alles hält?

wie recht du doch hast

ich habe jetzt aber ein weiteres Problem, ich habe einen Iterator ueber eine HashMap

for(hash_map<int,Node*>::iterator it = allNodes.begin(); it != allNodes.end();it++) {
  cout << it->num << endl;
}

Er laeuft bis ganz ans Ende, gibt also noch die letzte Zahl aus und bricht dann einfach ab, ohne Fehlermeldung. Mein debugger sagt Segmentation fault also irgendwas mit ueber Speicherbereich gelesen?!

<terminated>gdb/mi (1/27/10 3:40 PM) (Exited. Signal 'SIGSEGV' received. Description: Segmentation fault.)

wie kann den sowas passieren also irgendwie ist it++ dann ueber dem Speicherbereich und nicht allNodes.end() oder kann es sein das es allNodes.end() nicht gibt ?

Fellhuhn

Weiß ja nicht wie der Rest deines Codes aussieht, man benutzt aber eigentlich ++it statt it++.

Hab ich mal probiert, aendert aber auch nichts. Das ist ja eh eine eigenstaendige Anweisung am Ende einer Iteration.

So sieht der Rest der Schleife aus, das einzige was ich mache sind Zuweisungen, ich loesche nichts und veraendere auch nichts was ich in der Schleife benutze.

for(hash_map<int,Node*>::iterator it = allNodes.begin(); it != allNodes.end();++it) {
		cout << it->first << " ";
		for(hash_map<int,Node*>::iterator it1 = it->second->cameFrom.begin(); it1 != it->second->cameFrom.end();++it1) {
			cout << it1->first << " ";
			if(it1->second->away == 0) {
				it1->second->away = it->second->away+1;
				it1->second->from = it->second;

				newAllNodes[it1->first] = it1->second;
			}
 		}
		cout << "ENDE" << endl;

	}
	cout << "ENDE ALL" << endl;

Ich habe gerade nochmal was ausprobiert, ich mache diese Berechnung in einer Methode also

hash_map<int,Node*> allNodes;

vonDateiEinlese(allNodes);

findWay(allNodes);

findWay(hash_map<int,Node*> allNodes) {
	hash_map<int,Node*> newAllNodes;

	for(hash_map<int,Node*>::iterator it = allNodes.begin(); it != allNodes.end();++it) {
		cout << it->first << " ";
		for(hash_map<int,Node*>::iterator it1 = it->second->cameFrom.begin(); it1 != it->second->cameFrom.end();++it1) {
			cout << it1->first << " ";
			if(it1->second->away == 0) {
				it1->second->away = it->second->away+1;
				it1->second->from = it->second;

				newAllNodes[it1->first] = it1->second;
			}
 		}
		cout << "ENDE" << endl;

	}
	cout << "ENDE ALL" << endl;
}

Wenn ich die Berechnung die ich eigentlich in der Methode mache, gleich ohne Methode mache funktioniert es, habe ich da jetzt schon wieder was mit dem Uebergeben von Objekten falsch gemacht ?

Sebastian Pizer

xasew schrieb:

for(hash_map<int,Node*>::iterator it = allNodes.begin(); it != allNodes.end();it++) {
  cout << it->num << endl;
}
Er laeuft bis ganz ans Ende, gibt also noch die letzte Zahl aus und bricht dann einfach ab, ohne Fehlermeldung. Mein debugger sagt Segmentation fault also irgendwas mit ueber Speicherbereich gelesen?!
<terminated>gdb/mi (1/27/10 3:40 PM) (Exited. Signal 'SIGSEGV' received. Description: Segmentation fault.)
wie kann den sowas passieren also irgendwie ist it++ dann ueber dem Speicherbereich und nicht allNodes.end() oder kann es sein das es allNodes.end() nicht gibt ?

Nein. Viel wahrscheinlicher ist, dass Du ungültige Zeiger (oder Nullzeiger) in der map hast, die Du nicht dereferenzieren darfst, was Du aber mit "it->num" tust.

xaer schrieb:

findWay(hash_map<int,Node*> allNodes) {

Dir ist klar, dass allNodes hier eine lokale Kopie der Argument-Map ist, ja? Und dann zeigen die Elemente der Kopie auch noch auf dieselben Knoten-Objekte (sharing), die Du in der Funktion veränderst.

+-Node--+       +-Node--+
         | daten |       | daten |
         +-------+       +-------+
           A   A           A   A
           |   |           |    \_____________________________
           |    \__________|__________________                \
           |               |                  \                |
+-map------+---------------+-----+  +-map------+---------------+-----+
|          |               |     |  |          |               |     |
| +-pair-------+  +-pair-------+ |  | +-pair-------+  +-pair-------+ |
| | int, Node* |  | int, Node* | |  | | int, Node* |  | int, Node* | |
| +------------+  +------------+ |  | +------------+  +------------+ |
|                                |  |                                |
+--------------------------------+  +--------------------------------+
      (Argument von findWay)            (lokale Kopie in findWay)

Da kriegt man ja ganz schnell 'nen Knoten im Kopf. Ich muss gestehen, ich verstehe die Funktion findWay nicht. Vielleicht muss man dazu aber auch die Definition von Node kennen.

Ja, das ist auch ein bischen gekuerzt weil die Methode 2 Seiten lang ist.

Ich habe aber den Fehler gefunden.

Ich hatte ein

if(allNodes[end]) {

}

zum ueberpruefen ob der Endknoten enthalten ist benutzt, das Problem ist aber das die HashMap dann falls "end" nicht enthalten ist fuer den Key einen NullPointer anlegt und diesen dann zurueck gibt.
Der zerballert mir natuerlich dann auch die Iteration, das tragische ist aber das es ja manchmal funktioniert, naemlich immer dann wenn der Endknoten wirklich drin war das hat die Fehlersuche sehr erschwert...

Also waere es hier sinnvoller mit Pointern zu arbeiten ? gerade wenn es auf die Geschwindigkeit ankommt oder ?

Sebastian Pizer

defaef schrieb:

Also waere es hier sinnvoller mit Pointern zu arbeiten ? gerade wenn es auf die Geschwindigkeit ankommt oder ?

Es wäre sinnvoll, eine vernünftige Datenstruktur anzulegen und die auch soweit zu kapseln, dass man als Nutzer nicht viel falsch machen kann. Zum Bleistift einen "Graph"-Typen anlegen, der entweder nicht kopierbar ist, oder sich "regulär" verhält (--> "tiefe Kopie" wie es std::list, std::map etc auch machen).

Vielleicht kannst Du Dir von den Abstraktionen aus BGL etwas abgucken oder sogar einfach BGL benutzen.