Iterator on binary tree compilation error

Question

I get the following compilation error:

error: invalid conversion from 'const IntervalST' to 'IntervalST' [-fpermissive]

when I compile my code. The code is quite big but here are the relevant parts:

the class IntervalST:

template  class intervalST_const_iterator;

template  class IntervalST
{
private:
    Interval *root;

    //friend class intervalST_const_iterator;//allow the iterator class to access the private section of intervalST

    bool isRed(Interval *interval);
    Interval *rotateLeft(Interval *h);
    Interval *rotateRight(Interval *h);
    Interval *put(Interval *h,Key lo, Key hi, Key val);
    Interval *moveRedLeft(Interval *h);
    Interval *moveRedRight(Interval *h);
    Interval *deleteMin(Interval *h, Key hi);
    Interval *balance(Interval *h);
    Interval *remove(Interval *h, Key lo, Key hi);
    Interval *min(Interval *h);
    Interval *addDuplicate(Interval *h, Key hi);
    Interval *removeDuplicate(Interval *h, Key low, Key hi);
    Interval *getPointerToKey(Key low);

    void flipColors(Interval *h);
    void destroy(Interval *h);
    void printTree(Interval *h, int indent);
    Key maxVal(Interval *h);
    int size(Interval *h);
    bool isBST(Interval *x, Key min, Key max);
    inline bool isBST(){return isBST(root,0,0);}
    bool isSizeConsistent(Interval *x);
    inline bool isSizeConsistent(){return isSizeConsistent(root);}
    bool is23(Interval *x);
    inline bool is23(){return is23(root);}
    bool isBalanced();
    bool isBalanced(Interval *x,int black);
    int getKeySize(Key low);
    int compare(Key a, Key b);

public:

    //don't forget to build the constructor
    //and overload the =equal operator
    typedef intervalST_const_iterator const_iterator;//const iterator on a tree


    const_iterator begin() const;
    const_iterator end() const;

    IntervalST():root(NULL){};
    ~IntervalST();
    void remove(Key lo, Key hi);
    void put(Key lo, Key hi);
    inline int size(){return size(root);}
    inline bool isEmpty(){return root == NULL;}
    void print(int indent = 0);
    void check();


};

The compiler is complaining on the implementation of the begin() method of the class IntervalST

begin() and end() method:

template  typename IntervalST::const_iterator IntervalST::begin() const
{
return const_iterator(root,this);//<-----------code complaining here
}

template  typename IntervalST::const_iterator IntervalST::end() const
{
return const_iterator(NULL,this);
}

here is the iterator class:

template  class intervalST_const_iterator
{
//friend class IntervalST;

private:
    Interval *interval;
    IntervalST *tree;

public:
    intervalST_const_iterator(Interval *p, IntervalST *t): interval(p), tree(t){}
    bool operator != (const intervalST_const_iterator & other) const
    {
        return this->interval != other.interval;
    }
    bool operator == (const intervalST_const_iterator & other) const
    {
        return this->interval == other.interval;
    }
    Interval operator *() const
    {
        return *(this->interval);
    }
    intervalST_const_iterator & left() const
    {
        return (interval = interval->left);
    }
    intervalST_const_iterator & right() const
    {
        return (interval = interval->right);
    }
};

Why is this happening? and how to solve it? Surprisingly the implementation of the end() method is almost the same as the implementation of the begin() method. thanks for your help

Sean · Accepted Answer

Your member function Interval::begin(), is marked const, so any use of this must also be const. In this case, the constructor for your iterator class accepts pointers to non-const Interval objects, so passing this here is not allowed. You should add the const keyword to all the Interval pointers in your intervalST_const_iterator class, starting with the constructor arguments.

For similar reasons, your left() and right() member functions of intervalST_const_iterator will also fail to compile because they too are marked const, yet they modify the interval field of the iterator.

Note that in the conventions of the C++ template library, a const_iterator is not itself constant, but the container object it iterates over is constant. As opposed to a non-constant iterator that allows you to add/remove/modify elements of the container. Both const/non-const iterators must be themselves mutable so you can step them through each element.

Update: In your iterator class, your member variables must be constant:

const Interval *interval;
const IntervalST *tree;

Then, the iterator's member functions must also use constant interval pointers:

intervalST_const_iterator(const Interval *p, const IntervalST *t)
const Interval operator *() const

Iterator on binary tree compilation error

Answers (2)

Related Questions