C++ std :: unordered_map Komplexität

Question

Ich habe hier bei Stackoverflow viel über unordered_map(C++ 11)zeit Komplexität zu lesen, aber ich habe nicht die Antwort für meine Frage gefunden.

Nehmen wir an, die Indizierung durch integer (nur zum Beispiel):

Insert/an Funktionen arbeiten ständig (im Durchschnitt Zeit), so dass dieses Beispiel würde O nehmen (1)

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

Was ich Interessant ist, 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 jeder gespeicherte Wert nur einmal zugegriffen wird (oder zweimal oder Konstant mal) Dies würde bedeuten, dass die Iteration durch alle Werte in der N-wertigen Karte O (N) erfolgt. Die andere Möglichkeit ist, dass mein Beispiel mit den Schlüsseln {1,10,100000} bis zu 1000000 Iteration dauern könnte (wenn durch Array dargestellt)

Gibt es einen anderen Container, der linear durchlaufen werden kann und Wert, der durch gegebenen Schlüssel ständig zugegriffen wird ?

Was würde ich wirklich brauchen, ist (Pseudo-Code)

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 der Struktur die ich brauche?

Integer Indexierung ist ausreichend, durchschnittliche Komplexität auch.

Answer 1

Unabhängig davon, wie sie implementiert werden, bieten Standardcontainer Iteratoren, die die Iteratoranforderungen erfüllen. Das Inkrementieren eines Iterators muss eine konstante Zeit sein, so dass das Iterieren durch alle Elemente des beliebigen Standardcontainers O (N) ist.

Answer 2

Es gibt ein paar verschiedene Möglichkeiten, wie eine Hash-Tabelle implementiert werden kann, und ich schlage vor, Sie lesen mehr über diese, wenn Sie interessiert sind, aber die beiden wichtigsten sind durch Verkettung und offene Adressierung.

Im ersten Fall haben Sie ein Array von verknüpften Listen. Jeder Eintrag im Array kann leer sein, und jedes Element in der Hashtabelle befindet sich in einem Bucket. Also läuft die Iteration das Array hinunter und geht jede nicht leere Liste darin hinunter. Offensichtlich O (N), könnte aber je nach Zuordnung der verknüpften Listen möglicherweise sehr ineffizient sein.

Im zweiten Fall haben Sie nur ein sehr großes Array, das viele leere Slots haben wird. Hier ist die Iteration wiederum klar linear, könnte aber ineffizient sein, wenn die Tabelle größtenteils leer ist (was für Nachschlagezwecke sein sollte), weil die Elemente, die tatsächlich vorhanden sind, sich in verschiedenen Cache-Zeilen befinden.

So oder so, Sie werden lineare Iteration haben und Sie werden jedes Element genau einmal berühren. Beachten Sie, dass dies auch für std::map gilt, die Iteration wird auch dort linear sein. Aber im Fall der Karten ist die Iteration definitiv viel weniger effizient als die Iteration eines Vektors, also behalte das im Hinterkopf. Wenn Ihr Anwendungsfall BEIDE schnelle Suche und schnelle Iteration erfordert, wenn Sie alle Ihre Elemente im Voraus einfügen und nie löschen, könnte es viel besser sein, sowohl die Karte als auch den Vektor zu haben. Nimm den zusätzlichen Platz für die zusätzliche Leistung.

Answer 3

Die Komplexitätsgarantien aller Standardcontainer sind in der C++ Standard angegeben.

std::unordered_map Der Elementzugriff und die Elementeinfügung müssen im Durchschnitt O(1) im Durchschnitt und O(N) im schlimmsten Fall sein (vgl.Abschnitte 23.5.4.3 und 23.5.4.4; Seiten 797-798).

Eine bestimmte Implementierung (dh die Implementierung der Standardbibliothek durch einen bestimmten Anbieter) kann die gewünschte Datenstruktur auswählen. Um jedoch dem Standard zu entsprechen, muss ihre Komplexität mindestens wie angegeben sein.