Wie funktioniert std::map



  • Mich interresiert schon seit langem wie die std::(unordered_)map genau funktioniert.
    Der Quellcode der std ist zimlich schwer zu lesen deswegen hoffe ich jemand könnte mir algemein erklären( oder über einen link erklären lassen)
    wie sie genau funktioniert.

    Speziell interessiert mich wie das gefragte Element gefunden wird und wie es intern verwaltet wird.

    Die frage beschäftigt mich seit ich irgendwo, auf diesen Code gestoßen bin:

    T1 Candidate[N]; // ab welchem N lohnt sich eine Map definitiv?
    T2 Result[N];
    T2 Default;
    ...
    T1 toFind;
    ...
    int I=0;
    for( ; (I<N); ++I )
    {
      if( Candidate[I] == toFind ) break;
    }
    if(I==N)
    {
      return Default;
    }
    else
    {
      return Result[I];
    }
    


  • Normalerweise als Rot-Schwarz-Baum.



  • kann man ganz simpel nicht einach 2 gleich grosse array nebeneinander erstellen (alos nur bildlich gesprochen) und in dem einen den key und in dem anderen den value speichern?! natürlich beim gleichen index...



  • Skym0sh0 schrieb:

    kann man ganz simpel nicht einach 2 gleich grosse array nebeneinander erstellen (alos nur bildlich gesprochen) und in dem einen den key und in dem anderen den value speichern?! natürlich beim gleichen index...

    Klar.
    Aber die Suchzeiten (evtl auch Einfüge- und Löschzeiten) werden lang und länger, wenn die Arrays groß und größer werden. Irgendwann lohnt es sich, Bäume oder ähnliche Strukturen zu benutzen.


  • Mod

    Skym0sh0 schrieb:

    kann man ganz simpel nicht einach 2 gleich grosse array nebeneinander erstellen (alos nur bildlich gesprochen) und in dem einen den key und in dem anderen den value speichern?! natürlich beim gleichen index...

    Und wie findest du die Schlüssel effizient? Der Zugriffsoperator von map muss laut Standard mindestens logarithmisch in der Größe sein (oder besser, aber das ist wohl schwerlich machbar.).

    edit: Nur noch 6 Sekunden langsamer als volkard. Bald hole ich dich ein 😃 .



  • das war ja erstmal nicht die frage
    laufzeitkomplexität hab ich noch nicht bedacht, klar ist das langsam

    aber um ehrlich zu sein hab ich mich noch nie mit bäumen beschäftigt und an sie heran getraut (und das als informatik student!!!)


  • Mod

    Skym0sh0 schrieb:

    aber um ehrlich zu sein hab ich mich noch nie mit bäumen beschäftigt und an sie heran getraut (und das als informatik student!!!)

    Na dann wird's aber Zeit! Bäume sind ganz einfach und eigentlich Schulstoff. Sowohl biologisch als auch informatisch.



  • std::unordered_map funktioniert mit Hashtables. Dabei wird ein Algorithmus benutzt, um z.B. aus einem std::string eine Hash-Zahl zu generieren. Diese Hash-Zahl ist für diesen String immer gleich. Es kann auch vorkommen, dass mehrere Strings die gleiche Hash-Zahl besitzen. Optimalerweise sollten aber ähnliche Strings wie "1", "2", "3" oder "abcd", "dcba" nicht die gleiche Hash-Zahl besitzen. Je nach Anzahl der Elemente wird dann ein Array erstellt, das die Paare am Index ihrer Hash-Zahl speichert. Falls mehrere Keys den gleichen Hash-Wert besitzen, so werden sie in einer Liste aneinandergehängt und müssen dann noch abgesucht werden. Wird die Anzahl der Elemente vergrößert, so wird ggf. auch die Hash-Tabelle vergrößert, damit die Elementlisten nicht zu lange werden.
    Da diese map einen Algorithmus für den Key-Typ benötigt, funktioniert sie logischerweise nicht mit jedem Typ. Am üblichsten ist aber die Benutzung mit Strings.
    So bietet sich bei einigermaßen effektiver Nutzung eine Komplexität von O(1), d.h. die std::unordered_map braucht immer gleich lange zur Suche eines Elements, egal, wie viele Elemente darin enthalten sind.


Log in to reply