Ich habe viel darüber gelesenunordered_map (c ++ 11) zeitliche Komplexität hier bei stackoverflow, aber ich habe keine antwort auf meine frage gefunden.

Nehmen wir an, dass die Indizierung durch eine Ganzzahl erfolgt (nur zum Beispiel):

Insert / at-Funktionen arbeiten konstant (in durchschnittlicher Zeit), daher würde dieses Beispiel O (1) annehmen.

std::unordered_map<int, int> mymap = {
            { 1, 1},
            { 100, 2},
            { 100000, 3 }
};

Ich bin gespannt, wie lange es dauert, alle in der Karte gespeicherten (unsortierten) Werte zu durchlaufen - z.

for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }

Kann ich davon ausgehen, dass auf jeden gespeicherten Wert nur einmal (oder zweimal oder zu konstanten Zeiten) zugegriffen wird? Dies würde bedeuten, dass sich die Iteration durch alle Werte in der N-wertigen Abbildung O (N) befindet. Die andere Möglichkeit besteht darin, dass mein Beispiel mit den Schlüsseln {1,10,100000} bis zu 1000000 Iterationen dauern kann (wenn es durch ein Array dargestellt wird).

Gibt es einen anderen Container, der linear iteriert werden kann und auf den der angegebene Schlüssel ständig zugreift?

Was ich wirklich brauchen würde, ist (Pseudocode)

myStructure.add(key, value) // O(1)
value = myStructure.at(key) // O(1)
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values

Ist std :: unordered_map die Struktur, die ich brauche?

Die Indizierung ganzer Zahlen ist ausreichend, ebenso die durchschnittliche Komplexität.