Implementing const_reverse_iterator for List class

[mpark4656]

Textbook Problem Description: Add reverse iterators to the STL List class implementation. Define reverse_iterator and const_reverse_iterator. Add the methods rbegin and rend to return appropriate reverse iterators representing the position prior to the endmarker and the position that is the header node. Reverse iterators internally reverse the meaning of the ++ and -- operators. You should be able to print a list L in reverse by using the code.

List<Object>::reverse_iterator itr = L.begin();
while( itr != L.rend() )
cout << *itr++ << endl;

The below is my implementation. I am able to use the reverse_iterator with no issue, but the problem is with const_reverse_iterator.

If I write a line like this:
my::List<int>::const_reverse_iterator itr = test.rbegin();

I get the following error message:
error: conversion from 'my::List<int>::reverse_iterator' to non-scalar type 'my::List<int>::const_reverse_iterator' requested|
||=== Build failed: 1 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|

How can I fix this problem?

Despite the fact that I have rbegin() functions that return reverse_iterator and const_reverse_iterator, it seems the compiler does not recognize it.

[mpark4656]

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

namespace my
{
    template <typename Object>
    class List
    {
    private:
        struct Node
        {
            Object data;
            Node* prev;
            Node* next;

            Node( const Object &d = Object{} , Node* p = nullptr , Node* n = nullptr )
                : data{ d } , prev{ p } , next{ n } {}

            Node( Object &&d , Node* p = nullptr , Node* n = nullptr )
                : data{ std::move(d) } , prev{ p } , next{ n } {}
        };

    public:
        class const_iterator
        {
        protected:
            Node* current;

            Object & retrieve() const
            { return current->data; }

            const_iterator( Node* p ): current{ p } {}

            friend class List<Object>;

        public:
            const_iterator(): current{ nullptr } {}

            const Object & operator* () const
            { return retrieve(); }

            const_iterator & operator++ ()
            {
                current = current->next;
                return *this;
            }

            const_iterator operator++ ( int )
            {
                const_iterator old = *this;
                ++( *this );
                return old;
            }

            const_iterator operator-- ()
            {
                current = current->prev;
                return *this;
            }

            const_iterator operator-- ( int )
            {
                const_iterator old = *this;
                --( *this );
                return old;
            }

            bool operator== ( const const_iterator &rhs ) const
            { return current == rhs.current; }

            bool operator!= ( const const_iterator &rhs ) const
            { return !( *this == rhs ); }
        };

        class iterator: public const_iterator
        {
        public:
            iterator() {}

            Object & operator* ()
            { return const_iterator::retrieve(); }

            const Object & operator* () const
            { return const_iterator::operator*(); }

            iterator & operator++ ()
            {
                this->current = this->current->next;
                return *this;
            }

            iterator operator++ ( int )
            {
                iterator old = *this;
                ++( *this );
                return old;
            }

            iterator operator-- ()
            {
                this->current = this->current->prev;
                return *this;
            }

            iterator operator-- ( int )
            {
                iterator old = *this;
                --( *this );
                return old;
            }

        protected:
            iterator( Node* p ): const_iterator{ p } {}

            friend class List<Object>;
        };

        class reverse_iterator: public iterator
        {
        public:
            reverse_iterator() {}

            Object & operator* ()
            { return iterator::retrieve(); }

            const Object & operator* () const
            { return iterator::operator*(); }

            reverse_iterator & operator++ ()
            {
                this->current = this->current->prev;
                return *this;
            }

            reverse_iterator operator++ ( int )
            {
                reverse_iterator old = *this;
                ++( *this );
                return old;
            }

            reverse_iterator operator-- ()
            {
                this->current = this->current->next;
                return *this;
            }

            reverse_iterator operator-- ( int )
            {
                reverse_iterator old = *this;
                --( *this );
                return old;
            }

        protected:
            reverse_iterator( Node* p ): iterator{ p } {}

            friend class List<Object>;
        };

        class const_reverse_iterator: public const_iterator
        {
        public:
            const_reverse_iterator() {}

            const Object & operator* () const
            { return const_iterator::retrieve(); }

            const_reverse_iterator operator++ ()
            {
                this->current = this->current->prev;
                return *this;
            }

[mpark4656]

            const_reverse_iterator operator++ ( int )
            {
                const_reverse_iterator old = *this;
                ++( *this );
                return old;
            }
            const_reverse_iterator & operator-- ()
            {
                this->current = this->current->next;
                return *this;
            }

            const_reverse_iterator operator-- ( int )
            {
                const_reverse_iterator old = *this;
                --( *this );
                return old;
            }

        protected:
            const_reverse_iterator( Node* p ): const_iterator{ p } {}

            friend class List<Object>;
        };

    public:

        List()
        { init(); }

        List( const List &rhs )
        {
            init();
            for( auto &x : rhs ) {
                push_back( x );
            }
        }

        ~List()
        {
            clear();
            delete head;
            delete tail;
        }

        List & operator= ( const List &rhs )
        {
            List copy = rhs;
            std::swap( *this , copy );
            return *this;
        }

        List( List &&rhs ): theSize{ rhs.theSize } , head{ rhs.head } , tail{ rhs.tail }
        {
            rhs.theSize = 0;
            rhs.head = nullptr;
            rhs.tail = nullptr;
        }

        List & operator= ( List &&rhs )
        {
            std::swap( theSize , rhs.theSize );
            std::swap( head , rhs.head );
            std::swap( tail , rhs.tail );

            return *this;
        }

        iterator begin()
        { return iterator{ head->next }; }

        const_iterator begin() const
        { return const_iterator{ head->next }; }

        iterator end()
        { return iterator{ tail }; }

        const_iterator end() const
        { return const_iterator{ tail }; }

        reverse_iterator rbegin()
        { return reverse_iterator{ tail->prev }; }

        const_reverse_iterator rbegin() const
        { return const_reverse_iterator{ tail->prev }; }

        reverse_iterator rend()
        { return reverse_iterator{ head }; }

        const_reverse_iterator rend() const
        { return const_reverse_iterator{ head }; }



        int size() const
        { return theSize; }

        bool empty() const
        { return size() == 0 ;}

        void clear()
        {
            while( !empty() )
                pop_front();
        }

        Object & front()
        { return *begin(); }

        const Object & front() const
        { return *begin(); }

        Object & back()
        { return *--end(); }

        const Object & back() const
        { return *--end(); }

        void push_front( const Object &x )
        { insert( begin() , x ); }

        void push_front( Object &&x )
        { insert( begin() , std::move( x ) ); }

        void push_back( const Object &x )
        { insert( end() , x ); }

        void push_back( Object &&x )
        { insert( end() , std::move( x ) ); }

        void pop_front()
        { erase( begin() ); }

        void pop_back()
        { erase( --end() ); }

        iterator insert( iterator itr , const Object &x )
        {
            Node* p = itr.current;
            theSize ++;

            return { p->prev = p->prev->next = new Node{ x , p->prev , p } };
        }

        iterator insert( iterator itr , Object &&x )
        {
            Node* p = itr.current;
            theSize ++;
            return { p->prev = p->prev->next = new Node{ std::move( x ) , p->prev , p } };
        }

        iterator erase( iterator itr )
        {
            Node* p = itr.current;
            iterator retVal{ p->next };
            p->prev->next = p->next;
            p->next->prev = p->prev;

            delete p;

            theSize --;

            return retVal;
        }

        iterator erase( iterator from , iterator to )
        {
            for( iterator itr = from ; itr != to ; )
                itr = erase( itr );

            return to;
        }

    private:
        int theSize;
        Node *head;
        Node *tail;

        void init()
        {
            theSize = 0;
            head = new Node;
            tail = new Node;
            head->next = tail;
            tail->prev = head;
        }
    };
}

#endif // LIST_H_INCLUDED 

[JLBorges]

Just as there must be an implicit conversion from iterator to const_iterator, there must be an implicit conversion from reverse_iterator to const_reverse_iterator.

If the iterator adapter std::reverse_iterator http://en.cppreference.com/w/cpp/iterator/reverse_iterator is not to be used, either inherit reverse_iterator from const_reverse_iterator or provide a (non-explicit) conversion operator.

[mpark4656]

@JLBorges

You are right. I've fixed the problem by inheriting reverse_iterator from const_reverse_iterator instead of iterator...

I don't really understand. I've defined two functions (Overloaded):

reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

So why does my::List<int>::const_reverse_iterator itr = test.rbegin(); require implicit conversion? The complier should know that const_reverse_iterator rbegin() const must be used because the return types are distinct.

Do you happen to have a good reference for implicit conversion and why this has anything to do with how classes are inherited? Also, you've mentioned a non-explicit conversion operator. Could you give me an example of that as well?

As always, I appreciate your help.

[JLBorges]

> After all, the return types are distinct.

The return type does not participate in function overload resolution.

If test is a non-const object, test.rbegin() will resolve to the non-const overload of the function.
If test is a const object, test.rbegin() will resolve to the const overload of he function.


> implicit conversion and why this has anything to do with how classes are inherited?

In statically typed languages, inheritance (public inheritance) establishes a type-subtype relationship between the base class and the derived class. The derived class object IS-A base class object, this IS-A relationship is supported by implicit conversions.


> a non-explicit conversion operator. Could you give me an example of that as well?

There is an example on this page: http://en.cppreference.com/w/cpp/language/cast_operator

[mpark4656]

Thank you.

[Apple444]

thank you so much!!!
https://19216801.mobi/