c++ - 二叉树编译错误的迭代器

Question

我得到以下编译错误:

error: invalid conversion from 'const IntervalST' to '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 .在这种情况下，迭代器类的构造函数接受指向非常量 Interval<Key> 的指针。对象，所以传递 this这里是不允许的。您应该添加 const所有 Interval<Key> 的关键字intervalST_const_iterator 中的指针类，从构造函数参数开始。

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

请注意，在 C++ 模板库的约定中，一个 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