3. Kurze Frage zu STL map

Kurze Frage zu STL map

  • I

    Hallo,

    ich habe eine kleine Frage zum map-Container:
    Intern ist dieser ja ein Binärbaum.
    Wenn ich nun eine map vom typ map<int, myClass*> habe und immer neue Elemente einfüge, wobei der Schlüsselwert eine ID darstellt und dafür immer ein um 1 inkrementierter Wert genommen wird...

    (also

    // Dies ist nur Beispielcode, im Programm ist die konkrete Implementierung
// natürlich wesentlich komplexer
int id = 0;
myMap[id++] = new myClass();
myMap[id++] = new myClass();
myMap[id++] = new myClass();

    ... so wird ja der Binärbaum riesig, da der nächste Eintrag immer höher ist als die vorherigen und somit immer ein rechter Knoten angelegt wird. Die Wurzel im Binärbaum ist also 0, dann der erste rechte Knoten 1 etc. -> der Binärbaum entartet zu einem völlig unbalancierten Baum.
    Dadurch wird folglich auch das Suchen, ... innerhalb des Baumes ein langwieriger Prozess.

    Nun zur Frage:
    Ist die map intern so angelegt, dass ab und an eine Optimierung durchgeführt wird, also der Baum "balanciert" wird? Oder muss ich mich darum selbst kümmern?

    0
  • C

    Die schlechte Nachricht: Wie genau die map<> implementiert ist, legt der Standard nicht fest.

    Und nun die gute Nachricht: Der Standard legt fest, welche Laufzeitkomplexität wichtige map-Operationen haben dürfen. Und um diese einhalten zu können, brauchst du einen selbstbalancierenden Binärbaum (rot-schwarz-Bäume oder AVL-Bäume).

    (PS: Und als Nutzer bist du nicht einmal in der Lage, in die Arbeitsweise des Baums einzugreifen ;))

    0
  • L

    Die Map ist so spezifiziert, dass die Suche in logarithmischer Zeit stattfinden muss. Das ist bei einem total unbalancierten Baum nicht gegeben. Demnach muss die Implementierung um Standardkonform zu sein auf jeden Fall optimieren. Wie sie das macht, ist allerdings nicht vorgeschrieben (auch wenn es bei einem Binärbaum offensichtlich sein sollte).

    Die Implementierung vom gcc (jedenfalls in einer älteren Version die ich mal untersucht habe) verwendet z.B. einen RedBlack-Tree, der immer balanciert ist.

    0
  • I

    Wow, ok danke für die schnelle Antwort.

    Alles klar, dann muss ich mir darüber keine Gedanken mehr machen und kann getrost weiter an meinem Projekt arbeiten 🙂

    Bin eben noch in der Design-Phase und da kommen mir als C++-Anfänger ständig solche Fragen auf. Hey aber ich fang an C++ zu lieben; musste ich mich doch bis vor kurzem mit Basic-Sprachen und sogar noch mit Turbo-Pascal (man staune - selbst das lebt noch) herumplagen.

    Also vielen Dank nochmals, echt super Community in diesem Forum hier

    0
Anmelden zum Antworten