5

逆反復機能を取得するために std::reverse_iterator<> で使用している独自の反復子を実装するコンテナーに取り組んでいます。逆イテレータを rend または rbegin に割り当てることができますが、その機能 (!= または == など) にアクセスしようとすると、次のようになります。

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>>>>>

私のイテレータ演算子のオーバーロード:

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

そして逆イテレータの私の実装

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;

およびイテレータ typedef:

    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;

演算子の使用方法

    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
    {
    }

および iterator クラス (const_iterator は同じものですが、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;
    }
};

そしてツリークラス：

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
4

4 に答える 4

5

この行で：

rit != myTree.rend()

次のタイプの 2 つのオブジェクトを比較しています。

avltree<char,int>::reverse_iterator

これは、次のエイリアスです。

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

C++ 標準ライブラリは、std::名前空間で、逆反復子を比較するための完全一致である templatedを定義しoperator !=ます (C++11 標準の段落 24.5 を参照)。

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

ただし、これもあります：

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

テンプレートは制約されていないため (テンプレート パラメーターの名前が であってもtree、これはテンプレートがツリーのみを受け入れるという意味ではありません)、これも完全に一致しoperator !=ますが、リバース イテレーター用にテンプレート化されたものはさらに特殊化されています。

したがって、呼び出しがあいまいであってはなりません。これはコンパイラのバグだと思います。

この問題を解決するには、ツリーの不等式演算子がツリーのみを受け入れることを確認してください。これはとにかく良い考えです (結局、演算子に何かを比較させたくありません)。

template<class T> bool operator!=(const avltree<T>& left,const avltree<T>& right)
于 2013-03-01T15:05:50.633 に答える
2

operator !=sを含め、いつでも比較しようとしますreverse_iterator。使用してみてください。

template<class T> bool operator!= (const avltree<T>& left,const avltree<T>& right) {     
    return (!(left == right)); 
}
于 2013-03-01T15:04:55.123 に答える
2

壊れたコンパイラのようです。

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

「より専門的」です

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

したがって、表現rit != myTree.rend()があいまいであってはなりません。

それでも、同じ型の任意!=の 2 つのオブジェクトに適用できるものを宣言することは危険な考えです。

于 2013-03-01T15:04:56.977 に答える
-1

const_reverse_iterator を reverse_iterator と比較しようとすると、rend() の呼び出しは、利用可能な場合は常に非 const オーバーロードを使用します。これに対する修正は明らかです。私の記憶が正しければ、初期の std::set 実装にも同じ問題がありました。

とにかく、私見をさらにエレガントにしながら、この問題を回避する良いアプローチがあります。

for(container::iterator it=c.begin(), end=c.end(); it!=end; ++it)
    ...

つまり、for ループのヘッダーで宣言されている反復子のペアを常に使用します。C++11 の「auto」を使用すると、これはさらに短くなります。end() への単一の呼び出しは、中途半端な最新のコンパイラーでは高速ではありませんが、個人的には少し明確になっています。

于 2013-03-01T18:17:47.913 に答える