Operator != is ambiguous for std::reverse_iterator c++

Question

I am working on a container that implements its own iterator, which I am using with std::reverse_iterator<> to get reverse iteration functionality. I can assign the reverse iterator to rend or rbegin, but when i try to access any of its functionality (such as != or ==) I get this:

1   IntelliSense: more than one operator "!=" matches these operands:
        function template "bool std::operator!=(const std::reverse_iterator<_RanIt1> &_Left, const std::reverse_iterator<_RanIt2> &_Right)"
        function template "bool avl::operator!=(const tree &left, const tree &right)"
        operand types are: std::reverse_iterator<avl::avl_iterator<avl::avltree<char, int, std::less<char>, std::allocator<std::pair<const char, int>>>>> != std::reverse_iterator<avl::avl_iterator<avl::avltree<char, int, std::less<char>, std::allocator<std::pair<const char, int>>>>>

My iterator operator overloads:

bool operator == ( const avl_iterator& rhs ) const { return ( _node == rhs._node); }
    bool operator != ( const avl_iterator& rhs ) const { return ( _node != rhs._node); }

and my implementation of reverse iterator

typedef typename avl_iterator< tree >                               iterator;
typedef typename const_avl_iterator< tree >                         const_iterator;
typedef typename std::reverse_iterator<iterator>                    reverse_iterator;
typedef typename std::reverse_iterator<const_iterator>              const_reverse_iterator;

and the iterator typedefs:

    typedef typename tree::node                 node;
    typedef typename tree::node_ptr             node_ptr;
    typedef typename tree::value_type*          pointer;// for std reverse iterator
    typedef typename tree::value_type&          reference;
    typedef typename tree::const_node_ptr       const_node_ptr;
    typedef typename tree::utilities            utilities;
    typedef typename tree::value_type           value_type;
    typedef std::bidirectional_iterator_tag     iterator_category;
    typedef std::ptrdiff_t                      difference_type;

How I'm using the operator

    avltree<char,int> myTree;
    myTree.insert(std::pair<char,int>('a',1));
    myTree.insert(std::pair<char,int>('b',2));
    myTree.insert(std::pair<char,int>('c',3));

    avltree<char,int>::reverse_iterator rit = myTree.rbegin();

    for(; rit != myTree.rend(); ++rit) //fails on this line
    {
    }

and the iterator class (const_iterator is the same thing but with a const value_type)

template <class tree>
class avl_iterator {
public:
    typedef typename tree::node                 node;
    typedef typename tree::node_ptr             node_ptr;
    typedef typename tree::value_type*          pointer;// for std reverse iterator
    typedef typename tree::value_type&          reference;
    typedef typename tree::const_node_ptr       const_node_ptr;
    typedef typename tree::utilities            utilities;
    typedef typename tree::value_type           value_type;
    typedef std::bidirectional_iterator_tag     iterator_category;
    typedef std::ptrdiff_t                      difference_type;

private:
    friend class const_avl_iterator<tree>;
    node_ptr _node;
public:
    avl_iterator() : _node()  { }
    avl_iterator( const node_ptr node ) : _node ( node ) { }
    avl_iterator( const avl_iterator& iterator ) {
        (*this) = iterator;
    }
    ~avl_iterator() { _node = NULL; }

    avl_iterator& operator=(const avl_iterator& rhs) {
        _node = rhs._node;
        return (*this);
    }
    avl_iterator& operator=(const const_avl_iterator<tree>& rhs) {
        _node = rhs._node;
        return (*this);
    }

    bool operator == ( const avl_iterator& rhs ) const { return ( _node == rhs._node); }
    bool operator != ( const avl_iterator& rhs ) const { return ( _node != rhs._node); }

    avl_iterator& operator++()
    {
        _node = utilities::next_node( _node );
        return (*this);
    }
    avl_iterator operator ++( int ) {
        avl_iterator temp(*this);
        ++(*this);
        return(temp);
    }

    avl_iterator& operator -- () {
        _node = utilities::prev_node( _node );
        return (*this);
    }

    avl_iterator operator -- ( int ) {
        avl_iterator temp(*this);
        --(*this);
        return(temp);
    }

    value_type& operator * () const {
        assert( ! utilities::is_header( _node ) );
        return _node->_value;
    }

    value_type* operator -> () const {
        assert( ! utilities::is_header( _node ) );
        return &_node->_value;
    }
};

and the tree class:

template <
    class Key,
    class Type,
    class Traits = std::less<Key>,
    class Allocator = std::allocator<std::pair<Key const, Type>>
    >
    class avltree {
    private:
        typedef avltree< Key, Type, Traits, Allocator>                      tree;
    public:
        typedef std::pair<const Key, Type>                                  value_type;
        typedef Allocator                                                   allocator_type;
        typedef typename allocator_type::size_type                          size_type;
        typedef typename allocator_type::reference                          reference;
        typedef Key                                                         key_type;
        typedef Type                                                        mapped_type;
        typedef Traits                                                      key_compare;
        typedef typename avl_node< tree >                                   node;
        typedef typename node::node_ptr                                     node_ptr;
        typedef typename node::const_node_ptr                               const_node_ptr;
        typedef typename avl_utilities< tree >                              utilities;
        typedef typename avl_iterator< tree >                               iterator;
        typedef typename const_avl_iterator< tree >                         const_iterator;
        typedef typename std::reverse_iterator<iterator>                    reverse_iterator;
        typedef typename std::reverse_iterator<const_iterator>              const_reverse_iterator;
    private:
        node_ptr _header;
        std::size_t _size;
        key_compare _comparer;
        allocator_type _alloc;
    public:
            //c'tors and d'tors
         //*******************************************************
        //Iterators
        //*******************************************************
        iterator                begin()         { return iterator( node::get_left( _header ) ); }
        const_iterator          begin() const   { return const_iterator( node::get_left( _header ) ); }
        const_iterator          cbegin() const  { return const_iterator( node::get_left( _header ) ); }
        iterator                end()           { return iterator( _header ); }
        const_iterator          end() const     { return const_iterator( _header ); }
        const_iterator          cend() const    { return const_iterator( _header ); }

        reverse_iterator        rbegin()        { return reverse_iterator( _header ); }
        const_reverse_iterator  rbegin() const  { return const_reverse_iterator( _header ); }
        const_reverse_iterator  crbegin() const { return const_reverse_iterator( _header ); }
        reverse_iterator        rend()          { return reverse_iterator( node::get_left( _header ) ); }
        const_reverse_iterator  rend() const    { return const_reverse_iterator( node::get_left( _header ) ); }
        const_reverse_iterator  crend() const   { return const_reverse_iterator( node::get_left( _header ) ); }
        bool operator==(const tree& right)
        {   
            if(_size != right.size())
            {
                return false;
            }

            const_iterator lhs = cbegin();
            const_iterator rhs = right.cbegin();
            while(lhs != cend() && rhs != right.cend() )
            {
                if(lhs->first != rhs->first || lhs->second != rhs->second)
                {
                    return false;
                }
                ++lhs;
                ++rhs;
            }
            return true;
        }
        bool operator!=(const tree& right)
        {
            return (!(*this == right));
        }
        bool operator<(const tree& right)
        {
            const_iterator lhs = cbegin();
            const_iterator rhs = right.cbegin();
            while(lhs != cend() && rhs != right.cend() )
            {
                if(lhs->first != rhs->first || lhs->second != rhs->second)
                {
                    if(lhs->first < rhs->first || lhs->second < rhs->second)
                    {
                        return true;
                    }                       
                }
                ++lhs;
                ++rhs;
            }
            return false;
        }
        bool operator>(const tree& right)
        {
            return ( right < *this );
        }
        bool operator<=(const tree& right)
        {
            return ( !(right < *this) );
        }
        bool operator>=(const tree& right)
        {
            return ( !(*this < right) );
        }
};
//*******************************************************
//Relation Operators
//*******************************************************
template<class tree>
bool operator==(const tree& left,const tree& right)
{   
    if(left.size() != right.size())
    {
        return false;
    }

    tree::const_iterator lhs = left.cbegin();
    tree::const_iterator rhs = right.cbegin();
    while(lhs != left.cend() && rhs != right.cend() )
    {
        if(lhs->first != rhs->first || lhs->second != rhs->second)
        {
            return false;
        }
        ++lhs;
        ++rhs;
    }
    return true;
}
template<class tree>
bool operator!=(const tree& left,const tree& right)
{
    return (!(left == right));
}
template<class tree>
bool operator<(const tree& left,const tree& right)
{
    tree::const_iterator lhs = left.cbegin();
    tree::const_iterator rhs = right.cbegin();
    while(lhs != left.cend() && rhs != right.cend() )
    {
        if(lhs->first != rhs->first || lhs->second != rhs->second)
        {
            if(lhs->first < rhs->first || lhs->second < rhs->second)
            {
                return true;
            }                       
        }
        ++lhs;
        ++rhs;
    }
    return false;
}
template<class tree>
bool operator>(const tree& left,const tree& right)
{
    return ( right < left );
}
template<class tree>
bool operator<=(const tree& left,const tree& right)
{
    return ( !(right < left) );
}
template<class tree>
bool operator>=(const tree& left,const tree& right)
{
    return ( !(left < right) );
}
}//end namespace avl

Answer 1

On this line:

rit != myTree.rend()

You are comparing two objects of type:

avltree<char,int>::reverse_iterator

Which is in turn an alias for:

std::reverse_iterator<avl_iterator<char, int>::iterator>

The C++ Standard Library defines, in the std:: namespace, a templated operator != which is an exact match for comparing reverse iterators (see Paragraph 24.5 of the C++11 Standard):

template <class Iterator1, class Iterator2>
bool operator!=(
    const reverse_iterator<Iterator1>& x,
    const reverse_iterator<Iterator2>& y)

However, you also have this:

template<class tree> bool operator!=(const tree& left,const tree& right)

Since the template is unconstrained (even though the template parameter is named tree, this doesn't mean the template will only accept trees), this is also an exact match, but the templated operator != for reverse iterators is still more specialized.

Therefore, the call should not be ambiguous. I think this is a compiler bug.

---

To fix the issue, make sure your inequality operator for trees only accept trees, which is anyway a good idea (you really don't want your operator to compare anything after all):

template<class T> bool operator!=(const avltree<T>& left,const avltree<T>& right)

Answer 2

Your operator != tries to compare any time, including reverse_iterators, you may try use

template<class T> bool operator!= (const avltree<T>& left,const avltree<T>& right) {     
    return (!(left == right)); 
} 

Answer 3

Seems like a broken compiler.

template<typename Iter>
bool std::operator!=(const std::reverse_iterator<Iter>&,
                     const std::reverse_iterator<Iter>&);

is "more specialized than"

template<class tree>
bool avl::operator!=(const tree&, const tree&);

so the expression rit != myTree.rend() should not be ambiguous.

Still, declaring something that can apply != to any two objects of the same type is a dangerous idea.