#include <iostream>

using namespace std;

template <typename Object>

class List

{

    private:

        struct Node                             //List内部维护的节点类

        {

            Object data;

            Node *prev;

            Node *next;

            Node( const Object &d = Object(),Node *p = NULL,Node *n = NULL )

                : data( d ),prev( p ),next( n ) { }

        };

    public:

        class const_iterator                    //常量迭代器

        {

            public:

                const_iterator() : current( NULL )

                { }

                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;

                }

                bool operator== ( const const_iterator &rhs ) const

                { return current == rhs.current; }

                bool operator!= ( const const_iterator &rhs ) const

                { return !( *this == rhs ); }

            protected:

                Node *current;

                Object &retrieve() const

                { return current->data; }

                const_iterator( Node *p ) : current( p )

                { }

                friend class List<Object>;

        };

        class iterator : public const_iterator  //迭代器类继承自常量迭代器类

        {

            public:

            iterator()

            { }

            Object &operator*()

            { return const_iterator::retrieve(); }

            const Object &operator*() const

            { return const_iterator::operator*(); }

            iterator &operator++()

            {

                const_iterator::current = const_iterator::current->next;

                return *this;

            }

            iterator operator++( int )

            {

                iterator old = *this;

                ++( *this );

                return old;

            }

            protected:

                iterator( Node *p ) : const_iterator( p )

                { }

                friend class List<Object>;

        };

    public:

        List()

        { init(); }

        ~List()

        {

            clear();

            delete head;

            delete tail;

        }

        List( const List &rhs )

        {

            init();

            *this = rhs;

        }

        const List &operator= ( const List &rhs )

        {

            if ( this == &rhs )

                return *this;

            clear();

            for ( const_iterator itr = rhs.begin() ; itr != rhs.end() ; ++itr )

                push_back( *itr );

            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 ); }

        int size() const

        { return theSize; }

        bool empty() const

        { return size() == ; }

        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_back( const Object &x )

        { insert( end(),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 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 start,iterator end )

        {

            for ( iterator itr = start ; itr != end; )

                itr = erase( itr );

            return end;

        }

    private:

        int theSize;

        Node *head;

        Node *tail;

        void init()

        {

            theSize = ;

            head = new Node;

            tail = new Node;

            head->next = tail;

            tail->prev = head;

        }

};

void printLots( List<int> &L,List<int> &P )         //打印出L链表 指定位置（P中存放）的值

{

    List<int>::const_iterator itr = L.begin();

    int count = ;                                  //P是升序排列那么不必每次遍历L，维护计数器一直递增迭代器即可

    for ( List<int>::const_iterator itr_P = P.begin() ; itr_P != P.end() ; ++itr_P ){

        int pos = *itr_P;

        while ( pos != count ){

            if ( itr == L.end() )

                return ;

            count++;

            itr++;

        }

        if ( itr != L.end() )

            cout << *itr << endl;

    }

    return ;

}

int main( void )

{

    List<int> p,temp;

    p.push_back(  );

    p.push_back(  );

    temp.push_back(  );

    temp.push_back(  );

    cout << "The pos List:" << endl;

    for ( List<int>::iterator iter = p.begin() ; iter != p.end() ; ++iter )

        cout << *iter << " ";

    cout << endl;

    cout << "The temp List:" << endl;

    printLots( temp,p );

    return ;

}