Public-Zugriff im Iterator



  • Na schön..., würde mir jemand eine Beispiel impelementierung einer find-Methode(einer Multimap), die einen Iterator zurückgibt, geben?



  • Entweder du gibst einfach 2 Iteratoren zurueck (Anfang und Ende des Bereiches, der den find erfeullt) oder du gibst einfach einen Iterator nur auf den Anfang zurueck, mit dem kann man dann ueber den Rest iterieren. Kannst du auch gern in jeder beliebigen STL Implementation nachschlagen.



  • Also, da mir nur vom Iterator aus ++(),=!() und * Operator zur verfügen stehen, Wüsste ich nur wie ich eine lineare Suchmethode erstellen könnte, was aber wiederrum nicht so gut ist. Ist es evtl. sinnvoll das die Datenstruktur von der Iteratorklasse "protected" erbt, damit man auf den inhalt des Iterators beschränkt zugreifen kann?



  • Ist das Problem eventuell, dass der Multimap ein Baum zugrunde liegt (von wegen Stack)?. Wenn ja, dann benötigt der Iterator meines erachtens lediglich einen Pointer auf den aktuellen Knoten im Baum. Man kann ohne Stack und Rekursion von einem Knoten in z.B. einem Binären Baum via In-Order-Traversierung zu seinem Vorgänger/Nachfolger "hangeln". Versuch's mal mit dem am weitesten rechts/links liegenden Knoten im linken/rechten Unterbaum, bzw. dem eines Vorfahren-Knoten, wenn der aktuelle keinen hat (falls ich grad so früh am morgen keinen Denkfehler drinhab ;)). Ansonsten wird in den Knoten von solchen Baum-Datenstrukturen auch oft noch ein Pointer auf den Vorgänger/Nachfolger mitgeführt - etwas mehr Buchführung beim Einfügen/Löschen, aber spart Dereferenzierungen und das "iterieren" wird nicht umständlicher als bei einer verketteten Liste.

    Finnegan



  • Finnegan schrieb:

    Ist das Problem eventuell, dass der Multimap ein Baum zugrunde liegt (von wegen Stack)?. Wenn ja, dann benötigt der Iterator meines erachtens lediglich einen Pointer auf den aktuellen Knoten im Baum. Man kann ohne Stack und Rekursion von einem Knoten in z.B. einem Binären Baum via In-Order-Traversierung zu seinem Vorgänger/Nachfolger "hangeln".

    Falsch. Man braucht mehr Informationen, zum Beispiel im Iterator den root-Zeiger oder einen history-Stack, oder im Baum Aufwärts- oder rechts-links-Zeiger.

    TGGC schrieb:

    Wie immer Unfug oder Thema verfehlt.

    Iteratorfan schrieb:

    ich schreibe gerade einen Iterator für eine MultiMap. Nun habe ich das Problem, das ich mehrere Public-Methoden im Iterator brauche, weil die Map z.b mit "find" darauf zugreifen muss. Ich glaube aber das man von außen keine Methoden vom Iterator aufrufen darf außer den Konstruktor. Ist das so?

    Fremde Leute "dürfen" nur das aufrufen, was in der Doku steht. Steht da kein it.getImplPtr(), dann "dürfen" sie das nicht. Das kannste gerne unterstützen, indem Du getImplPtr() private machast und die MuMa<Foo> zum offiziellen friend des MuMa<Foo>::Iterators erklärst.

    Aber normalerweise benutzt Du innerhalb der find()-Implementierung überhaupt keine Iteratoren, sondern bloß Zeiger.



  • volkard schrieb:

    Finnegan schrieb:

    Ist das Problem eventuell, dass der Multimap ein Baum zugrunde liegt (von wegen Stack)?. Wenn ja, dann benötigt der Iterator meines erachtens lediglich einen Pointer auf den aktuellen Knoten im Baum. Man kann ohne Stack und Rekursion von einem Knoten in z.B. einem Binären Baum via In-Order-Traversierung zu seinem Vorgänger/Nachfolger "hangeln".

    Falsch. Man braucht mehr Informationen, zum Beispiel im Iterator den root-Zeiger oder einen history-Stack, oder im Baum Aufwärts- oder rechts-links-Zeiger.

    "Falsch" ist ein bisschen hart. Bin davon ausgegangen, dass es "parent"-Zeiger gibt und hab nicht dran gedacht, dass man die auch weglassen kann 🙄.
    Aber selbst ohne die - kann ich nicht einfach jedesmal stupide immer von der Wurzel suchen? Mit alle Elemente in n log n interieren gewinnt man zwar keinen Blumentopf, aber man kann sich von dem gesparten Stack nen Eis kaufen 😉

    Finnegan



  • Finnegan schrieb:

    volkard schrieb:

    Finnegan schrieb:

    Ist das Problem eventuell, dass der Multimap ein Baum zugrunde liegt (von wegen Stack)?. Wenn ja, dann benötigt der Iterator meines erachtens lediglich einen Pointer auf den aktuellen Knoten im Baum. Man kann ohne Stack und Rekursion von einem Knoten in z.B. einem Binären Baum via In-Order-Traversierung zu seinem Vorgänger/Nachfolger "hangeln".

    Falsch. Man braucht mehr Informationen, zum Beispiel im Iterator den root-Zeiger oder einen history-Stack, oder im Baum Aufwärts- oder rechts-links-Zeiger.

    "Falsch" ist ein bisschen hart. Bin davon ausgegangen, dass es "parent"-Zeiger gibt und hab nicht dran gedacht, dass man die auch weglassen kann 🙄.
    Aber selbst ohne die - kann ich nicht einfach jedesmal stupide immer von der Wurzel suchen? Mit alle Elemente in n log n interieren gewinnt man zwar keinen Blumentopf, aber man kann sich von dem gesparten Stack nen Eis kaufen 😉

    Nein. ++i soll gehen. Hat i nur einen Node*, geht das eben nicht. Hast ja keinen Zeiger auf die Wurzel verfügbar.



  • volkard schrieb:

    Nein. ++i soll gehen. Hat i nur einen Node*, geht das eben nicht. Hast ja keinen Zeiger auf die Wurzel verfügbar.

    hehe... Wusste doch dass was fehlt ;). Gut, in dem Fall braucht der Interator mehr als nur den Node* . Wie siehts mit "mindestens noch den Wurzel-Pointer" aus? Wahlweise nur diesen oder als unterstes Stack-Element, oder indirekt als MuMap* ? 😃
    Und ohnehin - ich denke man kann durchaus rechts/links-Pointer anregen - ich denke in den meisten Anwendungsfällen sind die eine gute Wahl - es sei denn man hat einen guten Grund besonders sparsam zu sein.

    Finnegan



  • volkard schrieb:

    Fremde Leute "dürfen" nur das aufrufen, was in der Doku steht. Steht da kein it.getImplPtr(), dann "dürfen" sie das nicht. Das kannste gerne unterstützen, indem Du getImplPtr() private machast und die MuMa<Foo> zum offiziellen friend des MuMa<Foo>::Iterators erklärst.

    Danke, der Tipp mit dem "friend" hat geholfen.
    Hier das ist mein bislang funktionierendes Ergebnis:

    Iterator find_help(const Key& mKey,Node* tmp,Iterator i){
            if(tmp!=nullptr){
                if(tmp->mKey!=mKey){
                    i.mStack.push_back(tmp);
                    if(mKey<tmp->mKey){
                        find_help(mKey,tmp->mLeft,i);
                    }else if(mKey>tmp->mKey){
                        find_help(mKey,tmp->mRight,i);
                    }
                }else if(tmp->mKey==mKey){
                    i.mStack.push_back(tmp);
                    i.mNode = tmp;
                    i.updatePair();//Aktualisiert das Pair mit dem neuen mNode.
                }
            }
            return i;
        }
    

    volkard schrieb:

    Aber normalerweise benutzt du innerhalb der find()-Implementierung überhaupt keine Iteratoren, sondern bloß Zeiger.

    Aber die find-Methode gibt einen Iterator zurück und deswegen muss die Methode doch irgendwie den Iterator bis zum fundus steuern oder nicht?



  • Nur bei deinem stackbasierten Iterator. Wenn der Iterator nicht mehr als ein Zeiger auf ein Knoten wäre kannst du einfach Iteratoren für einen Knoten anlegen. Wie du zu dem Knoten gefunden hast ist dann egal.


Anmelden zum Antworten