Iteratorproblem



  • Also, ich hab folgendes Problem.

    Ich hab einen Iterator für einen Binärbaum erstellt, der soweit auch gut funktioniert. Allerdings steht in meinem Examen das der Inhalt des Iterators ein Paar bestehend aus Wertebereich und Zielbereich sein soll.

    Ich verstehe nicht ganz was das soll. Da ich nur den Node* habe, der auf den Node des Binärbaums zeigt.

    Hier ist mein Iterator:

    template<class ValueType, class NodeType>
    class MyMultiMapIterator{
    public:
    
        MyMultiMapIterator (NodeType* pIRoot) : mIRoot(pIRoot){
            if(mIRoot!=nullptr){
                goLeft(mIRoot);
                mIRoot = mStk.back();
            }
        }
    
        friend bool operator != (const MyMultiMapIterator& crI1,const MyMultiMapIterator& crI2) {
            return crI1.mIRoot != crI2.mIRoot;
        }
    
        ValueType& operator * () {
            return mIRoot->mValue;
        }
    
        MyMultiMapIterator operator ++() {
    
            NodeType* tmp = mStk.back();
            mStk.pop_back();
            if(tmp->mRight!=nullptr){goLeft(tmp->mRight);}
            mIRoot = mStk.back();
            return *this;
        }
    
    private :
    
        void goLeft(NodeType* tmp){
            if(tmp!=nullptr){
                mStk.push_back(tmp);
                goLeft(tmp->mLeft);
            }
        }
    
        MyStack<NodeType*> mStk;
        NodeType* mIRoot;
    };
    


  • Tja, du stellst eigentlich keine Frage. Wie dein Baum genau aussieht verrätst du auch nicht. Ich gehe aber davon aus, dass es so etwas wie std::map seinsoll. Der iterator liefert dort mit first den Key und mit second den Value.



  • Meinem Verstaendnis nach sollte ein Iterator nie ein Wert sein, der irgendwo in der Datenstruktur gespeichert ist. Es sollte eine eindeutige "Hausnummer" eines Wertes sein (wenn in einer Datenstruktur n-mal der gleiche Wert gespeichert ist, hat trotzdem jeder eine andere Hausnummer). Das ist bei euch scheinbar anders, also schau in deine Unterlagen, was "Iterator" bedeuten soll.



  • TGGC schrieb:

    Meinem Verstaendnis nach sollte ein Iterator nie ein Wert sein, der irgendwo in der Datenstruktur gespeichert ist. Es sollte eine eindeutige "Hausnummer" eines Wertes sein (wenn in einer Datenstruktur n-mal der gleiche Wert gespeichert ist, hat trotzdem jeder eine andere Hausnummer). Das ist bei euch scheinbar anders, also schau in deine Unterlagen, was "Iterator" bedeuten soll.

    😕

    Das Problem, das ich sehe, ist, dass das Kopieren des Iterators hier O(log n) Zeit braucht, es aber üblicherweise konstant ist.

    Mein Vorschlag wäre daher

    MyMultiMapIterator operator ++() {
            mIRoot = mIRoot->mParent; // es braucht pro Node einen mParent
            if (mIRoot->mRight != nullptr)
              mIRoot = goLeft(mIRoot->mRight);
            return *this;
        }
        NodeType* goLeft(NodeType* tmp){
            while (tmp->mLeft)
                tmp = tmp->mLeft;
            return tmp;
        }
    

    Das eigentliche Problem wäre aber, dass in der Map wahrscheinlich so etwas steht:

    KeyType mKey;
    ValueType mValue;
    

    Wenn du dort hinschreibst

    pair<const KeyType, ValueType> mKeyValue;
    

    dann kannst du vom operator* aus eine Referenz auf das Paar zurückgeben.


Anmelden zum Antworten