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

Question

I'm trying to implement a const_iterator for my binary tree but when I try to compile this 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;
}

the compiler (clang++) outputs:

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.

the base_iterator< node_type > class is a public type of the rbtree class (rbnode is also a public type of rbtree) Here's the code of my 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;
};

and the typedefs for iterator and const iterator, and iterator functions in my 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(); }

I also edited private variables of rbtree class:

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

So technically this should work, so why doesn't it ? it seems that the wrong function is called (iterator one instead of const_iterator one). I saw from your answers that a const iterator must be convertible to an iterator ? so does that mean that I have to use the same type for both ?

Answer 1

You have to remember that templated types are completely independant.

 base_iterator<X>
 base_iteraotr<const X>

Are completely different types.

Your compiler is complaining that there is no constructor (or conversion operator) in base_iteraotr<const X> that accepts base_iteraotr<X> (a completely different type).