无法为二叉树 C++ 实现 const_iterator

Question

我正在尝试为我的二叉树实现一个 const_iterator 但是当我尝试编译这个 main 时：

#include "rbtree.hpp"
#include <iostream>

int main(void) {
    rbtree< int >   t;
    t.insert(9);
    t.insert(8);
    t.insert(7);
    t.insert(6);
    t.insert(5);
    t.insert(1);
    t.insert(2);
    t.insert(3);
    t.insert(4);
    for (rbtree< int >::const_iterator it = t.begin(); it != t.end())
        std::cout << *it << std::endl;
    return 0;
}

编译器 (clang++) 输出：

test.cpp:27:37: error: no viable conversion from 'base_iterator<rbtree<int, std::allocator<int>, unsigned long, long>::rbnode>' to 'base_iterator<const rbtree<int, std::allocator<int>, unsigned long, long>::rbnode>'
        for (rbtree< int >::const_iterator it = t.begin(); it != t.end())
                                           ^    ~~~~~~~~~
./rbtree.hpp:172:5: note: candidate constructor not viable: no known conversion from 'rbtree<int, std::allocator<int>, unsigned long, long>::iterator' (aka 'base_iterator<rbtree<int, std::allocator<int>, unsigned long, long>::rbnode>') to 'const rbtree<int, std::allocator<int>, unsigned long, long>::rbnode *' for 1st argument
                                base_iterator(node_type *from) : _ptr(from) { }
                                ^
./rbtree.hpp:173:5: note: candidate constructor not viable: no known conversion from 'rbtree<int, std::allocator<int>, unsigned long, long>::iterator' (aka 'base_iterator<rbtree<int, std::allocator<int>, unsigned long, long>::rbnode>') to 'const rbtree<int, std::allocator<int>, unsigned long, long>::base_iterator<const rbtree<int, std::allocator<int>, unsigned long, long>::rbnode> &' for 1st argument
                                base_iterator(const base_iterator &other) : _ptr(other._ptr) { }
                                ^
1 error generated.

base_iterator< node_type > class 是 rbtree class 的 public 类型（rbnode 是也是 public 类型的 rbtree) 这是我的代码 base_iterator class:

template <
    typename node_type
> class base_iterator : public std::iterator<
    std::bidirectional_iterator_tag,
    T, // fix, was node_type
    difference_type
> {
    public:
        base_iterator() : _ptr(NULL) { }
        base_iterator(node_type *from) : _ptr(from) { }
        base_iterator(const base_iterator &other) : _ptr(other._ptr) { }
        ~base_iterator() { }

        base_iterator   &operator =(const base_iterator &other) {
            _ptr = other._ptr;
        }
        T               &operator *(void) { return *_ptr->_data; }
        T               *operator ->(void) { return _ptr->_data; }
        base_iterator   &operator ++(void) {
            if (_ptr) {
                if (_ptr->_right) {
                    _ptr = _ptr->_right;
                    while (_ptr->_left) _ptr = _ptr->_left;
                } else {
                    while (
                        _ptr->_parent
                        && _ptr->_parent->_right == _ptr
                    ) _ptr = _ptr->_parent;
                    if (!_ptr->_parent) return base_iterator();
                }
            }
            return _ptr;
        }
        base_iterator   operator ++(int) {
            base_iterator   backup(_ptr);
            ++this;
            return backup;
        }
        base_iterator   &operator --(void) {
            if (_ptr) {
                if (_ptr->_left) {
                    _ptr = _ptr->_left;
                    while (_ptr->_right) _ptr = _ptr->_right;
                } else {
                    while (
                        _ptr->_parent
                        && _ptr->_parent->_left == _ptr
                    ) _ptr = _ptr->_parent;
                    if (!_ptr->_parent) return base_iterator();
                }
            }
            return _ptr;
        }
        base_iterator   operator --(int) {
            base_iterator   backup(_ptr);
            --this;
            return backup;
        }
    private:
        node_type   *_ptr;
};

和 iterator 和 const iterator 的类型定义，以及我的 rbtree class

中的迭代器函数

typedef base_iterator< rbnode >                 iterator;
typedef base_iterator< const rbnode >           const_iterator;
typedef ft::reverse_iterator< iterator >        reverse_iterator;
typedef ft::reverse_iterator< const_iterator >  const_reverse_iterator;

iterator                begin(void) { return iterator(_begin); } // fix, was return _begin;
const_iterator          begin(void) const {
    return const_iterator(_begin);
}
iterator                end(void) { return iterator(); }
const_iterator          end(void) const { return const_iterator(); }
reverse_iterator        rbegin(void) { return iterator(_rbegin); }
const_reverse_iterator  rbegin(void) const {
    return const_iterator(_rbegin);
}
reverse_iterator        rend(void) { return iterator(); }
const_reverse_iterator  rend(void) const { return const_iterator(); }

我还编辑了 rbtree class:

的私有变量

size_type           _size;
rbnode              *_root;
rbnode              *_begin; // was iterator
rbnode              *_rbegin; // was iterator

所以从技术上讲这应该可行，但为什么不行呢？似乎调用了错误的函数（iterator 一个而不是 const_iterator 一个）。我从您的回答中看出 const 迭代器必须可转换为迭代器？那么这是否意味着我必须为两者使用相同的类型？

Answer 1

你必须记住，模板类型是完全独立的。

 base_iterator<X>
 base_iteraotr<const X>

是完全不同的类型。

您的编译器抱怨 base_iteraotr<const X> 中没有接受 base_iteraotr<X>（完全不同的类型）的构造函数（或转换运算符）。

无法为二叉树 C++ 实现 const_iterator

Having trouble implementing a const_iterator for a binary tree C++

c++

iterator

class

c++98