二进制树编译错误的迭代器

Question

我收到以下编译错误:

错误:从'const IntervalST '到'IntervalST '的无效转换[-fpermissive]

当我编译我的代码.代码很大但这里是相关部分:

IntervalST类:

template <class Key> class intervalST_const_iterator;

template <class Key> class IntervalST
{
private:
    Interval<Key> *root;

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

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

    void flipColors(Interval<Key> *h);
    void destroy(Interval<Key> *h);
    void printTree(Interval<Key> *h, int indent);
    Key maxVal(Interval<Key> *h);
    int size(Interval<Key> *h);
    bool isBST(Interval<Key> *x, Key min, Key max);
    inline bool isBST(){return isBST(root,0,0);}
    bool isSizeConsistent(Interval<Key> *x);
    inline bool isSizeConsistent(){return isSizeConsistent(root);}
    bool is23(Interval<Key> *x);
    inline bool is23(){return is23(root);}
    bool isBalanced();
    bool isBalanced(Interval<Key> *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<Key> 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();


};

编译器抱怨IntervalST类的begin()方法的实现

begin()和end()方法:

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

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

这是迭代器类:

template <class Key> class intervalST_const_iterator
{
//friend class IntervalST<Key>;

private:
    Interval<Key> *interval;
    IntervalST<Key> *tree;

public:
    intervalST_const_iterator(Interval<Key> *p, IntervalST<Key> *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<Key> operator *() const
    {
        return *(this->interval);
    }
    intervalST_const_iterator<Key> & left() const
    {
        return (interval = interval->left);
    }
    intervalST_const_iterator<Key> & right() const
    {
        return (interval = interval->right);
    }
};

为什么会这样？以及如何解决？令人惊讶的是,end()方法的实现与begin()方法的实现几乎相同.谢谢你的帮助

Answer 1

您的会员功能Interval<Key>::begin(),已标记const,因此任何使用this也必须const.在这种情况下,迭代器类的构造函数接受指向非const Interval<Key>对象的指针,因此this不允许传递给此.您应该将const关键字添加到类中的所有Interval<Key>指针intervalST_const_iterator,从构造函数参数开始.

由于类似的原因,你的left()和right()成员函数也intervalST_const_iterator将无法编译,因为它们也标记为const,但它们修改interval了迭代器的字段.

请注意,在C++模板库的约定中,a const_iterator本身不是常量,但它迭代的容器对象是常量.与非常量相反iterator,允许您添加/删除/修改容器的元素.const/non-const迭代器必须本身是可变的,因此您可以逐步遍历每个元素.

更新:在您的迭代器类中,您的成员变量必须是常量:

const Interval<Key> *interval;
const IntervalST<Key> *tree;

然后,迭代器的成员函数也必须使用常量间隔指针:

intervalST_const_iterator(const Interval<Key> *p, const IntervalST<Key> *t)
const Interval<Key> operator *() const