Der Container std :: set (oder std :: map) ist eine Datenstruktur, die STL bereitstellt. In fast allen Compilern ist es als ein R & amp; B-Baum implementiert mit garantierter log (n) -Einfügung, Such- und Entfernungszeit.
In einem rot-schwarzen Baum werden die Elemente basierend auf dem "less" -Operator des gespeicherten Elements sortiert. Wenn also eine Wurzel N + 1 ist, befindet sich N auf dem linken Teilbaum, während N + 2 auf dem rechten Teilbaum liegt, und diese Ordnung wird durch den weniger Operator bestimmt.
Meine Frage ist, wenn Sie den folgenden Code ausführen:
%Vor%Die Elemente werden in einer sortierten Reihenfolge zurückgegeben. Wie kann dies angesichts der Tatsache, dass die zugrunde liegende Datenstruktur ein rot-schwarzer Baum ist, möglich sein? Gibt es eine separate verknüpfte Liste, die gespeichert werden kann, um vom äußersten linken Teilbaum zum am weitesten rechts liegenden Teilbaum zu iterieren? Wenn nicht, was ist der Mechanismus hinter dieser Implementierung mit einem R & amp; B-Baum?
Wir können eine definitive Antwort finden, indem wir uns den Quellcode anschauen (in diesem Fall libstdc ++ 5.2.1). So sieht ein Baumknoten aus:
%Vor%Jeder Knoten enthält also eine Farbe und Zeiger auf seine Eltern und seine linken und rechten Kinder. Inkrementieren wird implementiert als:
%Vor%Das tatsächliche Inkrement befindet sich nicht mehr in den öffentlichen Headern, sondern im kompilierten Teil der Bibliothek:
%Vor%Letztendlich handelt es sich also um eine Lehrbuchimplementierung des Traversierens von Bäumen: Der Iterator hält einen Zeiger auf den "aktuellen" Knoten, und um zum nächsten Knoten zu gelangen, geht er in den Baum hinein, solange er vom rechten Kind kommt . Wenn es vom linken Kind kommt, wird es zum ganz linken Kindknoten des rechten Kindes absteigen.
Der Iterator führt eine [In-Order-Tiefen-zuerst-Baum-Traversierung] durch. 1 Dies ist typischerweise implementiert in einem rekursiven Algorithmus. Da die Iterator-Verwendung nicht rekursiv implementiert werden kann, behält der Iterator intern einen Stapel von dem, wo er gewesen ist, so dass er den Baum zurückgehen kann.
Update: Danke an Chris Dodd für den Hinweis, dass RB-Baumknoten Zeiger auf ihre Eltern haben, so dass der Iterator ihnen einfach bis zum nächsten Element folgen kann.