spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Es wird wahrscheinlich iteriert. map ist eine Klasse und verwaltet den Speicher intern. So gesehen hast du also ein Array mit strings (oder allem anderen) als indices.

Die unordered_map nutzt allerdings Hash Werte und greift damit "direkt" auf den Wert zu, wobei natürlich der Hash berechnet werden muss usw.

Der Zugriff auf das Element geschieht mit der Laufzeitkomplexität O(log n), wobei n die Anzahl der Einträge der Map ist. Also nein, es wird weder über alle iteriert ( O(n) ), noch der Wert direkt angewählt ( O(1) ). Logarithmisch ist aber ausreichend schnell für die meisten Anwendungsfälle einer Map.
std::unordered_map bietet im Schnitt konstante Zugriffszeit, im Worst Case aber O(n). Zudem müssen eventuell die Hashes neu berechnet werden bei einem insert.

Das hängt wohl davon ab ob Du viele Schreib- oder viele Lese-Operationen machst.
Der Logarithmus kommt aus der Art und Weise, wie eine Map aufgebaut ist - nämlich als Baum.:

Um E zu erreichen, musst Du maximal 4 Knoten untersuchen, obwohl 9 im Baum enthalten sind. Das wäre auch noch so, wenn an A, G, I, C oder H noch andere Elemente hängen würden. Wären alle Ebenen belegt, wären das 15 Knoten. Und dennoch müsstest Du immer maximal 4 untersuchen, um den richtigen zu finden. Log_2(15) ~= 4

Eine unordered_map ist anders aufgebaut und benutzt die Hashes als Indices für Direkt-Zugriff. Dafür muss beim Einfügen von Elementen aber eventuell diese Hash-Tabelle neu aufgebaut werden.

Welche Map für Deine Zwecke wirklich effizienter ist, wird letztlich ohnehin nur ein Profiling zeigen.

Verstehe ich es richtig, dass wenn man die unordered map (zum Anfang des Programms) einmal erstellt, ist diese besser geeignet, da der Zugriff in der Regel schneller ist ?

Erklärung: Es geht bei mir darum, dass ich eine Liste von Zeigern auf bestimmte Elemente haben möchte. Diese Elemente sind an verschiedenen Stellen und mit der Liste möchte ich zentralen und schnelleren Zugriff haben.

(Ich hoffe es ist okay, wenn ich die Frage hier poste, aber es ist ja im Endeffekt die gleiche Frage wie der Ersteller hatte).

Theoretisch schon, aber da ein Computer etwas komplexer ist solltest du trotzdem profilen.
Ich könnte mir gerade bei Zeigern gut vorstellen dass du kaum einen Vorteil hast, da du trotzdem CPU Cache Missmatches hast (ein Zeiger springt durch den RAM, da ist der Cache kaum noch effektiv).

Das wäre aber auch bei anderen Containern so, und da ich immer den nehmen würde, der den Anforderungen am besten entspricht (nach der Beschreibung aus der Doku) macht es hier wohl sinn.
Wenn nicht wirst du das dann sehen.

Die "std::unordered_map" braucht für die interenen Tabellen relativ viel Speicherplatz. Außerdem hängt immer von dem Hash-Algorithmus ab, wie gut sie wirklich funktioniert, das heißt, ob sie ihr versprochenes O(1) wirklich halten kann. Und durch den hohen Speicherplatzverbrauch kommt dann eben auch der bereits erwähnte Cache ins Spiel, der dir leicht einen Strich durch die Rechnung machen kann. Ein eindeutiges Urteil ist deshalb nicht so leicht zu fällen. Beim einmaligen Aufbau oder bei sehr wenigen Elementen kann sogar auch ein stink normales Array oder ein "std::vector" im Vorteil sein, der dann sortiert und mit "std::binary_search" zugegriffen wird, weil Allokationen und Cache dann gespart sind.

Nee das Problem bei Zeigern in Listen ist immer eher dass es Zeiger sind

CPU liest 4MB linear aus den RAM in den Cache, ab Adresse x.
CPU liest den Zeiger mit Adresse y aus der Map die jetzt im Cache liegt.
y ist weiter als 4MB von x weg, so dass die CPU zu y springt und ab da wieder 4MB liest -> Cache missmatch.

Bei einem normalem array (keine Zeiger) kann die CPU direkt weiter im Cache lesen.
Alles profilen. Wie Blue immer sagt.

Ich würde hier aus den zwei Gründen trotzdem die unordered_map nehmen:

1. die Daten werden am Anfang einmal eingelesen und dann nicht mehr verändert.
2. die Zugriffszeit soll gering sein.

Das entspricht den Vorteilen die in der Doku beschrieben werden. Also einfach nehmen und glücklich sein.
Wenns daran hakt einfach was anderes testen.