Wie funktioniert std::Map ?

[Terrat]

Hallo,
ich versuche gerade Map nachzuvollziehen und frage mich daher wie sie genau funktioniert. Ich habe schon einen Counter gefunden der die anzahl der Elemente festhält. Aber woher weiß er wo das 1 Element ist ? Und woher weiß es wo das 2 Element ist?
Ich habe es mir so vorgestellt, dass in der Map die Adresse des 1 Elementes steht, im 1 Element die Adresse des 2 Elementes steht und beim 2 Element die Adresse des 3 Elementes usw.. Und wenn z.B. ein Element gelöscht wird z.B. 2 das in 1 die Adresse dann auf 3 zeigt und 2 gelöscht wird. Aber ich kann in der Map einfach keine Adresse zum 1 Element finden. Also sehe ich das richtig oder funktioniert die Map anders ?

[th0rex]

std::map wird meistens als Rot-Schwarz-Baum implementiert. Kannst dir ja mal die libc++ Implementierung angucken.
da siehst du das was __base ist, und __tree wird als __base definiert (Zeile 856; wenn man drauf klickt möchte epvp einen nicht zu der Zeile bewegen, obwohl ich sie mit verlinkt habe). Alle Funktionen von map rufen eigentlich nur etwas von __tree auf. .