hash_map

Abend,

Ich brauche folgende Struktur: Ich habe Knoten (Node*) und jeder davon hat einen eindeutigen Namen (string); es kann also niemals 2 Node mit dem gleichen Namen geben. Über den Namen möchte ich dann auf den Node* zugreifen. Zusätzlich soll über einen Index auf die Node* zugegriffen werden. Also wenn ich in die Struktur 2 Node hinzufüge (zb. "Knoten1" => Node*, "EinAndererKnoten" => Node*), dann soll Index 0 den "Knoden1" liefern und Index 1 den Knoten "EinAndererKnoten".

Ich dachte zunächst an std::map, aber ich glaube std::map sortiert und das würde ja meinen Index-Zugriff unmöglich machen, oder?

Also habe ich mir stdext::hash_map angeschaut (ich benutze VS 2008) und einen kleinen Test geschrieben:

stdext::hash_map<std::string, int> hm;

	hm["B"] = 2;
	hm["Z"] = 33;
	hm["A"] = -2;
	hm["AKEKFE"] = 4923;

	stdext::hash_map<std::string, int>::iterator it = hm.begin();

	for(; it != hm.end(); ++it) {
		std::string s = it->first;
		int j = it->second;
	}

Da gibt es nun 2 Dinge, die ich nicht verstehe:
1. Im Debugger wird mir folgender Inhalt von hm angezeigt:

[4](("A",-2),("B",2),("Z",33),("AKEKFE",4923))

Wieso ist das hier sortiert? Ich dachte hash_map sortiert nicht?

2. Wenn ich den Code ausführe, hat s in der Schleife folgende Werte:
"B", "Z", "AKEKFE".
Das raff ich nicht. Offenbar sind die Werte also doch unsortiert. Wieso zeigt der Debugger sie dann sortiert an? Und wieso ist "A" verschwunden?

Ist stdext::hash_map bei meinem Problem überhaupt die richtige Struktur?

Danke!

Die Ansicht im Debugger sagt doch nichts darüber aus ob die Einträge sortiert sind, schon gar nicht bei 4 Einträgen.

Allerdings verstehe ich nicht was dir die Hashtabelle bei deinem Problem nützt, du willst doch offensichtlich zwei Zuordnungen: Index |--> Node und Name |--> Node. Das einfachste hierfür wäre zwei std::maps zu nehmen, einmal std::map<int, Node*> und einmal std::map<std::string, Node*>.

otze

Wieso ist das hier sortiert? Ich dachte hash_map sortiert nicht?

Sicher tut sie es das. Nur nicht nach einer normalen Sortierordnung.

Schau dir mal den Artikel an, dann verstehst du es: http://en.wikipedia.org/wiki/Hash_table

Die Lösung deines Problems ist, dass du 2 Container brauchst. Der erste speichert die Elemente in einem Vektor (für Indexzugriff), und dazu eine Map, die zu jedem string den passenden Index im vector speichert.