Die C ++ STL-Klasse std :: map implementiert O (log (n)) Look-Up unter Verwendung eines Binärbaums. Aber bei Bäumen ist nicht sofort klar, wie ein Iterator funktionieren würde. Was bedeutet der ++ Operator eigentlich in einer Baumstruktur? Während das Konzept des "nächsten Elements" eine offensichtliche Implementierung in einem Array hat, ist es für mich in einem Baum nicht so offensichtlich. Wie würde man einen Tree Iterator implementieren?
Bei einem Inorder-Traversal (wahrscheinlich auch für andere) können Sie, wenn Sie in Ihren Knoten einen Parent-Zeiger haben, eine nicht-rekursive Traversierung durchführen. Es sollte möglich sein, nur zwei Zeiger in Ihrem Iterator zu speichern: Sie brauchen eine Angabe, wo Sie sind, und Sie werden wahrscheinlich (ich mache nicht die Forschung jetzt) etwas wie einen "vorherigen" Zeiger brauchen, damit Sie herausfinden können Ihre aktuelle Bewegungsrichtung (dh muss ich in den linken Teilbaum gehen, oder bin ich gerade von ihm zurückgekommen).
"Previous" ist wahrscheinlich etwas wie "parent", wenn wir gerade den Knoten eingegeben haben; "links", wenn wir vom linken Teilbaum zurückkommen, "rechts", wenn wir vom rechten Teilbaum zurückkommen, und "selbst", wenn der letzte Knoten, den wir zurückgaben, unser eigener war.
Betrachten Sie die Menge aller Elemente in der Map, die nicht kleiner als das aktuelle Element sind, die auch nicht das aktuelle Element sind. Das "nächste Element" ist das Element aus dieser Menge von Elementen, das kleiner ist als alle anderen Elemente in dieser Menge.
Um eine Karte zu verwenden, müssen Sie einen Schlüssel haben. Und dieser Schlüssel muss eine Operation "weniger als" implementieren. Dies bestimmt die Art und Weise, wie die Map erstellt wird, sodass die Operationen Suchen, Hinzufügen, Entfernen, Inkrementieren und Dekrementieren effizient sind.
Im Allgemeinen verwendet die Map intern einen Baum.